Accession Number : ADA132004

Title :   Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems.

Descriptive Note : Technical rept.,


Personal Author(s) : Balas,Egon

PDF Url : ADA132004

Report Date : Jun 1983

Pagination or Media Count : 43

Abstract : The author discusses 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 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. Then introduced is a class of relaxations based on replacing each conjunct (union of polyhdera) by its convex hull. The strength of the relaxation 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 author illustrates the approach on the first of these problems, which is a model for machine sequencing. (Author)

Descriptors :   *Linear programming, *Convex sets, Set theory, optimization, Approximation(Mathematics), Numerical methods and procedures, Hierarchies, Problem solving, Relaxation

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE