Polyhedral techniques in combinatorial optimization I: theory

K.I. Aardal, C.P.M. van Hoesel

    Research output: Contribution to journalArticleAcademicpeer-review

    16 Citations (Scopus)
    1 Downloads (Pure)

    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

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

    Cite this