Polyhedral techniques in combinatorial optimization I: Theory

Research output: Contribution to journalArticleScientificpeer-review

16 Citations (Scopus)

Abstract

Combinatorial optimization problems appear in many disciplines ranging from management and logistics to mathematics, physics, and chemistry. These problems are usually relatively easy to formulate mathematically, but most of them are computationally hard due to the restriction that a subset of the variables have to take integral values. During the last two decades there has been a remarkable progress in techniques based on the polyhedral description of combinatorial problems, leading to a large increase in the size of several problem types that can be solved. The basic idea behind polyhedral techniques is to derive a good linear formulation of the set of solutions by identifying linear inequalities that can be proved to be necessary in the description of the convex hull of feasible solutions. Ideally we can then solve the problem as a linear programming problem, which can be done efficiently. The purpose of this manuscript is to give an overview of the developments in polyhedral theory, starting with the pioneering work by Dantzig. Fulkerson and Johnson on the traveling salesman problem, and by Gomory on integer programming. We also present some modern applications, and computational experience.
Original languageEnglish
Pages (from-to)3-26
Number of pages24
JournalStatistica Neerlandica
Volume50
Issue number1
DOIs
Publication statusPublished - 1996
Externally publishedYes

Fingerprint

Dive into the research topics of 'Polyhedral techniques in combinatorial optimization I: Theory'. Together they form a unique fingerprint.

Cite this