# Disjunctive inequalities

Authors: Derek Moore, Grant Logan, Matthew Dinh, Daniel Ladron (SYSEN 5800/CHEME 6800 Fall 2021)

## Introduction

Disjunctive inequalities are a form of disjunctive constraints that can be applied to linear programming. Disjunctive constraints are applied in all disjunctive programming, which just refers to the use of logical constraints in linear inequalities, which include “Or", ”And", or "Complement of" statements.[1] In order to solve a disjunctive, the constraints have to be converted into mixed-integer programming (MIP) or mixed-inter linear programming (MILP) constraints, which is called disjunction. Disjunction involves the implementation of a binary variable to create a new set of constraints that can be solved easily. Two common methods for disjunction are the Big-M Reformulation and the Convex-Hull Reformulation.[2]

## Method

### General

When given a set of inequalities, such as ${\displaystyle f_{1}(x)\leq 0\ \ \And \ \ f_{2}(x)\leq 0}$, the disjunctive form is given by:  ${\displaystyle {\begin{bmatrix}y\\f_{1}(x)\leq 0\end{bmatrix}}\lor {\begin{bmatrix}\neg y\\f_{2}(x)\leq 0\end{bmatrix}}.}$[1] In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as ${\displaystyle M_{1}}$ and ${\displaystyle M_{2}}$, and a binary variable y for each inequality. This is shown below by ${\displaystyle M}$, ${\displaystyle y_{1}}$, and ${\displaystyle y_{2}}$:

${\displaystyle f_{1}(x)\leq M\ast (1-y_{1})}$

${\displaystyle f_{2}(x)\leq M\ast (1-y_{2})}$

To set the binary variable to be mutually exclusive, the sum of the variables is set to 1 and the range is set to {0,1}.

${\displaystyle \sum _{i}y_{i}=1}$

${\displaystyle y_{i}\ \epsilon \ \{0,1\}\ \ }$

### Big-M Reformulation[1][2]

For the Big-M reformulation, a sufficiently large number, ${\displaystyle M}$, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “${\displaystyle M*(1-y)}$” to the upper bound and lower bound constraints, respectively, with its respective binary variable. While choosing a large M value allows for isolation, the large value also yields poor relaxation of the model space.[3]

For example, given a solution space ${\displaystyle {\begin{bmatrix}y\\2\leq x_{1}\leq 6\\5\leq x_{2}\leq 9\end{bmatrix}}\lor {\begin{bmatrix}\neg y\\8\leq x_{1}\leq 11\\10\leq x_{2}\leq 15\ \end{bmatrix}}}$(shown graphically in Figure 1), to determine which of the solutions is optimal, the problem must be formulated such that one set of constraints is chosen. Using the Big-M Reformulation, the following MILP set would be obtained:

${\displaystyle y}$ Formulation

${\displaystyle 2-M*(1-y_{1})\leq x1\leq 6+M*(1-y_{1})}$

${\displaystyle 5-M*(1-y_{1})\leq x2\leq 9+M*(1-y_{1})}$

${\displaystyle \neg y}$ Formulation

${\displaystyle 8-M*(1-y_{2})\leq x1\leq 11+M*(1-y_{2})}$

${\displaystyle 10-M*(1-y_{2})\leq x2\leq 15+M*(1-y_{2})}$

### Convex-Hull Reformulation[1][2]

Similar to the Big-M reformulation, the convex-hull reformulation uses a binary variable, y, to constrain the set of inequalities. The first step in converting the problem into a solvable MILP is breaking all variables into a set of variables, such as (${\displaystyle x_{1}}$${\displaystyle x_{11}}$ + ${\displaystyle x_{12}}$). By adding these addition variables, it is possible to isolate what set of parameters provide for the optimal solution of the problem. Then, similar to the Big-M reformulation, a sufficiently large variable, M, is used to nullify the non-optimal variable set, such as ${\displaystyle x_{11}}$ and ${\displaystyle x_{12}}$. For the problem show in Figure 1, the following variable constraints would be formulated:

