Project description/target:

Develop a machine learning guided predict-and-search framework to efficiently identify high-quality feasible solutions to mixed-integer linear programming (MILP) problems.

Challenges/pain points:

In real-world settings, MILP models from the same application share similar patterns and characteristics, and such models are routinely solved without making uses of those similarities. Solution-predicting machine learning methods are suitable under such a context, but existing methods:

• ignore feasibility requirements enforced by constraints
• necessitate high sample collection costs

Solution:

• Utilize bipartite graphs to represent MILPs and train a graph neural network (GNN) to learn the weighted conditional marginal probability.
• Adopt a trust region like method to carry out a search algorithm that finds near-optimal solutions around a certain point.

Contribution/application:

• We propose a novel predict-and-search framework that first trains GNNs to predict the weighted conditional marginal probability and then constructs a trust region to search for high quality feasible solutions.
• We demonstrate the ability of our proposed framework to provide equivalently good or better solutions than fixing-based solution-predicting approaches.
• We conduct comprehensive computational studies on several public benchmarks datasets and the computational results show that our proposed framework achieves 51% and 9% smaller primal gaps than state-of-the-art general-purpose optimization solvers SCIP and Gurobi, respectively.

Next step:

• Continue to explore the and refine our proposed idea.
• Conduct computational experiments on more generalized datasets.

Collaborators/partners：

Huawei GTS algorithm team

Team/contributors：

Qingyu Han, Linxin Yang, Qian Chen, Akang Wang, Ruoyu Sun, Xiaodong Luo