Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On disjunctive cuts for combinatorial optimization
AU - Letchford, A. N.
PY - 2001/9
Y1 - 2001/9
N2 - In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general. A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product. The disjunctive approach is then compared and contrasted with some other ‘general-purpose’ frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.
AB - In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general. A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product. The disjunctive approach is then compared and contrasted with some other ‘general-purpose’ frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.
KW - integer programming
KW - cutting planes
U2 - 10.1023/A:1011493126498
DO - 10.1023/A:1011493126498
M3 - Journal article
VL - 5
SP - 299
EP - 315
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 3
ER -