Download PDFOpen PDF in browserRelationship Between K-Cutsets and Comb InequalitiesEasyChair Preprint 27152 pages•Date: February 19, 2020AbstractThe 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
|