DROPS

Artifact

Software

KAOC-chuffed

Authors: Samuel Cloutier and Claude-Guy Quimper

Abstract

Cite as

Samuel Cloutier, Claude-Guy Quimper. KAOC-chuffed (Software, Source Code, Instances, and Results). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26894,
   title = {{KAOC-chuffed}}, 
   author = {Cloutier, Samuel and Quimper, Claude-Guy},
   note = {Software (visited on 2026-07-13)},
   url = {https://github.com/Samclou/chuffed/releases/tag/KAOC-cp2026},
   doi = {10.4230/artifacts.26894},
}

Document

DOI: 10.4230/LIPIcs.CP.2026.13

Augmenting the Cumulative Overload Check with Integral Resource Usage Reasoning

Authors: Samuel Cloutier and Claude-Guy Quimper

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

Abstract

Few amongst the rules that filter the Cumulative constraint reason on the integrity of resource consumption. We augment the overload check with an integral reasoning that better evaluates resource availability. This reasoning is based on the knapsack problem, which we solve using dynamic programming. Our new rule subsumes the time table horizontally elastic overload check while its running time complexity is 𝒪(C n²), only increasing by a factor C (the resource capacity) due to solving knapsack problems. Exploiting word-parallelism actually makes this complexity 𝒪(C/w n²) for w-bit machines. On usual instances, C is small and this complexity collapses back to 𝒪(n²). Our algorithm generates explanations for lazy clause generation solvers. With our new knapsack augmented overload check, we are able to solve all but 5 instances of the Pack benchmark. By performing a small transformation of the instances, we show that our method is more robust than known pre-solving methods that perform well on the original benchmark.

Cite as

Samuel Cloutier and Claude-Guy Quimper. Augmenting the Cumulative Overload Check with Integral Resource Usage Reasoning. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cloutier_et_al:LIPIcs.CP.2026.13,
  author =	{Cloutier, Samuel and Quimper, Claude-Guy},
  title =	{{Augmenting the Cumulative Overload Check with Integral Resource Usage Reasoning}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{13:1--13:17},
  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.13},
  URN =		{urn:nbn:de:0030-drops-266464},
  doi =		{10.4230/LIPIcs.CP.2026.13},
  annote =	{Keywords: Scheduling, Cumulative constraint, Knapsacks, Overload check}
}

Document

DOI: 10.4230/LIPIcs.CP.2024.7

Cumulative Scheduling with Calendars and Overtime

Authors: Samuel Cloutier and Claude-Guy Quimper

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

Abstract

In project scheduling, calendar considerations can increase the duration of a task when its execution overlaps with holidays. On the other hand, the use of overtime may decrease the task’s duration. We introduce the CalendarOvertime constraint which verifies that a task follows a calendar with overtime and holidays. We also introduce the CumulativeOvertime constraint, a variant of the Cumulative constraint, that also reasons with the calendars when propagating according to the resource consumption, the overtime, and the holidays. Experimental results of a RCPSP model on the PSPLIB, BL, and PACK instances augmented with calendars and overtime show that the use of the CalendarOvertime constraint offers a speedup greater than 2.9 on the instances optimally solved and finds better solutions on more than 79% of the remaining instances when compared to a decomposition of the constraint. We also show that the use of our CumulativeOvertime constraint further improves these results.

Cite as

Samuel Cloutier and Claude-Guy Quimper. Cumulative Scheduling with Calendars and Overtime. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cloutier_et_al:LIPIcs.CP.2024.7,
  author =	{Cloutier, Samuel and Quimper, Claude-Guy},
  title =	{{Cumulative Scheduling with Calendars and Overtime}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{7:1--7:16},
  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.7},
  URN =		{urn:nbn:de:0030-drops-206927},
  doi =		{10.4230/LIPIcs.CP.2024.7},
  annote =	{Keywords: Constraint programming, Scheduling, Global constraints, Calendars, Overtime, Cumulative constraint, Time-Tabling}
}

Search Results

Documents authored by Cloutier, Samuel

KAOC-chuffed

Abstract

Cite as

Augmenting the Cumulative Overload Check with Integral Resource Usage Reasoning

Abstract

Cite as

Cumulative Scheduling with Calendars and Overtime

Abstract

Cite as

Thanks for your feedback!

Could not send message