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.

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.