Abstract
Mixed-Integer Linear Programming (MILP) is fundamental to solving complex discrete optimization problems across various industries. The efficiency of the standard Branch-and-Bound (B&B) algorithm depends heavily on the Search Strategy (SS) used for node selection. This paper presents GP2S, a method that employs Genetic Programming to automatically evolve lightweight, symbolic mathematical expressions for node selection. By incorporating a double tournament selection process to control expression complexity, GP2S achieves performance comparable to deep learning models while maintaining the speed and interpretability of traditional heuristics.
Introduction
In discrete optimization, solving MILP problems often involves navigating a massive search space. The Branch-and-Bound (B&B) algorithm manages this by partitioning the problem into a tree of subproblems (nodes). A critical decision in this process is the Search Strategy: determining which node to explore next. Traditional solvers like SCIP rely on hand-crafted heuristics, which are fast but may not be optimal for specific problem classes. Conversely, modern neural network approaches offer high "intelligence" but introduce significant computational overhead.
The researchers propose a middle ground: using Genetic Programming (GP) to discover symbolic formulas that are as fast as heuristics but as effective as learned models.
Methodology: The GP2S Framework
The core of the proposed approach is GP2S (Genetic Programming for Search Strategy). Instead of training black-box models, the system evolves symbolic expressions using basic mathematical operators and node-specific data (terminals) such as depth, lower bounds, and constraint counts.
Evolutionary Process
The evolution begins with a population of random mathematical formulas. These candidates are evaluated based on their ability to solve training instances efficiently. Fitter individuals are selected to undergo genetic operations.
As shown in Figure 1, the process involves two phases:
- Phase 1 (Mating): Combining parts of two successful "parent" trees to create offspring.
- Phase 2 (Mutation): Introducing random changes to a tree to maintain genetic diversity and explore new strategy spaces.
Controlling Bloat with Double Tournament Selection
A common challenge in Genetic Programming is "bloat," where formulas become unnecessarily complex without improving performance. To address this, the authors implemented a Double Tournament Selection mechanism.
In this two-stage process (Figure 2), the first tournament selects candidates based on their fitness (solving speed). A second tournament then selects among the winners based on the size of the symbolic tree, favoring smaller, more efficient formulas. This ensures the resulting search strategies remain lightweight and interpretable.
Experimental Results
The GP2S framework was evaluated on synthetic hard problems (FCMCNF, MAXSAT, GISP) and the industry-standard MIPLIB 2017 benchmark.
- Performance Gains: GP2S achieved an average speedup of 11.3% over the default SCIP solver on synthetic benchmarks. On the diverse MIPLIB dataset, GP2S-generated heuristics outperformed SCIP in 70% of the tested cases.
- Generalization: Strategies evolved on small-scale problems transferred effectively to larger, more complex instances, outperforming Graph Neural Network (GNN) baselines in several transfer tasks.
- Interpretability: The evolved formulas are human-readable, allowing researchers to gain insights into the underlying logic of successful search strategies for specific problem classes.
Conclusion and Future Work
GP2S demonstrates that symbolic expressions evolved through Genetic Programming can provide a powerful, efficient alternative to both hand-crafted heuristics and deep learning models for B&B node selection. While the evolution process is computationally intensive, the resulting strategies offer near-zero overhead during solver execution. Future research will focus on evolving specialized "expert" heuristics for different problem clusters and applying GP to other critical B&B decisions, such as branching and cutting plane selection.
Reference: Maudet, G., & Danoy, G. (2025). Search Strategy Generation for Branch and Bound Using Genetic Programming. Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI-25).
Summary updated