Polyhedral techniques in combinatorial optimization

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

Onderzoeksoutput: Boek/rapportRapportAcademic

178 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's44
StatusGepubliceerd - 1995

Publicatie series

NaamMemorandum COSOR
Volume9515
ISSN van geprinte versie0926-4493

Vingerafdruk Duik in de onderzoeksthema's van 'Polyhedral techniques in combinatorial optimization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit