Skip to Main content Skip to Navigation
Conference papers

A Circuit Constraint for Multiple Tours Problems

Philippe Vismara 1, 2 Nicolas Briot 1 
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Routing problems appear in many practical applications. In the context of Constraint Programming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem or the Vehicle Routing Problem. These kind of constraints are linked to the search for a Hamiltonian circuit in a graph. In this paper we consider a more general multiple tour problem that consists in covering a part of the graph with a set of minimal cost circuits. We define a new global constraint WeightedSubCircuits that generalizes the WeightedCircuit constraint by releasing the need to obtain a Hamil-tonian circuit. It enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph, the subsets of vertices to be covered being induced by external constraints. We show that enforcing Bounds Consistency for WeightedSubCircuits is NP-hard. We propose an incomplete but polynomial filtering method based on the search for a lower bound of a weighted Steiner circuit.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Philippe Vismara Connect in order to contact the contributor
Submitted on : Thursday, November 15, 2018 - 7:04:05 PM
Last modification on : Wednesday, September 28, 2022 - 3:08:26 PM


Files produced by the author(s)



Philippe Vismara, Nicolas Briot. A Circuit Constraint for Multiple Tours Problems. CP 2018 - 24th International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.389-402, ⟨10.1007/978-3-319-98334-9_26⟩. ⟨lirmm-01924361⟩



Record views


Files downloads