- author = "Alisa Vorokhta and Gwen Maudet and Gregoire Danoy",
- title = "Selecting the Best Lower-Bound Strategy in a Branch-and-Bound Algorithm Using Genetic Programming",
- booktitle = "International Workshop on Big Optimization, WBO 2025",
- year = "2025",
- editor = "Claudia Cavallaro and Carolina Crespi",
- pages = "48--63",
- address = "Catania, Italy",
- month = "31 " # jul # "-1 " # aug,
- organisation = "Department of Mathematics and Computer Science, University of Catania",
- publisher = "Springer Nature",
- keywords = "genetic algorithms, genetic programming, GPLB",
- isbn13 = "978-3-032-15455-2",
-
URL = "
https://www.ants-lab.it/wbo2025/assets/pdf/program-wbo2025.pdf",
-
DOI = "
10.1007/978-3-032-15455-2_4",
- abstract = "Branch-and-bound (B&B) algorithms are exact methods widely used to solve combinatorial optimization problems. A critical component of B&B is the computation of lower bounds (LB), which significantly impacts the efficiency of pruning and, thus, overall performance. In many B&B applications, multiple alternative LB methods are available, and no single one performs best in all situations. To address this, we propose an adaptive approach based on a genetic programming (GP) hyper-heuristic, called GPLB (GP for LB selection), which dynamically chooses the most suitable LB based on node characteristics and computational constraints. Our approach is evaluated on the permutation flowshop scheduling problem (PFSP). Our GP-based strategies consistently outperform the most common LB methods, achieving improvements of up to 3.74 percentage points. Our method also surpassed other baselines even with different time limits, demonstrating superior solution quality and computational efficiency. We discuss the scalability of GPLB and its potential for other combinatorial optimization problems",
-
notes = "Published after the workshop.
UltraBO Project
University of Luxembourg",
