Solution-Based Phase Saving for CP: A Value-Selection Heuristic to Simulate Local Search Behavior in Complete Solvers

Large neighbourhood search, a meta-heuristic, has proven tobe successful on a wide range of optimisation problems. The algorithmrepeatedly generates and searches through a neighbourhood around thecurrent best solution. Thus, it finds increasingly better solutions by solv-ing a series of simplified problems, all of which are related to the currentbest solution. In this paper, we show that significant benefits can be ob-tained by simulating local-search behaviour in constraint programmingby using phase saving based on the best solution found so far duringthe search, activity-based search (VSIDS), and nogood learning. The ap-proach is highly effective despite its simplicity, improving the highestscoring solver, Chuffed, in the free category of the MiniZinc Challenge2017, and can be easily integrated into modern constraint programmingsolvers. We validated the results on a wide range of benchmarks from thecompetition library, comparing against seventeen state-of-the-art solvers.

Authors: Emir Demirovic, Geoffrey Chu, and Peter J. Stuckey