.png){kind=icon}
.png){kind=icon}
Return
Towards an unsupervised learning scheme for efficiently solving parameterized mixed-integer programs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2025.107290.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Mixed integer programming (MIP) has been widely utilized to tackle a broad range of real-world decision-making problems, while its solution efficiency remains a key challenge. In this paper, we describe a novel unsupervised learning scheme for accelerating the solution of a family of MIP problems. Distinct substantially from existing learning-to-optimize methods, our proposal seeks to train an autoencoder (AE) for binary variables in an unsupervised learning fashion, using data of optimal solutions to historical instances for a parametric family of MIPs. By a deliberate design of AE architecture and exploitation of its statistical implication, we present a simple and straightforward strategy to construct a class of cutting plane constraints from the decoder parameters of an offline-trained AE. These constraints reliably enclose the optimal binary solutions of new problem instances thanks to the representation strength of AE. More importantly, their integration into the primal MIP problem of an unseen instance leads to a tightened MIP, which can be resolved at decision time using off-the-shelf solvers with much higher efficiency. Our method is applied to two benchmark problems: the batch process scheduling problem, formulated as a mixed-integer linear programming (MILP) problem, and the cart–pole system control problem, formulated as a mixed-integer quadratic programming (MIQP) problem. Comprehensive results demonstrate that our approach significantly reduces the computational cost of off-the-shelf MILP solvers while retaining a high solution quality. The codes of this work are open-sourced at https://github.com/qushiyuan/AE4BV .
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W