Today, Large Neighborhood Search (LNS) [PER] is the preferred heuristic algorithm in solvers like CP Optimizer, Google OR-Tools, or OptalCP, as it offers a better ability to escape local optima and higher diversity in the exploration than previously often used Local Search. At the same time, Failure-Directed Search (FDS) [VIL] is used to efficiently explore the whole search space using a Fail-First principle to prove that no solution or better solution than the one found so far exists. Nevertheless, CP solvers are less efficient when a criterion is more complex than, e.g., makespan minimization in scheduling. But any algorithm that quickly provides a good solution, even without optimality guarantees, can be used inside the CP solver in the same way as LNS. The objective values of found solutions can be used as bounds (hard constraints on objective value), limiting the search space for the FDS. Thus, the better the provided solution is, the faster FDS explores the whole solution space.
This opens up research areas like a hybridization of problem-oriented heuristics and CP solvers that can lead to better performance while sharing the objective value and no-goods among heuristics and CP workers. We expect to explore utilizing machine learning (ML) in search algorithms, such as guiding search branching. Due to our collaboration with Petr Vilím, OptalCP [OPT] developer, we expect to exchange more information between the heuristic and the solver during the algorithm run.
[PER] L. Perron, P. Shaw, V. Furnon, Propagation guided large neighborhood search, in: M. Wallace (Ed.), Principles and Practice of Constraint Programming – CP 2004, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 468–481.
[OPT] ScheduleOpt: OptalCP’s solver landing page (2023). URL https://scheduleopt.com/
[VIL ]P. Vilím, P. Laborie, P. Shaw, Failure-directed search for constraint-based scheduling, in: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer, 2015, pp. 437–453.