Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables

I. R. De Farias, E. L. Johnson, G. L. Nemhauser

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

Many optimisation problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most one variable in a group of nonnegative variables may be positive. Traditionally, in the mathematical programming community, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. Traditionally, constraint programming approaches to such problems keep and use the combinatorial structure, but do not use linear programming bounds in the search for an optimal solution. Here we present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. We review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics. To illustrate the ideas, we present a production scheduling model that arises in the manufacture of fibre optic cables.

Original languageEnglish
Pages (from-to)25-39
Number of pages15
JournalKnowledge Engineering Review
Volume16
Issue number1
DOIs
StatePublished - Mar 2001

Fingerprint

Dive into the research topics of 'Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables'. Together they form a unique fingerprint.

Cite this