Finding Good Partial Assignments during Restart-Based Branch and Bound Search
Open Access
- 26 June 2023
- journal article
- research article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 37 (4) , 4035-4043
Abstract
Restart-based Branch-and-Bound Search (BBS) is a standard algorithm for solving Constraint Optimization Problems (COPs). In this paper, we propose an approach to find good partial assignments to jumpstart search at each restart for general COPs, which are identified by comparing different best solutions found in different restart runs. We consider information extracted from historical solutions to evaluate the quality of the partial assignments. Thus the good partial assignments are dynamically updated as the current best solution evolves. Our approach makes restart-based BBS explore different promising sub-search-spaces to find high-quality solutions. Experiments on the MiniZinc benchmark suite show how our approach brings significant improvements to a black-box COP solver equipped with the state of the art search techniques. Our method finds better solutions and proves optimality for more instances.Keywords
This publication has 3 references indexed in Scilit:
- Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern MiningProceedings of the AAAI Conference on Artificial Intelligence, 2020
- Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems1998
- Optimal speedup of Las Vegas algorithmsInformation Processing Letters, 1993