Relationship Between K-Cutsets and Comb Inequalities

EasyChair Preprint no. 2715

Abstract

The TSP is an NP-Complete problem that has been motivated by concrete problems, such as school bus routes, logistics, routing, etc. Almost all types of resolution methods (MIP, SAT, CP, evolutionary algorithms, etc.) have been used to solve it. In this paper, we are interested by two of them: CP and MIP. The CP method is manly based on the Lagrangian Relaxation of the 1-Tree. The MIP method uses an LP model in combination with cutting-planes. Both of them use structural constraints for their solving. We show that although the formulations of these constraints seem very different, they are in fact very similar.

Keyphrases: comb inequalities, CP, k-cutsets, LP

@Booklet{EasyChair:2715,
  author = {Nicolas Isoart and Jean-Charles Régin},
  title = {Relationship Between K-Cutsets and Comb Inequalities},
  howpublished = {EasyChair Preprint no. 2715},

  year = {EasyChair, 2020}}