# Search Strategy Generation for Branch and Bound Using Genetic Programming

arXiv: https://arxiv.org/abs/2412.09444 · HTML: https://mlsanity.com/paper/2412.09444/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 12 Dec 2024.

## Builds on (most cited first, 7 of 7)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP](https://mlsanity.com/paper/2007.03948/) (2020)
- [Learning to Search via Retrospective Imitation](https://mlsanity.com/paper/1804.00846/) (2018)

## Built on by (most cited first, 2 of 2)

- [A Distance Metric for Mixed Integer Programming Instances](https://mlsanity.com/paper/2507.11063/) (2025)
- [Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks](https://mlsanity.com/paper/2603.19318/) (2026)

## Abstract (arXiv)

Branch-and-Bound (B&B) is an exact method in integer programming that recursively divides the search space into a tree. During the resolution process, determining the next subproblem to explore within the tree-known as the search strategy-is crucial. Hand-crafted heuristics are commonly used, but none are effective over all problem classes. Recent approaches utilizing neural networks claim to make more intelligent decisions but are computationally expensive. In this paper, we introduce GP2S (Genetic Programming for Search Strategy), a novel machine learning approach that automatically generates a B&B search strategy heuristic, aiming to make intelligent decisions while being computationally lightweight. We define a policy as a function that evaluates the quality of a B&B node by combining features from the node and the problem; the search strategy policy is then defined by a best-first search based on this node ranking. The policy space is explored using a genetic programming algorithm, and the policy that achieves the best performance on a training set is selected. We compare our approach with the standard method of the SCIP solver, a recent graph neural network-based method, and handcrafted heuristics. Our first evaluation includes three types of primal hard problems, tested on instances similar to the training set and on larger instances. Our method is at most 2% slower than the best baseline and consistently outperforms SCIP, achieving an average speedup of 11.3%. Additionally, GP2S is tested on the MIPLIB 2017 dataset, generating multiple heuristics from different subsets of instances. It exceeds SCIP's average performance in 7 out of 10 cases across 15 times more instances and under a time limit 15 times longer, with some GP2S methods leading on most experiments in terms of the number of feasible solutions or optimality gap.