${\displaystyle y}$ Formulation

${\displaystyle 0\leq x_{11}\leq M*y_{1}}$

${\displaystyle 0\leq x_{21}\leq M*y_{1}}$

${\displaystyle \neg y}$ Formulation

${\displaystyle 0\leq x_{12}\leq M*y_{2}}$

${\displaystyle 0\leq x_{22}\leq M*y_{2}}$

Formulation of the numerical constraints would then be implemented:

${\displaystyle y}$ Formulation

${\displaystyle 2\ast y_{1}\leq \ x_{11}\ \leq 6\ast y_{1}}$

${\displaystyle 5\ast y_{1}\leq \ x_{21}\ \leq 9\ast y_{1}}$

${\displaystyle \neg y}$ Formulation

${\displaystyle 8\ast y_{2}\leq \ x_{12}\ \leq 11\ast y_{2}}$

${\displaystyle 10\ast y_{2}\leq \ x_{22}\ \leq 15\ast y_{2}}$

With the Convex-Hull transformation, the additional constraints confine the problem, such that a tighter (convex) solution space is examined compared to Big-M Formulation.[3]

## Numerical Example

Given the following Disjunctive Inequality form below, reformulate the following problem using Convex Hull method and Big-M:

${\displaystyle {\begin{bmatrix}y\\0\leq x_{1}\leq 13\\0\leq x_{2}\leq 4\\1\leq x_{2}+x_{3}\leq 7\end{bmatrix}}\lor {\begin{bmatrix}\neg y\\2\leq x_{1}\leq 10\\4\leq x_{2}\leq 6\ \\2\leq x_{2}+x_{3}\leq 8\end{bmatrix}}}$

### Convex Hull Method

We begin by setting introducing a binary variable y as a summation to 1:

${\displaystyle y_{1}+y_{2}=1,y_{1},y_{2}\epsilon }$ {0,1}

Next we begin by grouping our ${\displaystyle x_{ij}}$ values.

${\displaystyle x_{1}=x_{11}+x_{12}}$

${\displaystyle x_{2}=x_{21}+x_{22}}$

${\displaystyle x_{3}=x_{31}+x_{32}}$

Next nullify the non-optimal variable sets with another binary variable large ${\displaystyle M}$ variable to:

${\displaystyle 0\leq x_{11}\leq y_{1}*M}$

${\displaystyle 0\leq x_{21}\leq y_{1}*M}$

${\displaystyle 0\leq x_{31}\leq y_{1}*M}$

${\displaystyle 0\leq x_{12}\leq y_{2}*M}$

${\displaystyle 0\leq x_{22}\leq y_{2}*M}$

${\displaystyle 0\leq x_{32}\leq y_{2}*M}$

Keep in mind the ${\displaystyle M}$ must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

Finally the below constraints are reformulated from the original constraints, reformulated with ${\displaystyle y}$ included to pin ${\displaystyle x_{ij}=0}$ when ${\displaystyle y_{j}=0}$, subject to the original constraint when ${\displaystyle y_{j}=1}$.

${\displaystyle 0\leq x_{11}\leq y_{1}*13}$

${\displaystyle 0\leq x_{21}\leq y_{1}*4}$

${\displaystyle 1*y_{1}\leq x_{21}+x_{31}\leq y_{1}*7}$

${\displaystyle 2*y_{2}\leq x_{12}\leq y_{2}*10}$

${\displaystyle 4*y_{2}\leq x_{22}\leq y_{2}*6}$

${\displaystyle 2*y_{2}\leq x_{22}+x_{32}\leq y_{2}*8}$

The reformulated constraint set is thus all of these constraints, making the problem a MIP.

### Big-M Method

We now present the same constraint set reformulated by the Big-M method. We can begin by setting 2 binary variables ${\displaystyle y_{1}}$ and ${\displaystyle y_{2}}$ summing to 1.

