진학프로석·박사 채용 접수 플랫폼

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 even if such algorithm is not as generic as CP when used to solve a specific scheduling problem, for example. 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 reasoning 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.

About the group: The Industrial Informatics Department, led by Zdenek Hanzalek, is oriented towards scheduling, combinatorial optimization, and automated cars. The group collaborates strongly with high-tech companies (CEZ – Czech Energy Group, Porsche Engineering Services, EATON, Skoda Auto, ST Microelectronics, Volkswagen, DHL, …).

[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.