Disjunctive Programming

Egon Balas

Publisher:

Springer

Publication Date:

2018

Number of Pages:

238

Format:

Hardcover

Price:

109.99

ISBN:

9783030001476

Category:

Monograph

MAA Review
Table of Contents

[Reviewed by

Brian Borchers

, on

09/22/2019

]

This monograph by the late Egon Balas lays out the disjunctive programming approach to 0-1 mixed integer linear programming (MILP) problems that Balas introduced in the 1970's and developed further throughout his career.

A disjunctive program is a constrained optimization problem with groups of constraints for which at least one constraint in each group must be satisfied. This is a natural way in which to model logical "or" conditions. It has long been known that linear programming problems with disjuctive constraints can be converted into 0-1 MILP problems using the "Big-M method." For example, the disjunctive constraints

\( ( a_{1}^{T} x \leq b_{1}) \) or \( (a_{2}^{T} x \leq b_{2}) \)

can be converted into

\( a_{1}^{T} x \leq b_{1}+ yM \)

\( a_{2}^{T} x \leq b_{2}+ (1-y)M \)

where \( y \) is a 0-1 integer variable and \( M \) is a large positive constant. Depending on whether \( y \) is 0 or 1, one of the two constraints will be active while the other will be inactive. Conversely, any 0-1 MILP can be thought of as a disjunctive linear programming problem with disjunctive constraints \( y_{i}=0 \) or \( y_{i}=1 \) for each 0-1 variable \( y_{i} \).

Although the "Big-M" approach is widely used in MILP, branch and bound algorithms often have trouble with the resulting 0-1 problems because the resulting LP relaxations provide weak bounds on the optimal objective value. Balas developed an alternative cutting plane approach that strengthens the LP relaxations of 0-1 MILP's by adding "disjunctive cuts." These cuts are linear inequalities that are valid for the integer solutions to the problem but cut off unneeded points that would otherwise be feasbile in the LP relaxation of the MILP. This tightens the formulation of the MILP so that it can be more efficiently solved. Disjunctive cuts and the related lift-and-project cuts developed by Balas and his coauthors are now widely used by software packages for MILP.

In Disjunctive Programming, Balas provides a very thorough and authoritative account of the theory of disjunctive programming and its applications to 0-1 MILP. This book will be of interest to graduate students and researchers working in integer programming.

Brian Borchers is a professor of mathematics at New Mexico Tech and the editor of MAA Reviews.

See the table of contents in the publisher's webpage.

Tags:

Integer Programming