(463c) An Algorithm for Preprocessing and Tightening Generalized Disjunctive Programming Models Through the Application of Basic Steps

Francisco Trespalacios and Ignacio Grossmann

Many optimization problems are represented with algebraic equations, using continuous and discrete variables, giving rise to Mixed (Linear or Nonlinear) Integer 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 can be regarded as an extension of well-known disjunctive programming paradigm developed by Balas^[3]. A particular operation in disjunctive programming that helps to generate a tighter formulation of the problem, using the logic structure of disjunctions, is the so-called Basic Step^[4]. 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 propose an algorithmic approach to sequentially apply basic steps to linear and nonlinear convex GDP problems that will, at most double the number of continuous variables, and will potentially decrease the number of binary variables in the MILP/MINLP reformulation. There are three main stages that will allow this: (a) Feasibility check in individual disjunctions through the solution of continuous programs; (b) application of basic steps in specific disjunctions; (c) logic transformation after reducing the number of disjunctive terms into a GDP.

For the first stage we analyze the feasibility of the binary variables, which have a one to one correspondence with each of the disjunctive terms. Through a pre-solving analysis, we discard those binary variables that make the problem infeasible when taking a value of 1. In this way we reformulate 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.

For the second stage we start from the observation that the growth in continuous variables is mainly driven by the increase of the number of terms in the disjunctions as we apply basic steps. Additionally, the number of terms in a disjunction (after the application of a basic step) is defined by the multiplication of the number of terms in the two disjunctions to which we applied the basic step. For example, if we apply a basic step between two disjunctions with two terms each, we obtain a new single disjunction with four terms; if one has 4, and the other 3, the resulting disjunction will have 12 terms. In this stage we apply basic steps between two disjunctions with two terms in each, resulting in 4-term disjunctions. In this way the number of terms in the disjunctions of the problem is kept constant. This stage, in combination with the feasibility check, allows us to sequentially apply basic steps without increasing the number of disjunctions.

The third stage relies on the fact that there is a one to one correspondence with binary variables and the disjunctive terms in a GDP. When we eliminate some of the disjunctive terms of a GDP, through the feasibility check, this results into a new GDP problem with fewer disjunctive terms (even if a basic step is applied in an earlier stage). With this in mind, we can assign a new binary variable to the disjunctive terms in the new GDP, and relate them to the logic propositions as needed, and in that way reduce the number of binary variables.

These three stages can be applied iteratively for a finite number of times. This will then lead to a tighter GDP, with potentially fewer binary variables and limited growth in continuous variables and constraints that can be solved more efficiently. The resulting GDP problems can then be either reformulated as an MILP or MINLP using the hull relaxation, or else be solved through a cutting plane algorithm.

We illustrate the application of this 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