Polyhedral Techniques in Combinatorial Optimization

K.I. Aardal, S. van Hoesel

Research output: Working paperDiscussion paperOther research output

346 Downloads (Pure)

Abstract

Combinatorial optimization problems arise in several areas ranging from management to mathematics and graph theory. Most combinatorial optimization problems are compu- tationally 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 anoverview 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
PublisherCentER
Volume1995-57
Publication statusPublished - 1995

Publication series

NameCentER Discussion Paper
Volume1995-57

Fingerprint Dive into the research topics of 'Polyhedral Techniques in Combinatorial Optimization'. Together they form a unique fingerprint.

Cite this