Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On the separation of split cuts and related inequalities
AU - Caprara, A
AU - Letchford, A N
PY - 2003
Y1 - 2003
N2 - The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols and Li. In this paper we settle this question by proving strong NP-completeness of separation for split cuts. As a by-product we also show NP-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen NP-completeness results of Caprara & Fischetti (for {0,1/2}-cuts) and Eisenbrand (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle.
AB - The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols and Li. In this paper we settle this question by proving strong NP-completeness of separation for split cuts. As a by-product we also show NP-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen NP-completeness results of Caprara & Fischetti (for {0,1/2}-cuts) and Eisenbrand (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle.
U2 - 10.1007/s10107-002-0320-3
DO - 10.1007/s10107-002-0320-3
M3 - Journal article
VL - 94
SP - 279
EP - 294
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 2-3
ER -