Search Results

Documents authored by Régin, Jean-Charles

Document
DOI: 10.4230/LIPIcs.CP.2024.27
Efficient Implementation of the Global Cardinality Constraint with Costs

Authors: Margaux Schmied and Jean-Charles Régin

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

Abstract
The success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach can be seen as a preprocessing. It is fast and avoids, in practice, a large number of explicit computations of shortest paths.
Cite as

Margaux Schmied and Jean-Charles Régin. Efficient Implementation of the Global Cardinality Constraint with Costs. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schmied_et_al:LIPIcs.CP.2024.27,
  author =	{Schmied, Margaux and R\'{e}gin, Jean-Charles},
  title =	{{Efficient Implementation of the Global Cardinality Constraint with Costs}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{27:1--27:18},
  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.27},
  URN =		{urn:nbn:de:0030-drops-207126},
  doi =		{10.4230/LIPIcs.CP.2024.27},
  annote =	{Keywords: global constraint, filtering algorithm, cardinality constraints with costs, arc consistency}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.24
MDD Archive for Boosting the Pareto Constraint

Authors: Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin

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

Abstract
Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.
Cite as

Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin. MDD Archive for Boosting the Pareto Constraint. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{malalel_et_al:LIPIcs.CP.2023.24,
  author =	{Malalel, Steve and Malapert, Arnaud and Pelleau, Marie and R\'{e}gin, Jean-Charles},
  title =	{{MDD Archive for Boosting the Pareto Constraint}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{24:1--24:15},
  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.24},
  URN =		{urn:nbn:de:0030-drops-190610},
  doi =		{10.4230/LIPIcs.CP.2023.24},
  annote =	{Keywords: Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.29
A Linear Time Algorithm for the k-Cutset Constraint

Authors: Nicolas Isoart and Jean-Charles Régin

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

Abstract
In CP, the most efficient model solving the TSP is the Weighted Circuit Constraint (WCC) combined with the k-cutset constraint. The WCC is mainly based on the edges cost of a given graph whereas the k-cutset constraint is a structural constraint. Specifically, for each cutset in a graph, the k-cutset constraint imposes that the size of the cutset is greater than or equal to two. In addition, any solution contains an even number of elements from this cutset. Isoart and Régin introduced an algorithm for this constraint. Unfortunately, their approach leads to a time complexity growing with the size of the considered cutsets, i.e. with k. Thus, they introduced an algorithm with a quadratic complexity dealing with k lower or equal to three. In this paper, we introduce a linear time algorithm for any k based on a DFS checking the consistency of this constraint and performing its filtering. Experimental results show that the size of most of the k-cutsets is lower or equal than 3. In addition, since the time complexity is improved, our algorithm also improves the solving times.
Cite as

Nicolas Isoart and Jean-Charles Régin. A Linear Time Algorithm for the k-Cutset Constraint. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{isoart_et_al:LIPIcs.CP.2021.29,
  author =	{Isoart, Nicolas and R\'{e}gin, Jean-Charles},
  title =	{{A Linear Time Algorithm for the k-Cutset Constraint}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{29:1--29:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.29},
  URN =		{urn:nbn:de:0030-drops-153200},
  doi =		{10.4230/LIPIcs.CP.2021.29},
  annote =	{Keywords: k-Cutset, TSP, Linear algorithm, Constraint}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.30
A k-Opt Based Constraint for the TSP

Authors: Nicolas Isoart and Jean-Charles Régin

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

Abstract
The LKH algorithm based on k-opt is an extremely efficient algorithm solving the TSP. Given a non-optimal tour in a graph, the idea of k-opt is to iteratively swap k edges of this tour in order to find a shorter tour. However, the optimality of a tour cannot be proved with this method. In that case, exact solving methods such as CP can be used. The CP model is based on a graph variable with mandatory and optional edges. Through branch-and-bound and filtering algorithms, the set of mandatory edges will be modified. In this paper, we introduce a new constraint to the CP model named mandatory Hamiltonian path constraint searching for k-opt in the mandatory Hamiltonian paths. Experiments have shown that the mandatory Hamiltonian path constraint allows us to gain on average a factor of 3 on the solving time. In addition, we have been able to solve some instances that remain unsolved with the state of the art CP solver with a 1 week time out.
Cite as

Nicolas Isoart and Jean-Charles Régin. A k-Opt Based Constraint for the TSP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{isoart_et_al:LIPIcs.CP.2021.30,
  author =	{Isoart, Nicolas and R\'{e}gin, Jean-Charles},
  title =	{{A k-Opt Based Constraint for the TSP}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{30:1--30:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.30},
  URN =		{urn:nbn:de:0030-drops-153212},
  doi =		{10.4230/LIPIcs.CP.2021.30},
  annote =	{Keywords: TSP, k-opt, 1-tree, Constraint}
}
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