ISOART , Nicolas

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

The TSP is the problem of finding a single cycle going through all the vertices of a graph suchthat the sum of the costs of the edges it contains is minimal. It has many applications andhas been motivated by concrete problems, such as school bus routes, logistics, routing, etc. Itis solved in CP with the WCC [2] and the k-cutset constraint [4]....

International audience

International audience

M. Sellmann showed that CP-based Lagrangian relaxation gave good results but the interactions between the two techniques were quite dicult to understand. There are two main reasons for this: the best multipliers do not lead to the best ltering and each ltering disrupts the Lagrangian multiplier problem (LMP) to be solved. As the resolution of...

Several models based on constraint programming have been proposed to solve the traveling salesman problem (TSP). The most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian relaxation of the TSP, based on the search for spanning tree or more precisely "1-tree". The weakness of these approaches is that...

Plusieurs modèles basés sur la programmation par contraintes ont été proposés pour résoudre le problème du voyageur de commerce (TSP). Les plus efficaces, telle que la weighted circuit constraint (WCC), s'appuient prin-cipalement sur la relaxation lagrangienne du TSP, basée sur la recherche d'arbres recouvrants ou plus précisément de...

International audience

International audience