Search Results

Documents authored by Vilím, Petr

Document
DOI: 10.4230/LIPIcs.CP.2026.28
Accelerating Constraint Programming Solver with Parallel External Heuristics: Experiments on Scheduling and Routing Problems

Authors: Vilém Heinz, Šimon Zvára, Vít Knobloch, Zdeněk Hanzálek, and Petr Vilím

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Constraint Programming (CP) is a powerful optimization method that provides optimality guarantees, but due to its exact nature, its scalability to large instances is often limited. To address this, we propose a hybrid approach that combines a CP solver with heuristic methods, directly and asynchronously exchanging solutions and objective values during runtime. The hybrid parallel configuration yields faster convergence to good solutions across various problem domains than the solver alone, while retaining the ability to guarantee optimality, leveraging the complementary nature of the CP solver and heuristics. The efficiency of this approach is evaluated on three well-known scheduling problems and three well-known routing problems. Noticeable improvements are observed for the Flow-shop Scheduling Problem (FSSP), the Traveling Salesman Problem (TSP), and the Vehicle Routing Problem with Time Windows (VRP-TW). Even for problems where improvements are marginal, the portfolio of methods increases the robustness of the approach.
Cite as

Vilém Heinz, Šimon Zvára, Vít Knobloch, Zdeněk Hanzálek, and Petr Vilím. Accelerating Constraint Programming Solver with Parallel External Heuristics: Experiments on Scheduling and Routing Problems. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{heinz_et_al:LIPIcs.CP.2026.28,
  author =	{Heinz, Vil\'{e}m and Zv\'{a}ra, \v{S}imon and Knobloch, V{\'\i}t and Hanz\'{a}lek, Zden\v{e}k and Vil{\'\i}m, Petr},
  title =	{{Accelerating Constraint Programming Solver with Parallel External Heuristics: Experiments on Scheduling and Routing Problems}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.28},
  URN =		{urn:nbn:de:0030-drops-266608},
  doi =		{10.4230/LIPIcs.CP.2026.28},
  annote =	{Keywords: Constraint Programming, Hybridization, Heuristics, Discrete Optimization, Scheduling, Routing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2023.5
CP Solver Design for Maximum CPU Utilization (Invited Talk)

Authors: Petr Vilím

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
In this talk, I explain how to improve the performance of a solver without focusing on algorithms, search, propagation or parallelism. Performance is achieved instead with better CPU utilization, efficient code and more precise design of the solver itself. In the words of Fedor G. Pikus [Pikus, 2021], the time of "performance taking care of itself" is over. In today’s hardware the number of cores is increasing while the CPU clock speed has reached a plateau. Main memory access is slow in comparison to the CPU. And despite multiple memory cache levels, the CPU can easily become idle waiting for data from the memory, slowing down the computation considerably. Unfortunately, those trends are probably not going to change in the near future. For those reasons we are witnessing revived interest in efficient code and performance-centered software design, especially in areas where the performance is critical: computer games, compilers, internet browsers, language interpreters (e.g. JavaScript or Python), etc. The good news is that many of the tricks used in the above-mentioned areas, can be used in constraint programming as well. The bad news is that the performance has to be taken into account from the very beginning of the design. It is not possible to add it easily later. Sometimes, better performance can be achieved only by radical shifts in the design such as from object-oriented to data-oriented programming. The design of a CP solver is not an exception in this regard. Without the efficient core of the CP solver, it is not possible to write truly efficient propagation or search algorithms. On the other hand, all algorithms in the solver must take the design of the solver into account and leverage it. In this talk, I will describe what I consider the most important aspects of the design of ScheduleOpt Optal solver. I will concentrate on the performance, but I will also mention other aspects such as ease of use, maintainability, and testing.
Cite as

Petr Vilím. CP Solver Design for Maximum CPU Utilization (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vilim:LIPIcs.CP.2023.5,
  author =	{Vil{\'\i}m, Petr},
  title =	{{CP Solver Design for Maximum CPU Utilization}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.5},
  URN =		{urn:nbn:de:0030-drops-190425},
  doi =		{10.4230/LIPIcs.CP.2023.5},
  annote =	{Keywords: Constraint Programming, Software Design, Efficient Code}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact