Search Results

Documents authored by Delecluse, Augustin

Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.36
Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming (Short Paper)

Authors: Augustin Delecluse and Pierre Schaus

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Significant research efforts have focused on black-box variable selection, with less attention given to value heuristics. An ideal value heuristic enables depth-first-search to prioritize high-quality solutions first. The Bound-Impact Value Selection achieves this goal through a look-ahead strategy, trying every value of the selected variable and ranking them based on their impact on the objective. However, this method is generally too computationally intensive for the entire search tree. We introduce two simple yet powerful modifications to improve its scalability. First, a lighter fix point computation involving only the constraints on the shortest path in the constraint graph between the variable and the objective. Second, a reverse look-ahead strategy optimistically fixes the objective variable to its minimum in order to prioritize the remaining values. These two ideas have been empirically validated on a range of academic problems and in the XCSP³ competition, demonstrating significant improvements in scalability.
Cite as

Augustin Delecluse and Pierre Schaus. Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{delecluse_et_al:LIPIcs.CP.2024.36,
  author =	{Delecluse, Augustin and Schaus, Pierre},
  title =	{{Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.36},
  URN =		{urn:nbn:de:0030-drops-207214},
  doi =		{10.4230/LIPIcs.CP.2024.36},
  annote =	{Keywords: Constraint Programming, Value Selection, Look-Ahead, Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.19
Sequence Variables for Routing Problems

Authors: Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Constraint Programming (CP) is one of the most flexible approaches for modeling and solving vehicle routing problems (VRP). This paper proposes the sequence variable domain, that is inspired by the insertion graph introduced in [Bent and Van Hentenryck, 2004] and the subset bound domain for set variables. This domain representation, which targets VRP applications, allows for an efficient insertion-based search on a partial tour and the implementation of simple, yet efficient filtering algorithms for constraints that enforce time-windows on the visits and capacities on the vehicles. Experiment results demonstrate the efficiency and flexibility of this CP domain for solving some hard VRP problems, including the Dial-A-Ride, the Patient Transportation, and the asymmetric TSP with time windows.
Cite as

Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck. Sequence Variables for Routing Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{delecluse_et_al:LIPIcs.CP.2022.19,
  author =	{Delecluse, Augustin and Schaus, Pierre and Van Hentenryck, Pascal},
  title =	{{Sequence Variables for Routing Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.19},
  URN =		{urn:nbn:de:0030-drops-166485},
  doi =		{10.4230/LIPIcs.CP.2022.19},
  annote =	{Keywords: Constraint Programming, Dial-A-Ride, Patient Transportation, TSPTW, Vehicle Routing, Sequence Variables, Insertion Variables}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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