12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

97%

97% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > On disjunctive cuts for combinatorial optimization
View graph of relations

« Back

On disjunctive cuts for combinatorial optimization

Research output: Contribution to journalJournal article

Published

<mark>Journal publication date</mark>09/2001
<mark>Journal</mark>Journal of Combinatorial Optimization
Issue3
Volume5
Number of pages17
Pages299-315
<mark>Original language</mark>English

Abstract

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.

Related projects