PhD defense - Nicolas Isoart - Friday 19 November at 2 p.m (GMT+1)
Marie Pelleau
Title: The Traveling Salesman Problem in Constraint Programming
Abstract:
Several constraint programming (CP) models, based on Lagrangian relaxation (LR), have been introduced to solve the traveling salesman problem (TSP).
In this thesis, we define three new constraints and filtering algorithms based on the structure of the graph. First, the k-cutset constraint imposes that any solution contains a strictly positive and even number of elements in each cutset. Then, the mandatory Hamiltonian path constraint is based on the local search k-opt algorithm. If a path of mandatory edges is not optimal (i.e. it exists a k-opt), then it cannot belong to any optimal solution. Finally, the 1-tree constraint is based on the idea that if the problem can be decomposed in two independent sub-problems, then a part of the 1-tree can be optimal in a sub-problem.
In addition, to speed-up the practical performances, we introduce an algorithm named SSSA to avoid oscillations and non-variations of the objective function of LR, saving useless solving times.
We also parallelize the search for solutions with Embarrassingly Parallel Search (EPS). Unfortunately, a direct application of EPS does not lead to good results for the TSP. Indeed, the decomposition mechanism of EPS is a depth-bounded process whereas the search strategy used to solve the TSP is depth-first. Therefore, we define a diving algorithm fixing this issue. However, sub-problems with extremely different solving times may appear. Thus, we introduce a re-decomposition policy in EPS.
Finally, our experiments on the TSPLib showed that the structural constraints reduce the solving times by an order of magnitude. Moreover, we show that our version of EPS leads to a huge improvement related to the number of cores.
Keywords: CP, TSP, algorithms, optimization, parallelism.