Search Results

Documents authored by Knobloch, Vít

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}
}
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