HTS-LB: Hypergraph tree search for learning branch.

Area of Science:

• Combinatorial Optimization
• Machine Learning
• Operations Research

Background:

• Mixed Integer Linear Programming (MILP) is crucial for resource-constrained problems.
• Existing machine learning approaches for MILP solving face challenges in scalability, information richness, and branching accuracy.
• Current methods often represent MILPs as bipartite graphs, limiting their effectiveness.

Purpose of the Study:

• To propose a novel framework, Hypergraph Tree Search for Learning Branch (HTS-LB), to address limitations in machine learning-based MILP solving.
• To enhance the scalability, information richness, and branching accuracy of MILP solvers.
• To improve the decision-making process in solving complex optimization problems.

Main Methods:

• Representing MILPs using hypergraphs for improved scalability.
• Developing a Hypergraph Attention Network (HAN) for accurate branching policy encoding.
• Implementing a tree search gating mechanism to capture dynamic information for variable representation updates.

Main Results:

• HTS-LB demonstrates superior performance over popular machine learning algorithms on NP-hard MILP problems.
• The framework achieves higher branching accuracy, fewer branch and bound nodes, and a smaller dual-primal gap.
• Integration into the SCIP solver showcases strong generalization for large-scale MILPs.

Conclusions:

• The proposed HTS-LB framework effectively addresses key challenges in machine learning-based MILP solving.
• HTS-LB offers significant improvements in efficiency and accuracy for complex optimization tasks.
• This approach shows promise for advancing the field of combinatorial optimization through machine learning integration.