Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Mixed-integer linear programming (MILP) is crucial for real-world applications.
• Current MILP solvers rely on human-designed heuristics for cut selection.
• Existing machine learning methods often overlook the number and order of cuts.

Purpose of the Study:

• To develop a data-driven methodology for learning effective cut selection policies in MILPs.
• To address the simultaneous challenges of selecting which cuts to prefer, how many cuts to select, and in what order.
• To improve the overall efficiency of MILP solvers through advanced machine learning.

Main Methods:

• Proposed a novel hierarchical sequence/set model (HEM) for MILP cut selection.
• HEM features a bi-level architecture: a higher-level module for cut cardinality and a lower-level module for ordered subset selection.
• Formulated cut selection as a sequence/set-to-sequence learning problem within the lower-level module.

Main Results:

• HEM effectively learns to select the number, identity, and order of cuts.
• The proposed model significantly enhances MILP solving efficiency across eleven challenging benchmarks.
• Demonstrated superior performance compared to existing heuristic and learning-based approaches.

Conclusions:

• HEM represents the first data-driven approach to simultaneously optimize MILP cut selection criteria (P1-P3).
• The hierarchical model offers a powerful new direction for improving optimization solver performance.
• HEM shows practical applicability, including on real-world problems from Huawei.