DROPS

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

Search Results

Documents authored by Isoart, Nicolas

A Linear Time Algorithm for the k-Cutset Constraint

Abstract

Cite as

A k-Opt Based Constraint for the TSP

Abstract

Cite as

Thanks for your feedback!

Could not send message