Finding Good Partial Assignments during Restart-Based Branch and Bound Search

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.

Authors

• Hongbo Li Beijing Geekplus Technology Co, Ltd, Beijing, 100101, China
• Jimmy H.M. Lee Department of Computer Science and Engineering, The Chinese University of Hong Kong

Keywords

• CSO: Constraint Optimization
• CSO: Constraint Satisfaction