4 Search Results for "Cappart, Quentin"

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.34
Scheduling the Equipment Maintenance of an Electric Power Transmission Network Using Constraint Programming

Authors: Louis Popovic, Alain Côté, Mohamed Gaha, Franklin Nguewouo, and Quentin Cappart

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

Abstract
Modern electrical power utilities must maintain their electrical equipment and replace it when the end of its useful life arrives. The Transmission Maintenance Scheduling (TMS) problem consists in generating an annual maintenance plan for electric power transportation equipment while maintaining the stability of the network and ensuring a continuous power flow for customers. Each year, a list of equipment (power lines, capacitors, transistors, etc.) that needs to be maintained or replaced is available and the goal is to generate an optimal maintenance plan. This paper proposes a constraint-based scheduling approach for solving the TMS problem. The model considers two types of constraints: (1) constraints that can be naturally formalized inside a constraint programming model, and (2) complex constraints that do not have a proper formalization from the field specialists. The latter cannot be integrated inside the model due to their complexity. Their satisfaction is thus verified by a black box tool, which is a simulator that mimics the impact of a maintenance schedule on the real power network. The simulator is based on complex differential power-flow equations. Experiments are carried out at five strategic points of Hydro-Québec power grid infrastructure, and involve more than 200 electrical equipment and 300 withdrawal requests. Results show that the model is able to comply with most of the formalized and unformalized constraints. It also generates maintenance schedules within an execution time of only a few minutes. The generated schedules are similar to the ones proposed by a field specialist and can be used to simulate maintenance programs for the next 10 years.
Cite as

Louis Popovic, Alain Côté, Mohamed Gaha, Franklin Nguewouo, and Quentin Cappart. Scheduling the Equipment Maintenance of an Electric Power Transmission Network Using Constraint Programming. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{popovic_et_al:LIPIcs.CP.2022.34,
  author =	{Popovic, Louis and C\^{o}t\'{e}, Alain and Gaha, Mohamed and Nguewouo, Franklin and Cappart, Quentin},
  title =	{{Scheduling the Equipment Maintenance of an Electric Power Transmission Network Using Constraint Programming}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{34:1--34:15},
  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.34},
  URN =		{urn:nbn:de:0030-drops-166635},
  doi =		{10.4230/LIPIcs.CP.2022.34},
  annote =	{Keywords: Transmission maintenance scheduling, Electric power network, Constraint programming}
}
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}
}
  • Refine by Author
  • 4 Cappart, Quentin
  • 3 Rousseau, Louis-Martin
  • 1 Côté, Alain
  • 1 François, Tristan
  • 1 Gaha, Mohamed
  • Show More...

  • Refine by Classification
  • 2 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 Constraint programming
  • 1 Deep Learning
  • 1 Deep reinforcement learning
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2022
  • 1 2021
  • 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