Learning-Enhanced Optimization Algorithms for MILPs
Develop a machine learning guided predict-and-search framework to efficiently identify high-quality feasible solutions to mixed-integer linear programming (MILP) problems.
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
- 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.
- 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.
- Continue to explore the and refine our proposed idea.
- Conduct computational experiments on more generalized datasets.
Huawei GTS algorithm team
Qingyu Han, Linxin Yang, Qian Chen, Akang Wang, Ruoyu Sun, Xiaodong Luo