${\displaystyle y_{1}+y_{2}=1,y_{1},y_{2}\epsilon }$ {0,1}

Next, we add the binary variable ${\displaystyle M}$ as it is a arbitrarily large constant which is used to reformulate the inequality. Each inequality is formed in a single step by adding or subtracting ${\displaystyle M*(1-y_{i})}$ depending on if the inequality is greater than or equal to, or less than or equal to.

${\displaystyle -M*(1-y_{1})+0\leq x_{1}\leq 13+M(1-y_{1})}$

${\displaystyle -M*(1-y_{1})+0\leq x_{2}\leq 4+M(1-y_{1})}$

${\displaystyle -M*(1-y_{1})+1\leq x_{2}+x_{3}\leq 7+M(1-y_{1})}$

${\displaystyle -M*(1-y_{2})+2\leq x_{1}\leq 10+M(1-y_{2})}$

${\displaystyle -M*(1-y_{2})+4\leq x_{2}\leq 6+M(1-y_{2})}$

${\displaystyle -M*(1-y_{2})+2\leq x_{2}+x_{3}\leq 8+M(1-y_{2})}$

In this way, if ${\displaystyle y_{1}=1}$ and ${\displaystyle y_{2}=0}$ the first set of inequalities is enforced and the second set of inequalities are dramatically expanded, effectively keeping them from constraining the problem, given that ${\displaystyle M}$ is large enough.

## Applications

Disjunctive inequality programming can be used to solve real world problems in various sectors. Integer programming formulations utilizing a binary decision variable on which multiple constraints depend can be reformulated into disjunctive inequality formulations.

### Strip Packing Problem

The Strip Packing Problem is a well-known problem in which two dimensional rectangles, or strips, are aligned in a two dimensional grid, subject to the constraints that the strips do not overlap. One method of formulating this problem is to describe the non-overlapping constraints as a set of four statements: for an existing rectangle ${\displaystyle A}$, a new rectangle ${\displaystyle B}$ must be above, below, to the left, or to the right of rectangle ${\displaystyle A}$. Each situation represents a unique inequality constraint; for example, if ${\displaystyle B}$ is above ${\displaystyle A}$, then it must hold that the lower border of ${\displaystyle B}$ is at a greater value than the lower border of ${\displaystyle A}$ plus the height of ${\displaystyle A}$. This can be extended to remove symmetries and improve efficiency of the solutions as well[4]. This can also be extended into three dimensions, for applications such as loading a cargo ship.

### Process Scheduling

Disjunctive inequalities are invaluable for decisions within process engineering when multiple setups, reactors, or processes are possible. In process scheduling, machine and shop floor operations are scheduled in such a way to maximize production of a final product, minimize downtime, or maximize profit. Many of the decisions underlying these operations are binary: whether or not to run a machine/operation at a given time. If a machine/operation is run, constraints are required to define costs (CAPEX and OPEX), profits, thermodynamic constraints, and resources (including mass and energy balances) associated with the running machine/operation. If a machine/operation is not run, a different set of constraints is required to define idle costs and resources. This can be formulated into a disjunctive inequality formulation and solved using the described methods. The disjunctive inequality takes the form:

${\displaystyle MinZ=f(x)+\textstyle \sum _{k\epsilon K}c_{k}\displaystyle }$

${\displaystyle s.t.g(x)\leq 0}$

${\displaystyle {\underset {i\epsilon D_{i}}{\lor }}{\begin{bmatrix}Y_{ki}\\r_{ki}(x)\leq 0\\c_{k}=l_{ki}\end{bmatrix}}k\epsilon K}$

${\displaystyle \veebar _{i\epsilon D_{i}}Y_{ki}}$

In this general formulation, ${\displaystyle c_{k}}$ represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above [5]. Some specific applications include distillation columns, pharmaceutical purification plants, and wastewater treatment plants.

Figure 2 shows a special case of process scheduling, a wastewater network that removes pollutants from its mixture. The task is to figure out the total cost to discharge the pollution.[6] This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:[6]

