TSP and WeightedCircuit

TSP and the weighted circuit global constraint



The package cptsp.jar provides an implementation of the weighted circuit constraint (updated from [1] to be compatible with choco 3.3.3) and requires the library choco.3.3.3 (as well as java 1.8).

The api to state the constraint and specify one of the relaxation described in [1] is available through a single class
WeightedCircuitFactory.

TSPExample.java provides an example of how to use the library and needs the following TSPlib data set : gr24.tsp to execute properly.

References


[1] Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW. Sylvain Ducomman Hadrien Cambazard and Bernard Penz, AAAI 2016.