# Disjunctive inequalities

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Author: Camille Bilodeau

Stewards: Dajun Yue and Fengqui You

A disjunctive inequality is a type of constraint that exists in mixed integer linear programming (MILP) and mixed integer nonlinear programming (MINLP) problems. It involves constraining a solution space with multiple inequalities or sets of inequalities related by an OR statement. This "OR" statement must then be reformulated using one or more binary variables.

## Model Formulation

An example of a disjunctive inequality constraint is

$\begin{bmatrix} y \\ 0\le x_{1}\le 3 \\ 0\le x_{2}\le 4 \end{bmatrix}\or \begin{bmatrix} \neg y \\ 5\le x{1}\le 9\\ 4\le x{2}\le 6 \end{bmatrix}$
Solution space associated with example disjunctive inequality

In this example, y is a binary variable that determines which condition is enforced and x is a continuous variable. As shown in the graph, this set of inequalities results in two separate solution spaces representing the constraints associated with the two alternatives. This example shows a disjunctive inequality with only one alternative, but it is possible to create disjunctive inequalities with any number of alternatives. Thus the problem can be formulated as follows:

$\bigcup_{y\in Y} \begin{Bmatrix} A_{i} x\le b_{i} y_{i} | i = 1, ..., m \end{Bmatrix}$

where $A_{i} x\le b_{i} y_{i}$ is a system of inequalities associated with alternative i and where $y_{i}$ is the binary variable associated with choosing the optimal alternative.

## Disjunctive Inequality Solution Methods

Since disjunctive inequalities require MILP, they are more computationally difficult to solve than LP problems. A good way to approach MILP problems in general is to begin by relaxing the constraints on the problem. By solving a problem with relaxed constraints, a solution that is either more optimal or equally optimal to the true optimal solution can be found. Thus, the two main methods for solving disjunctive inequalities involve relaxing the problem’s constraints. These two methods are called the Big-M reformulation and the Convex Hull Reformulation.

### Big-M Reformulation

In order to redefine a problem as a Big-M reformulation, first binary variable(s) must be defined corresponding to each alternative case. For example if there are two alternative cases, there must be two different binary variables. Since only one of these cases will provide the constraints on the optimal solution, all of the binary variables must add up to 1. Thus for two alternative cases

$y_{1}+y_{2}=1$

$y_{1}, y_{2}\in \begin{Bmatrix}0,1\end{Bmatrix}$

Then an arbitrarily large constant, M, must be defined. Using M, each inequality can then be reformulated such that if it is not in the set of inequalities being used, it is null. This can be accomplished by subtracting M from the left side of any greater than or equal to inequalities or by adding M to the right side of any less than or equal to inequalities. Thus for two inequalities associated with two cases:

$-M(1-y_{1})+0\le x_{1}\le 3+M(1-y_{1})$

$-M(1-y_{1})+0\le x_{2}\le 4+M(1-y_{1})$

$-M(1-y_{2})+5\le x_{1}\le 9+M(1-y_{2})$

$-M(1-y_{2})+4\le x_{2}\le 6+M(1-y_{2})$

In this way, if $y_{1}= 1$ and $y_{2}= 0$, the first set of inequalities is enforced and the bounds of the second set of inequalities are dramatically expanding rendering them ineffective.

### Convex-Hull Reformulation

Redefining a problem as a Convex Hull Reformulation also involves defining binary variables associated with each case and setting their summation to 1. Then, new variables derived from the original variables are created for use in each case. For example:

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

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

These variables are then bound between zero and M (arbitrarily large constant) multiplied by the binary variable corresponding to that case:

$0\le x_{11}\le My_{1}$

$0\le x_{21}\le My_{1}$

$0\le x_{12}\le My_{2}$

$0\le x_{22}\le My_{2}$

Thus if $y_{2}= 0$, $x_{12}$ and $x_{22}$ will be constrained to 0 and $x_{1}$ and $x_{2}$ will be fully determined by $x_{11}$ and $x_{21}$. The original constraints will then be reformulated with each of the bounds multiplied by the corresponding binary variable and each continuous variable replaced by its appropriate component:

