Polyhedral techniques in combinatorial optimization

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

Research output: Book/ReportReportAcademic

186 Downloads (Pure)

Abstract

Combinatorial optimization problems arise in several areas ranging from management to mathematics and graph theory. Most combinatorial optimization problems 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 development in polyhedral techniques leading to an increase in the size of several problem types that can be solved by a factor hundred. 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. The purpose of this article 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 discuss several computational aspects and implementation issues related to the use of polyhedral methods.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages44
Publication statusPublished - 1995

Publication series

NameMemorandum COSOR
Volume9515
ISSN (Print)0926-4493

Fingerprint

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

Cite this