Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs
This work addresses the computational bottleneck in solving mixed-integer programs for optimization tasks, offering a domain-specific improvement that is incremental in nature.
The paper tackles the problem of efficiently solving parameterized mixed-integer programs by proposing an unsupervised learning scheme that trains an autoencoder on historical optimal solutions to generate cutting plane constraints, which significantly reduces computational costs while maintaining high solution quality in a benchmark batch process scheduling problem.
In this paper, we describe a novel unsupervised learning scheme for accelerating the solution of a family of mixed integer programming (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 the AE. More importantly, their integration into the primal MIP problem leads to a tightened MIP with the reduced feasible region, which can be resolved at decision time using off-the-shelf solvers with much higher efficiency. Our method is applied to a benchmark batch process scheduling problem formulated as a mixed integer linear programming (MILP) 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.