Separating comb inequalities is NP-hard

Yohan Finet, Victor Drouin-Touchette

Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in p…