Abstract
Mixed-integer linear programming (MILP) has been a fundamental problem in combinatorial optimization. Previous works have designed a plethora of hard-coded heuristics to accomplish challenging MILP solving with domain knowledge. Driven by the high capability of neural networks, recent research is devoted to replacing manually designed heuristics with learned policies. Although learning-based MILP methods have shown great promise, existing works independently treat the policy learning in each module of MILP solvers without considering their interdependence, severely hurting the solving speed and quality. To address this issue, we propose a novel multi-agent-based policy learning framework for MILP (Collab-Solver), which can collaboratively optimize the policies for multiple modules. Specifically, we formulate the collaboration of cut selection and branching in MILP solving as a Stackelberg game. Under this formulation, we develop a two-phase learning paradigm to stabilize the collaborative policy learning, where the first phase achieves the data-communicated policy pretraining and the second phase further orchestrates the policy learning for various modules. The jointly learned policy significantly improves the solving performance on both synthetic and large-scale real-world MILP datasets. Moreover, the policies learned by Collab-Solver have also demonstrated excellent generalization abilities across different instance sets.
Introduction
Mixed-Integer Linear Programming (MILP) is a versatile tool in combinatorial optimization, essential for applications ranging from power grid management to portfolio optimization. Solving MILP problems is NP-hard, and modern solvers typically employ the Branch-and-Bound (B&B) framework. This framework relies on several heuristic modules, most notably cut selection (adding constraints to tighten the search space) and branching (partitioning the problem into sub-problems).
While recent efforts have replaced these heuristics with neural networks, most approaches train these models in isolation. However, these modules are tightly coupled: the cuts selected directly influence the problem landscape, which in turn affects the optimal branching strategy. Collab-Solver addresses this by treating these modules as collaborative agents.
Methodology: The Collab-Solver Framework
Collab-Solver introduces a multi-agent framework that models solver modules as players in a Stackelberg game. In this leader-follower model, cut selection acts as the "leader," making decisions that the branching "follower" must react to.
Two-Phase Learning Paradigm
To ensure stable training in a multi-agent environment, the authors developed a two-phase approach:
- Phase 1: Pretraining. The cut selection policy ($\pi_c$) is pretrained using Reinforcement Learning. Subsequently, the branching policy ($\pi_b$) is trained via Imitation Learning on an expert dataset generated after applying the learned cuts.
- Phase 2: Concurrent Finetuning. Both policies are optimized together. To manage the non-stationarity of the environment, a two-timescale update rule is applied: the leader (cut selection) updates slowly, while the follower (branching) updates rapidly to adapt to the leader's evolving strategy.
Neural Architecture and Communication
The framework utilizes Graph Convolutional Neural Networks (GCNNs) to encode the bipartite graph structure of MILP instances. For cut selection, LSTMs and Pointer Networks handle sequences of candidate cuts. A "Communication Bond" allows agents to share MILP features, ensuring that the cut selection policy considers the global optimization context.
Experimental Results
Collab-Solver was evaluated across eight NP-hard benchmarks, including synthetic sets (e.g., Set Covering, Max Independent Set) and complex real-world datasets (e.g., Production Planning, Item Placement).
- Efficiency and Quality: Collab-Solver achieved up to a 60% speedup over the traditional SCIP solver on standard benchmarks. On highly challenging instances like Item Placement, it significantly reduced the Primal-Dual gap compared to isolated learning methods.
- Generalization: The learned policies demonstrated robust generalization, maintaining a performance edge when scaling from small training instances (500 variables) to much larger test instances (1000 variables).
- Multi-Module Scalability: The framework successfully extended to a three-module hierarchy, incorporating "Predict-and-Search" alongside cut selection and branching.
Conclusion
Collab-Solver demonstrates that the "siloed" approach to training MILP heuristics is suboptimal. By leveraging a game-theoretic framework for collaborative learning, the system achieves significant improvements in solving speed and solution quality. Future work aims to integrate additional modules like presolve and primal heuristics into this collaborative neural framework, moving toward a fully neuralized MILP solver.
Reference: Li, S., Yu, Y., Zhang, Z., et al. "Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming." Science China Information Sciences (arXiv:2508.03030v2).
Summary updated