Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems

TLDR

Disjunctive programming provides a description of the convex hull of a union of polyhedra in higher dimensions, and recent work by Jeroslow and Lowe has shown this yields improved representations of discrete optimization problems. The paper introduces a new conceptual framework for convexifying discrete optimization problems and a general technique to approximate their convex hull. The authors express the feasible set as an intersection of unions of polyhedra, define an operation that reduces the number of conjuncts, and introduce a hierarchy of relaxations obtained by replacing each conjunct with its convex hull, strengthening the relaxation as conjuncts decrease from the standard LP relaxation to the full convex hull. The approach yields advantages for critical path problems in disjunctive graphs, network synthesis problems, certain fixed‑charge network flow problems, and is illustrated on a machine‑sequencing model.

Abstract

We 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. We express 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. We then introduce 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 has advantages include critical path problems in disjunctive graphs, network synthesis problems, certain fixed charge network flow problems, etc. We illustrate the approach on the first of these problems, which is a model for machine sequencing.