Polyhedral techniques in combinatorial optimization I: Theory

K. Aardal and C. P. M. van Hoesel

Statistica Neerlandica, 1996, vol. 50, issue 1, 3-26

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.

Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1111/j.1467-9574.1996.tb01478.x

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:stanee:v:50:y:1996:i:1:p:3-26

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0039-0402

Access Statistics for this article

Statistica Neerlandica is currently edited by Miroslav Ristic, Marijtje van Duijn and Nan van Geloven

More articles in Statistica Neerlandica from Netherlands Society for Statistics and Operations Research
Bibliographic data for series maintained by Wiley Content Delivery ().