Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction

Understand

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.