authors 
Balas, Egon 
year 
1983 
title 
Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems 
source 
December, 1983. 38 p. : ill. includes bibliography 
summary 
The author discuss a new conceptual framework for the convexification of discrete optimization problems, and a general technique for obtaining approximations to the convex hull of the feasible set. The concepts come from disjunctive programming and the key tool is a description of the convex hull of a union of polyhedra in terms of a higher dimensional polyhedron. Although this description was known for several years, only recently was it shown by Jeroslow and Lowe to yield improved representations of discrete optimization problems. The author expresses the feasible set of a discrete optimization problem as the intersection (conjunction) of unions of polyhedra, and define an operation that takes one such expression into another, equivalent one, with fewer conjuncts. He then introduces a class of relaxations based on replacing each conjunct (union of polyhedra) by its convex hull. The strength of the relaxations increases as the number of conjuncts decreases, and the class of relaxations forms a hierarchy that spans the spectrum between the common linear programming relaxation, and the convex hull of the feasible set itself. Instances where this approach presents advantages include critical path problems in disjunctive graphs, network synthesis problems, certain fixed charge network flow problems, etc. The approach on the first of these problems is illustrated, which is a model for machine sequencing 
keywords 
polyhedra, computational geometry, optimization, programming, convex hull, graphs 
series 
CADline 
references 
Contenttype: text/plain

last changed 
1999/02/12 14:07 
