DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.7

Revisiting Optional Variables in Lazy Clause Generation Solvers for Flexible Scheduling

Authors: Arthur Bit-Monnot

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

Abstract

Optional variables have for a long time been identified as a crucial component of state-of-the-art scheduling solvers. They not only offer a natural way to model many scheduling problems but also play an important role in the efficiency of such solvers by enabling a stronger inference in a constraint propagation engine. Despite this recognition, their adoption in modern solvers remains extremely scarce presumably because their native support requires pervasive changes to a solver and handling many subtleties that have not been extensively studied. In this paper, we aim to provide a good foundation in this direction by providing a formal characterization of optional variables and of their interactions with key components of a constraint programming solver including propagators, reification and lazy clause generation. In addition, we present a new lazy clause generation solver with native support for optional variables and demonstrate its efficiency on variants of the flexible jobshop problem.

Cite as

Arthur Bit-Monnot. Revisiting Optional Variables in Lazy Clause Generation Solvers for Flexible Scheduling. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bitmonnot:LIPIcs.CP.2026.7,
  author =	{Bit-Monnot, Arthur},
  title =	{{Revisiting Optional Variables in Lazy Clause Generation Solvers for Flexible Scheduling}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{7:1--7:23},
  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.7},
  URN =		{urn:nbn:de:0030-drops-266400},
  doi =		{10.4230/LIPIcs.CP.2026.7},
  annote =	{Keywords: Constraint Programming, Scheduling, Lazy-Clause Generation, Optional Variables}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2013.150

Carpooling: the 2 Synchronization Points Shortest Paths Problem

Authors: Arthur Bit-Monnot, Christian Artigues, Marie-José Huguet, and Marc-Olivier Killijian

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks. We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.

Cite as

Arthur Bit-Monnot, Christian Artigues, Marie-José Huguet, and Marc-Olivier Killijian. Carpooling: the 2 Synchronization Points Shortest Paths Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 150-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bitmonnot_et_al:OASIcs.ATMOS.2013.150,
  author =	{Bit-Monnot, Arthur and Artigues, Christian and Huguet, Marie-Jos\'{e} and Killijian, Marc-Olivier},
  title =	{{Carpooling: the 2 Synchronization Points Shortest Paths Problem}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{150--163},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.150},
  URN =		{urn:nbn:de:0030-drops-42517},
  doi =		{10.4230/OASIcs.ATMOS.2013.150},
  annote =	{Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths}
}

Search Results

Documents authored by Bit-Monnot, Arthur

Revisiting Optional Variables in Lazy Clause Generation Solvers for Flexible Scheduling

Abstract

Cite as

Carpooling: the 2 Synchronization Points Shortest Paths Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message