Research map / Learning theory and algorithms / Combinatorial and search optimization
Search Strategy Generation for Branch and Bound Using Genetic Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GP2S, which uses genetic programming to evolve node-scoring functions for a best-first search strategy in SCIP's branch-and-bound, evaluated on three synthetic MILP families and MIPLIB 2017.
Problem
Choosing the next node to explore (search strategy) in branch-and-bound for MILP is crucial for solving time, but handcrafted heuristics are inconsistent and neural approaches are computationally expensive black boxes.
Approach
Define a space of node-scoring trees built from node and model features (depth, best estimate, lower bound, root dual bound, constraint/variable counts) with arithmetic operators, search it with a genetic programming algorithm (double tournament selection), and use the best-scoring function as a best-first search policy inside SCIP.
Key results
- On three synthetic problem types, GP2S is at most 2% slower than the best baseline and achieves an average speedup of 11.3% over SCIP across six categories.
- On MIPLIB 2017 at a 150-second limit, GP2S surpasses SCIP in at least 7 of 10 GP-generated heuristics on both reduced and full sets, per the paper's claim.
- GP training for one problem type takes several days of computation (stated as O(50^3) seconds of solving), a one-time cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GP2S instead of SCIP's default search strategy | SCIP on FCMCNF, MAXSAT, and GISP test and transfer sets · Three synthetic problem types | solving time: average speedup of 11.3% | Helped |
| Use GP2S instead of the best baseline for each instance set | SCIP on FCMCNF, MAXSAT, and GISP test and transfer sets · Three synthetic problem types | solving time | No clear effect |
| Use GP2S 12 instead of SCIP | SCIP · MIPLIB 2017 all, 150 seconds | instances with no feasible solution: 293 -> 232 | Helped |
| Use GP2S 16 instead of SCIP | SCIP · MIPLIB 2017 all, 150 seconds | optimality gap: 1.14$$\pm$$4.8 -> 0.68$$\pm$$4.4 | Helped |
| Use GP2S 12 instead of SCIP | SCIP · MIPLIB 2017 reduced, 150 seconds | instances with no feasible solution: 26 -> 16 | Helped |
| Use GP2S 16 instead of SCIP | SCIP · MIPLIB 2017 reduced, 150 seconds | optimality gap: 0.41$$\pm$$4.1 -> 0.28$$\pm$$5.0 | Helped |
| Train GP2S search strategies on different seed-selected instance subsets | GP2S on MIPLIB 2017 · MIPLIB 2017 reduced and full sets at 150 seconds | instances with no feasible solution and optimality gap: 7 out of 10 | Mixed |
Surprising findings
- No single handcrafted heuristic performs consistently across all three problem types, and GP-generated heuristics' performance varies highly with the training pool.
Limitations
- Performance of GP-generated heuristics on MIPLIB 2017 is highly variable across training seeds and training pools
- Generating a heuristic requires several days of GP computation per problem type
- Evaluated mainly on primal-hard synthetic problems and time-limited MIPLIB runs; GNN baseline excluded from MIPLIB comparison
Experimental setup
Datasets: FCMCNF synthetic instances MAXSAT synthetic instances GISP synthetic instances MIPLIB 2017
Benchmarks: FCMCNF MAXSAT GISP MIPLIB 2017
Metrics: 1-shifted geometric mean solving time number of instances without feasible solution 1-shifted geometric mean optimality gap
Baselines: SCIP default search strategy LB BFS BE BFS BE DFS GNN 2 dives GNN full
Builds on: SCIP DEAP GNN-based search strategy imitation learning
Closest papers by meaning
- Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies (AAAI 2021 · similarity 0.90)
- Learning to Branch in Mixed Integer Programming (AAAI 2016 · similarity 0.88)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.87)
- Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond (NeurIPS 2021 · similarity 0.87)
- Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.87)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.