Search Results

Documents authored by Quimper, Claude-Guy


Document
Acquiring Maps of Interrelated Conjectures on Sharp Bounds

Authors: Nicolas Beldiceanu, Jovial Cheukam-Ngouonou, Rémi Douence, Ramiz Gindullin, and Claude-Guy Quimper

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


Abstract
To automate the discovery of conjectures on combinatorial objects, we introduce the concept of a map of sharp bounds on characteristics of combinatorial objects, that provides a set of interrelated sharp bounds for these combinatorial objects. We then describe a Bound Seeker, a CP-based system, that gradually acquires maps of conjectures. The system was tested for searching conjectures on bounds on characteristics of digraphs: it constructs sixteen maps involving 431 conjectures on sharp lower and upper-bounds on eight digraph characteristics.

Cite as

Nicolas Beldiceanu, Jovial Cheukam-Ngouonou, Rémi Douence, Ramiz Gindullin, and Claude-Guy Quimper. Acquiring Maps of Interrelated Conjectures on Sharp Bounds. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{beldiceanu_et_al:LIPIcs.CP.2022.6,
  author =	{Beldiceanu, Nicolas and Cheukam-Ngouonou, Jovial and Douence, R\'{e}mi and Gindullin, Ramiz and Quimper, Claude-Guy},
  title =	{{Acquiring Maps of Interrelated Conjectures on Sharp Bounds}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{6:1--6:18},
  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.6},
  URN =		{urn:nbn:de:0030-drops-166353},
  doi =		{10.4230/LIPIcs.CP.2022.6},
  annote =	{Keywords: Acquisition of conjectures, digraphs, bounds}
}
Document
A Constraint Programming Approach to Ship Refit Project Scheduling

Authors: Raphaël Boudreault, Vanessa Simard, Daniel Lafond, and Claude-Guy Quimper

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


Abstract
Ship refit projects require ongoing plan management to adapt to arising work and disruptions. Planners must sequence work activities in the best order possible to complete the project in the shortest time or within a defined period while minimizing overtime costs. Activity scheduling must consider milestones, resource availability constraints, and precedence relations. We propose a constraint programming approach for detailed ship refit planning at two granularity levels, daily and hourly schedule. The problem was modeled using the Cumulative global constraint, and the Solution-Based Phase Saving heuristic was used to speedup the search, thus achieving the industrialization goals. Based on the evaluation of seven realistic instances over three objectives, the heuristic strategy proved to be significantly faster to find better solutions than using a baseline search strategy. The method was integrated into Refit Optimizer, a cloud-based prototype solution that can import projects from Primavera P6 and optimize plans.

Cite as

Raphaël Boudreault, Vanessa Simard, Daniel Lafond, and Claude-Guy Quimper. A Constraint Programming Approach to Ship Refit Project Scheduling. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{boudreault_et_al:LIPIcs.CP.2022.10,
  author =	{Boudreault, Rapha\"{e}l and Simard, Vanessa and Lafond, Daniel and Quimper, Claude-Guy},
  title =	{{A Constraint Programming Approach to Ship Refit Project Scheduling}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{10:1--10:16},
  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.10},
  URN =		{urn:nbn:de:0030-drops-166396},
  doi =		{10.4230/LIPIcs.CP.2022.10},
  annote =	{Keywords: Ship refit, planning, project management, constraint programming, scheduling, optimization, resource-constrained project scheduling problem}
}
Document
Constraint Acquisition Based on Solution Counting

Authors: Christopher Coulombe and Claude-Guy Quimper

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


Abstract
We propose CABSC, a system that performs Constraint Acquisition Based on Solution Counting. In order to learn a Constraint Satisfaction Problem (CSP), the user provides positive examples and a Meta-CSP, i.e. a model of a combinatorial problem whose solution is a CSP. This Meta-CSP allows listing the potential constraints that can be part of the CSP the user wants to learn. It also allows stating the parameters of the constraints, such as the coefficients of a linear equation, and imposing constraints over these parameters. The CABSC reads the Meta-CSP using an augmented version of the language MiniZinc and returns the CSP that accepts the fewest solutions among the CSPs accepting all positive examples. This is done using a branch and bound where the bounding mechanism makes use of a model counter. Experiments show that CABSC is successful at learning constraints and their parameters from positive examples.

Cite as

Christopher Coulombe and Claude-Guy Quimper. Constraint Acquisition Based on Solution Counting. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{coulombe_et_al:LIPIcs.CP.2022.15,
  author =	{Coulombe, Christopher and Quimper, Claude-Guy},
  title =	{{Constraint Acquisition Based on Solution Counting}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{15:1--15:16},
  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.15},
  URN =		{urn:nbn:de:0030-drops-166449},
  doi =		{10.4230/LIPIcs.CP.2022.15},
  annote =	{Keywords: Constraint acquisition, CSP, Model counting, Solution counting}
}
Document
A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times

Authors: Alejandro Lopez-Ortiz and Claude-Guy Quimper

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
Consider the problem of scheduling a set of tasks of length p without preemption on $m$ identical machines with given release and deadline times. We present a new algorithm for computing the schedule with minimal completion times and makespan. The algorithm has time complexity O(min(1,p/m)n^2) which improves substantially over the best known algorithm with complexity O(mn^2).

Cite as

Alejandro Lopez-Ortiz and Claude-Guy Quimper. A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 380-391, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{lopezortiz_et_al:LIPIcs.STACS.2011.380,
  author =	{Lopez-Ortiz, Alejandro and Quimper, Claude-Guy},
  title =	{{A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{380--391},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.380},
  URN =		{urn:nbn:de:0030-drops-30282},
  doi =		{10.4230/LIPIcs.STACS.2011.380},
  annote =	{Keywords: Scheduling}
}
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