Download PDFOpen PDF in browser

Relationship Between K-Cutsets and Comb Inequalities

EasyChair Preprint 2715

2 pagesDate: February 19, 2020

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: CP, LP, comb inequalities, k-cutsets

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:2715,
  author    = {Nicolas Isoart and Jean-Charles Régin},
  title     = {Relationship Between K-Cutsets and Comb Inequalities},
  howpublished = {EasyChair Preprint 2715},
  year      = {EasyChair, 2020}}
Download PDFOpen PDF in browser