$0\le x_{11}\le 3y_{1}$

$0\le x_{21}\le 4y_{1}$

$5y_{2}\le x_{12}\le 9y_{2}$

$4y_{2}\le x_{22}\le 6y_{2}$

In this way the inequality associated with the active set of constraints determined by the binary variable will be valid. The other variables will be set to zero.

### Comparing Solution Methods

Both Convex-Hull and Big-M formulations are ways of reformulating a disjunctive inequality so it can be solved as an MILP or an MINLP. Both MILP and MINLP problem types typically look for a solution by relaxing the bounds of the problem. While Convex-Hull and Big-M formulations result in problems that represent identical solution spaces, their relaxed problems are not identical. In order to use the two reformulations, a value for M must be chosen. For illustrative purposes, take $M=7$. Plugging this into the Big-M reformulation yields

Big-M Formulation Solution Space: Relaxed Problem

$-7(1-y_{1})\le x_{1}\le 3+7(1-y_1)$

$-7(1-y_{1})\le x_{2}\le 4+7(1-y_1)$

$-7(1-y_{2})+5\le x_{1}\le 9+7(1-y_2)$

$-7(1-y_{2})+4\le x_{2}\le 6+7(1-y_2)$

In order to relax this problem, $y_{1}$ and $y_{2}$ converted to continuous variables such that $y_{1}, y_{2}\in \begin{bmatrix} 0,1 \end{bmatrix}$. As with any relaxation, this results in an expansion of the solution space as shown on the graph. Since the solution space is now larger, the solution to the relaxed LP provides an upper bound (for a maximization problem) for the problem. Note, however that the solution space resulting from the Big-M Formulation is larger than the minimum solution space for a relaxed, convex, linear programming problem.

Plugging the same value for M into the Convex Hull Formulation yields

$0\le x_{11}\le 7y_{1}$

$0\le x_{21}\le 7y_{1}$

$0\le x_{12}\le 7y_{2}$

$0\le x_{22}\le 7y_{2}$

$0\le x_{11}\le 3y_{1}$

$0\le x_{21}\le 4y_{1}$

$5y_{2}\le x_{12}\le 9y_{2}$

$4y_{2}\le x_{22}\le 6y_{2}$

Convex Hull Formulation Solution Space: Relaxed Problem

The problem can be relaxed in the same way, by converting $y_{1}$ and $y_{2}$ into continuous variables such that $y_{1}, y_{2}\in \begin{bmatrix} 0,1 \end{bmatrix}$. This formulation results in a different, smaller solution space as shown in the graph. This solution space is referred to as the convex hull of the original non-convex problem. A convex hull is defined as the smallest set of points that include the full solution space of the original problem and is convex. As the name suggests, the relaxation of the Convex Hull Formulation is necessarily the convex hull. As a consequence, the Big-M Formulation will always have a relaxation solution space that is larger than or equal to that of the Convex Hull Formulation.

This has significant implications computationally. Since the relaxation step is intended to identify an upper bound for the MILP solution (maximization), and since the Convex Hull Formulation has a necessarily smaller solution space, the relaxation of the Convex Hull Formulation will have a lower upper bound. This results in fewer iterations required to solve disjunctive inequality problems formulated using Convex Hull, which, in turn, reduces the computation time. While this effect may be less pronounced in simpler problems, it can greatly improve the ease and feasibility of more complex problems. Despite this, the Big-M formulation is simpler, requiring fewer inequalities and is therefore preferable for solving problems where computational time is not a concern.

## Illustrative Example: Locating a Warehouse

Disjunctive inequalities can be used to describe the solution space of any decision-making problem that involves first choosing between binary routes and then maximizing within that choice. A good example of this is a problem that involves m possible locations for warehouse and n customers who would like to purchase items from those warehouses. This type of problem is of interest to shipping companies like UPS or Amazon. Construction of each warehouse has a fixed cost and a capacity, and each customer has a demand. Goods must be shipped from warehouses on trucks, which also have a fixed capacity. The objective of this problem is to determine which warehouses to install to supply the product while minimizing the distribution costs. Thus the decision to construct a warehouse at location i for customer j can be described by the following disjunctive inequality:

