Search Strategy Generation for Branch and Bound Using Genetic Programming
Created by W.Langdon from
gp-bibliography.bib Revision:1.9262
- @InProceedings{DBLP:conf/aaai/MaudetD25,
-
author = "Gwen Maudet and Gregoire Danoy",
-
editor = "Toby Walsh and Julie Shah and Zico Kolter",
-
title = "Search Strategy Generation for Branch and Bound Using
Genetic Programming",
-
booktitle = "AAAI-25, Sponsored by the Association for the
Advancement of Artificial Intelligence, February 25 -
March 4, 2025, Philadelphia, PA, {USA}",
-
pages = "11299--11308",
-
publisher = "{AAAI} Press",
-
year = "2025",
-
keywords = "genetic algorithms, genetic programming, GP2S,
MIPLIB2",
-
timestamp = "Thu, 01 May 2025 01:00:00 +0200",
-
biburl = "
https://dblp.org/rec/conf/aaai/MaudetD25.bib",
-
bibsource = "dblp computer science bibliography, https://dblp.org",
-
URL = "
https://ojs.aaai.org/index.php/AAAI/article/download/33229/35384",
-
URL = "
https://hdl.handle.net/10993/64761",
-
URL = "
https://doi.org/10.1609/aaai.v39i11.33229",
-
DOI = "
10.1609/AAAI.V39I11.33229",
-
size = "10 pages",
-
abstract = "Branch-and-Bound (BB) 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 BB 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 BB 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 percents slower than the best baseline and
consistently outperforms SCIP, achieving an average
speedup of 11.3 percents. 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.",
-
notes = "See also \cite{DBLP:journals/corr/abs-2412-09444}",
- }
Genetic Programming entries for
Gwen Maudet
Gregoire Danoy
Citations