${\displaystyle MinZ=\textstyle \sum _{k\epsilon PU}CP_{k}\displaystyle }$

${\displaystyle f_{k}^{j}=\textstyle \sum _{i\epsilon M_{k}}f_{i}^{j}\displaystyle }$ ${\displaystyle \forall jk\in MU}$

${\displaystyle \textstyle \sum _{i\epsilon S_{k}}f_{i}^{j}\displaystyle =f_{k}^{j}}$ ${\displaystyle \forall jk\in SU}$

${\displaystyle \textstyle \sum _{i\epsilon S_{k}}\zeta _{i}^{j}\displaystyle =1}$ ${\displaystyle k\in SU}$

${\displaystyle f_{k}^{j}=\textstyle \zeta _{i}^{k}f_{k}^{j}\forall _{j}\displaystyle }$ ${\displaystyle i\in S_{k}}$ ${\displaystyle k\in SU}$

${\displaystyle {\underset {h\epsilon D_{k}}{\lor }}{\begin{bmatrix}y\\f_{i}^{j}=\mathrm {B} _{i}^{jh},i\epsilon OPU_{k},i^{i}\epsilon IPU_{k},\forall _{j}\\F_{k}=\sum _{j}f_{i}^{j},i\epsilon OPU_{k}\\CP_{k}=\partial _{ik}F_{k}\end{bmatrix}}k\epsilon PU}$

${\displaystyle 0\leq \zeta _{i}^{k}\leq 1}$ ${\displaystyle \forall j,k}$

${\displaystyle 0\leq f_{i}^{j},f_{k}^{j}}$ ${\displaystyle \forall i,j,k}$

${\displaystyle 0\leq CP_{k}}$ ${\displaystyle \forall k}$

${\displaystyle YP_{k}^{h}\in }$ {True, False} ${\displaystyle \forall h\in D_{k}\forall k\in PU}$

## Conclusion

As shown, disjunctive inequalities can be used to formulate various different types of mixed-integer program linear and nonlinear programs where binary decisions determine constraint sets. Two methods that are used to reformulate the problem are Convex Hull and Big-M reformulations. It could be shown that to obtain the convex hull of a 0 or 1 mixed-integer program, it suffices to take the convex hull of each 0 or 1 variable at a time [3]. Implementing the Big-M method generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method, providing more efficient computational solutions. Disjunctive inequalities can also be used to improve the performance of any general purpose Branch-and-Cut algorithm as shown on the research from Balas and Bonami [7]. Many of the real world problems that can be solved through disjunctive inequalities involve process optimization where various binary decisions have to be made to optimize the solution. Examples of real world problems illustrated here include cargo packing and processing plants such as wastewater treatment plants. In conclusion, formulating these types of problems with disjunctive inequalities allows for a simple representation and conversion to MILP/MILP, solvable with standard MILP/MINLP solution algorithms.

## References

1. E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.
2. Pedro M. Castro and Ignacio E. Grossmann. 'Generalized Disjunctive Programming as a Systematic Modeling Framework to Derive Scheduling Formulations." 2012 51 (16), 5781-5792 DOI: 10.1021/ie2030486
3. You, Fengqi. (2021). "Mixed-Integer Linear Programming."
4. Trespalacios, Francisco, and Ignacio E. Grossmann. "Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem." Annals of Operations Research 258, no. 2 (2017): 747-759.
5. Grossmann, Ignacio E., and Francisco Trespalacios. "Systematic modeling of discrete‐continuous optimization models through generalized disjunctive programming." AIChE Journal 59, no. 9 (2013): 3276-3295.
6. Grossmann, Ignacio E., and Juan P. Ruiz. Generalized Disjunctive Programming: A framework for formulation and alternative algorithms for MINLP optimization, Mixed Integer Nonlinear Programming, Springer New York, 2012.
7. E. Balas, P. Bonami. "Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Prog. Comp. 1", 165–199 (2009)