DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.49

The Distance Constraint on Sequence Variables

Authors: Margaux Schmied, Augustin Delecluse, Jean-Charles Régin, and Pierre Schaus

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

Abstract

Insertion sequence variables have recently been introduced as a computational domain for modeling routing and sequencing problems in constraint programming. Typically, search heuristics guide the insertion process of new nodes into a partial growing path, while constraints eliminate infeasible insertions. This paper investigates filtering for the (minimum) distance constraint over insertion sequence variables. This global constraint links a sequence to a distance variable based on a given distance matrix. So far, only a simple filtering algorithm has been proposed, which considers the partial path but ignores mandatory nodes. Our contribution is to introduce stronger lower bounds that also take mandatory nodes into account. These bounds further enable the derivation of additional filtering rules for node insertions. An experimental evaluation on the TourMustSee problem shows that the proposed filtering rules significantly reduce the search space compared to the existing filtering approach.

Cite as

Margaux Schmied, Augustin Delecluse, Jean-Charles Régin, and Pierre Schaus. The Distance Constraint on Sequence Variables. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schmied_et_al:LIPIcs.CP.2026.49,
  author =	{Schmied, Margaux and Delecluse, Augustin and R\'{e}gin, Jean-Charles and Schaus, Pierre},
  title =	{{The Distance Constraint on Sequence Variables}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{49:1--49:19},
  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.49},
  URN =		{urn:nbn:de:0030-drops-266828},
  doi =		{10.4230/LIPIcs.CP.2026.49},
  annote =	{Keywords: Constraint programming, sequence variable, global constraint, cost-based constraint, distance constraint, lower bound}
}

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}
}

Search Results

Documents authored by Schmied, Margaux

The Distance Constraint on Sequence Variables

Abstract

Cite as

Efficient Implementation of the Global Cardinality Constraint with Costs

Abstract

Cite as

Thanks for your feedback!

Could not send message