Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction
This work addresses the challenge of solving similar MIP models efficiently for applications in combinatorial optimization, representing an incremental improvement by integrating machine learning with existing solver techniques.
The paper tackles the problem of accelerating primal solution finding for Mixed Integer Programs (MIPs) by using a Graph Convolutional Network (GCN) to predict solution values for binary variables, which are then used to generate cuts that improve performance in a state-of-the-art solver, as shown in computational evaluations on 8 distinct MIP problem types.
Mixed Integer Programming (MIP) is one of the most widely used modeling techniques for combinatorial optimization problems. In many applications, a similar MIP model is solved on a regular basis, maintaining remarkable similarities in model structures and solution appearances but differing in formulation coefficients. This offers the opportunity for machine learning methods to explore the correlations between model structures and the resulting solution values. To address this issue, we propose to represent an MIP instance using a tripartite graph, based on which a Graph Convolutional Network (GCN) is constructed to predict solution values for binary variables. The predicted solutions are used to generate a local branching type cut which can be either treated as a global (invalid) inequality in the formulation resulting in a heuristic approach to solve the MIP, or as a root branching rule resulting in an exact approach. Computational evaluations on 8 distinct types of MIP problems show that the proposed framework improves the primal solution finding performance significantly on a state-of-the-art open-source MIP solver.