(340c) A Cutting Plane Algorithm for Convex Generalized Disjunctive Programming Models

Many optimization problems are represented with algebraic equations, using continuous and discrete variables, giving rise to Mixed Integer (Linear or Nonlinear) Programs (MILP/ MINLP). An alternative way to represent this type of problems is Generalized Disjunctive Programming (GDP) proposed by Raman and Grossmann^[2]  that involves not only algebraic equations, but also disjunctions and logic propositions^[1]. This higher level representation, which is of special importance in engineering, allows us to exploit the logic structure of the problem to obtain better formulations.

GDP problems are normally reformulated as MILP/MINLP models to exploit the developments of these types of solvers. There are two classic reformulations: the Big-M (BM) and the hull-reformulation (HR). The former yields a smaller MILP/MINLP while the later a tighter one. The (HR) reformulation can be further strengthened, by using the concept of basic step from disjunctive programing^[3][4].

A basic step is defined as the intersection of two disjunctions. The basic steps can be applied sequentially to generate a hierarchy of relaxations, where the limiting case is given by the convex hull of the original GDP problem. The application of basic steps has proven to improve the tightness in linear GDP formulations as shown by Sawaya and Grossmann^[5], and in general convex GDP formulations as shown by Ruiz and Grossmann^[6]. The drawback in the application of this operation is the exponential growth of continuous variables and number of constraints (although the number of binary variables can be kept constant).   

In this work we seek to exploit the advantages of having small but weak formulations (BM) and strong but larger formulations (HR after the application of some basic steps). In order to do this, we propose a cutting plane algorithm for linear and nonlinear convex GDP problems. The algorithm first uses a pre-solve strategy to improve GDP formulations. Next, it iteratively derives valid inequalities (or cutting planes) for the MILP/MINLP reformulations. Once the cuts are do not improve the tightness of the formulation, the final MILP/MINLP is generated by using the (BM) of the GDP and including all the generated cuts. This MILP/MINLP is then solved using traditional methods.

For the pre-solve we analyze the feasibility of the binary variables, which have a one to one correspondence with each of the disjunctive terms. Through the solution of some LP/NLPs we discard those binary variables that make the problem infeasible when taking a value of 1. In this way we formulate the GDP excluding the disjunctive terms that were proven to be infeasible for a corresponding “True” value. Through this first stage we can rigorously reduce the size of the GDP problem. This pre-solve strategy also provides a new lower bound for the GDP, and a value that will characterize each disjunction.

The idea of the cutting planes method is to solve the continuous relaxation of the (BM) of the convex GDP, and use the strong formulation of the (HR) after basic steps to derive cutting planes. The cutting planes are determined by solving a separation problem (LP or NLP), in which the feasible solution corresponds to the continuous relaxation of the (HR) formulation after a sequence of basic steps. A similar idea for linear GDP and without using basic steps (i.e. using only (HR) and (BM)) was proposed by Sawaya and Grossmann^[5].

The algorithm selects to which disjunctions basic steps are applied. The selection of intersection of disjunctions is done through a combination of theoretical results^[4][6] and heuristic rules. The algorithm stops deriving cutting planes when the improvement of the value of the objective function of the separation problem lies within a specified tolerance.

We illustrate the application of this cutting plane algorithm with several linear and convex GDP examples, including strip packing, reactor selection and layout problems. The results show the improvement in their relaxed solution, reduction in the number of binary variables, and relatively small growth in number of continuous variables and constraints.

References:

[1] Williams H.P., “Model Building in Mathematical Programming”, Wiley, 1985.

[2] Raman R. and Grossmann I.E., “Modelling and Computational Techniques for Logic-Based Integer Programming”, Computers and Chemical Engineering, 18, 563, 1994.

[3] Balas E., “Disjunctive Programming: Properties of the Convex Hull of Feasible Points”, MSRR #348, Carnegie Mellon University, Pittsburgh, PA, July 1974.

[4] Balas E., “Disjunctive Programming and a Hierarchy of Relaxations for Discrete Continuous Optimization Problems”, SIAM J. Alg. Disc. Meth., Vol. 6, No. 3, 1985.

[5] Nicolas Sawaya, Ignacio Grossmann, “Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming”, Carnegie Mellon University, Department of Chemical Engineering, Pittsburgh, PA, U.S.A, 15201.

[6] Juan P. Ruiz, Ignacio E. Grossmann, “A hierarchy of relaxations for nonlinear convex generalized disjunctive programming”, Carnegie Mellon University, Department of Chemical Engineering, Pittsburgh, PA, U.S.A, 15201