$\begin{bmatrix}\sum_{j} x_{ij}\le C_{i}\\ 0\le x_{ij}\le K_{ij} w_{ij}, for all j\\ z_{i}\ge f_{i} + \sum_{j} c_{ij} w_{ij} \end{bmatrix} \or \begin{bmatrix} x_{ij}=0, for all j\\ z_{i}\ge 0 \end{bmatrix}$

$x_{ij}=$ number of goods shipped from warehouse i to customer j

$C_{i}=$ capacity of warehouse i

$K_{ij}=$ capacity of truck shipping from warehouse i to customer j

$w_{ij}=$ number of trucks used to transport goods from warehouse i to customer j

$z_{i}=$ total cost of warehouse i

$f_{i}=$ fixed cost of warehouse i

$c_{ij}=$ fixed cost associated with each truck shipping from warehouse i to customer j

The alternative on the left refers to the case where a warehouse is built on location i and the alternative on the right refers to the case where that warehouse is not built. Thus by solving this problem minimizing distribution costs or by introducing a similar constraint to a cost maximization problem, this constraint can determine the optimal layout of warehouses. In order to solve this problem, it can be reformulated into the Convex Hull Reformulation. This would result in the following set of conditions:

$x_{ij} = x_{ij1} + x_{ij2}$

$z_{i} = z_{i1} + z_{i2}$

$0\le x_{ij1}\le y_{1} M$

$0\le x_{ij2}\le y_{2} M$

$0\le z_{i1}\le y_{1} M$

$0\le z_{i2}\le y_{2} M$

$\sum_{j} x_{ij1}\le C_{i}$

$0\le x_{ij1}\le K_{ij} w_{ij}$

$z_{i1}\ge f_{i} + \sum_{j} c_{ij} w_{ij}$

$x_{ij2}=0$

$z_{i2}\ge 0$

Thus, by introducing this formulation to an optimization solver, the optimal layout of warehouses can be found.

## Applications

In addition to optimizing layouts for product distribution networks, disjunctive inequalities can be used to model a number of other scenarios. In general, disjunctive inequalities are useful for problems that are formulated such that there are multiple discrete alternatives that can be chosen from where each alternative can also be optimized within itself.

### Example Applicaiton: Factory Production Planning

A good example of a problem that uses disjunctive inequalities is determining how much of a product a factory should produce and what methods it should use in order to maximize profits. Consider a factory that can produce product C from product B using either of two processes. Process 1 has an efficiency of $E_{1}$, a fixed cost of $FC_{1}$, and a variable cost of $VC_{1}$ per kilogram C produced. Similarly, process 2 has an efficiency of $E_{2}$, a fixed cost of $FC_{2}$, and a variable cost of $VC_{2}$ per kilogram C produced. A kilogram of B costs $P_{B}$ and a kilogram of C can be sold for $P_{C}$. The problem could be formulated as follows:

$max profit = C P_{C} - B P_{B} - Cost$

$\begin{bmatrix} y_{1}\\ C = E_{1} B\\ Cost= FC_{1} + VC_{1} C \end{bmatrix} \or \begin{bmatrix} y_{2}\\ C = E_{2} B\\ Cost = FC_{2} + VC_{2} C \end{bmatrix}$

Note that while this problem is a significantly oversimplified problem compared to a realistic scenario, it can still help to inform decision making.

## Conclusion

Disjunctive inequalities can be a powerful tool for decision making in a variety of fields. They are capable of breaking down logical decisions that involve linear and nonlinear constraints. It is important to note that the two methods of reformulation, Convex Hull and Big-M, are necessary for solving problems with disjunctive inequalities. It is also important to note that while both of these reformulations have the same logical constraints, their relaxed problem is different. Thus the computational difficulty associating with solving these two reformulations can be different.

## References

1. Belotti, Pietro, Liberti, Leo, Lodi, Andrea, Nannicini, Giacomo, Tramontani, Andrea. "Disjunctive Inequalities: Applications and Extensions." pp. 1-11.