RL-ISLAP: A Reinforcement Learning Framework for Industrial-Scale Linear Assignment Problems at Alipay

Industrial-scale linear assignment problems (LAPs) are frequently encountered in various industrial scenarios, e.g., asset allocation within the domain of credit management. However, optimization algorithms for such problems (e.g., PJ-ADMM) are highly sensitive to hyper-parameters. Existing solving systems rely on empirical parameter selection, which is challenging to achieve convergence and extremely time-consuming. Additionally, the resulting parameter rules are often inefficient. To alleviate this issue, we propose RL-ISLAP, an efficient and lightweight Reinforcement Learning framework for Industrial-Scale Linear Assignment Problems. We formulate the hyper-parameter selection for PJ-ADMM as a sequential decision problem and leverage reinforcement learning to enhance its convergence. Addressing the sparse reward challenge inherent in learning policies for such problems, we devise auxiliary rewards to provide dense signals for policy optimization, and present a rollback mechanism to prevent divergence in the solving process. Experiments on OR-Library benchmark demonstrate that our method is competitive to SOTA stand-alone solvers. Furthermore, the scale-independent design of observations enables us to transfer the acquired hyper-parameter policy to a scenario of LAPs in varying scales. On two real-world industrial-scale LAPs with up to 10 millions of decision variables, our proposed RL-ISLAP achieves solutions of comparable quality in 2/3 of the time when compared to the SOTA distributed solving system employing fine-tuned empirical parameter rules.