4 Search Results for "Rousseau, Louis-Martin"

Document
DOI: 10.4230/LIPIcs.CP.2023.25
Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver

Authors: Tom Marty, Tristan François, Pierre Tessier, Louis Gautier, Louis-Martin Rousseau, and Quentin Cappart

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. We propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network. Experiments on graph coloring, maximum independent set, and maximum cut problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks.
Cite as

Tom Marty, Tristan François, Pierre Tessier, Louis Gautier, Louis-Martin Rousseau, and Quentin Cappart. Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{marty_et_al:LIPIcs.CP.2023.25,
  author =	{Marty, Tom and Fran\c{c}ois, Tristan and Tessier, Pierre and Gautier, Louis and Rousseau, Louis-Martin and Cappart, Quentin},
  title =	{{Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.25},
  URN =		{urn:nbn:de:0030-drops-190625},
  doi =		{10.4230/LIPIcs.CP.2023.25},
  annote =	{Keywords: Branching heuristic, Deep reinforcement learning}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.35
Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

Authors: Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau

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

Abstract
Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.
Cite as

Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau. Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rudich_et_al:LIPIcs.CP.2022.35,
  author =	{Rudich, Isaac and Cappart, Quentin and Rousseau, Louis-Martin},
  title =	{{Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{35:1--35:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.35},
  URN =		{urn:nbn:de:0030-drops-166647},
  doi =		{10.4230/LIPIcs.CP.2022.35},
  annote =	{Keywords: decision diagrams, discrete optimization, branch-and-bound, sequencing, constraint programming}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.33
Learning TSP Requires Rethinking Generalization

Authors: Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
End-to-end training of neural network solvers for combinatorial optimization problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances of practical scales. Towards leveraging transfer learning to solve large-scale TSPs, this paper identifies inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols.
Cite as

Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning TSP Requires Rethinking Generalization. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{joshi_et_al:LIPIcs.CP.2021.33,
  author =	{Joshi, Chaitanya K. and Cappart, Quentin and Rousseau, Louis-Martin and Laurent, Thomas},
  title =	{{Learning TSP Requires Rethinking Generalization}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.33},
  URN =		{urn:nbn:de:0030-drops-153248},
  doi =		{10.4230/LIPIcs.CP.2021.33},
  annote =	{Keywords: Combinatorial Optimization, Travelling Salesman Problem, Graph Neural Networks, Deep Learning}
}
Document
DOI: 10.4230/DagSemProc.09261.9
Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling

Authors: Marie-Claude Cote, Bernard Gendron, and Louis-Martin Rousseau

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
We present a new implicit formulation for shift scheduling problems, using context-free grammars to model regulation in the composition of shifts. From the grammar, we generate an integer programming (IP) model allowing the same set of shifts as Dantzig’s set covering model. When solved by a state-of-the- art IP solver on problems allowing a small number of shifts, our model, the set covering formulation and a typical implicit model from the literature yield comparable solving times. Moreover, on instances where many shifts are allowed, our model is superior and can encode a wider variety of constraints. Among others, multi-activity cases, which cannot be modeled by existing implicit formulations, can easily be captured with grammars.
Cite as

Marie-Claude Cote, Bernard Gendron, and Louis-Martin Rousseau. Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{cote_et_al:DagSemProc.09261.9,
  author =	{Cote, Marie-Claude and Gendron, Bernard and Rousseau, Louis-Martin},
  title =	{{Grammar-Based Integer Programing Models for Multi-Activity Shift Scheduling}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.9},
  URN =		{urn:nbn:de:0030-drops-21775},
  doi =		{10.4230/DagSemProc.09261.9},
  annote =	{Keywords: Shift Scheduling, Implicit models, Integer Programming, Context-free grammars}
}
  • Refine by Author
  • 4 Rousseau, Louis-Martin
  • 3 Cappart, Quentin
  • 1 Cote, Marie-Claude
  • 1 François, Tristan
  • 1 Gautier, Louis
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Operations research
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Neural networks

  • Refine by Keyword
  • 1 Branching heuristic
  • 1 Combinatorial Optimization
  • 1 Context-free grammars
  • 1 Deep Learning
  • 1 Deep reinforcement learning
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2009
  • 1 2021
  • 1 2022
  • 1 2023

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