Cornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]

Disjunctive inequalities

2021-12-15T23:57:59Z

Dl976:

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>

== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>\sum_i y_i =1
</math>

<math>y_i \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''<math>y</math> Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''<math>\neg y</math> Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''<math>y</math> Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''<math>\neg y</math> Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented:

'''<math>y</math> Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''<math>\neg y</math> Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Numerical Example==
===Convex Hull Method===
Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

<math>\begin{bmatrix} y \\ 0\le x_1 \le3 \\ 0\le x_2 \le4 \end{bmatrix} \lor

\begin{bmatrix} \neg y \\ 5\le x_1 \le9 \\ 4\le x_2 \le6\ \end{bmatrix}

</math>

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

<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Next we begin by grouping our <math>x_{ij}</math> values.

<math> x_1 = x_{11} + x_{12}</math>

<math> x_2 = x_{21} + x_{22}</math>

Next nullify the non-optimal variable sets with another binary variable large <math>M_i</math> variable to:
[[File:Convex hull relax.jpg|thumb| Figure 2: Graph showing LP Relaxation of convex hull reformulation in section "Numerical Example"]]
<math> 0\leq x_{11}\leq y_{1}*M_1 </math>

<math> 0\leq x_{21}\leq y_{1}*M_2 </math>

<math> 0\leq x_{12}\leq y_{2}*M_3 </math>

<math> 0\leq x_{22}\leq y_{2}*M_4 </math>

If <math>y_2 = 0, x_{12}</math> & <math>x_{22}</math> will be constrained to 0 and <math>x_1</math> & <math>x_2</math> will be fully determined by <math>x_{12}</math> & <math>x_{21}</math>.

Next we must include our binary variable <math>M_i</math> values in order to render the inequality redundant. Keep in mind the <math>M_i</math> must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

<math> 0\leq x_{11}\leq y_{1}*3 </math>

<math> 0\leq x_{21}\leq y_{1}*4 </math>

<math> 5*y_{2}\leq x_{12}\leq y_{2}*9 </math>

<math> 4*y_{2}\leq x_{22}\leq y_{2}*6 </math>

The graphing result provided on figure 2 shows not only a feasible spacing but also shows the LP relaxation of the convex hull. In result, the inequality determined by the binary variables <math>M_i</math> & <math>y_i</math> will be valid while the other variables will be set to Zero.

==Applications==

[[File:Water.PNG|thumb|Figure 3: Wastewater system ]]
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 <math>A</math>, a new rectangle <math>B</math> must be above, below, to the left, or to the right of rectangle <math>A</math>. Each situation represents a unique inequality constraint; for example, if <math>B</math> is above <math>A</math>, then it must hold that the lower border of <math>B</math> is at a greater value than the lower border of <math>A</math> plus the height of <math>A</math>. This can be extended to remove symmetries and improve efficiency of the solutions as well<ref name=":7">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.</ref>. 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:

<math>Min Z = f(x) + \textstyle \sum_{k\epsilon K} c_k\displaystyle</math>

<math>s.t. g(x) \leq 0</math>

<math>\underset{i\epsilon D_i}{\lor} \begin{bmatrix} Y_{ki} \\ r_{ki} (x) \leq 0 \\ c_k = l_{ki} \end{bmatrix} k \epsilon K
</math>

<math> \veebar_{i\epsilon D_i} Y_{ki} </math>

In this general formulation, <math>c_k</math> represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above <ref name=":8">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.</ref>. 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.<ref name=":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. </ref> This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==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 <ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>. 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 <ref name=":5">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) </ref>. 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==

<references />

Disjunctive inequalities

2021-12-15T23:43:55Z

Dl976:

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>

== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>\sum_i y_i =1
</math>

<math>y_i \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''<math>y</math> Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''<math>\neg y</math> Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''<math>y</math> Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''<math>\neg y</math> Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented:

'''<math>y</math> Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''<math>\neg y</math> Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Numerical Example==
===Convex Hull Method===
Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

<math>\begin{bmatrix} y \\ 0\le x_1 \le3 \\ 0\le x_2 \le4 \end{bmatrix} \lor

\begin{bmatrix} \neg y \\ 5\le x_1 \le9 \\ 4\le x_2 \le6\ \end{bmatrix}

</math>

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

<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Next we begin by grouping our <math>x_{ij}</math> values.

<math> x_1 = x_{11} + x_{12}</math>

<math> x_2 = x_{21} + x_{22}</math>

Next nullify the non-optimal variable sets with another binary variable large <math>M_i</math> variable to:
[[File:Convex hull relax.jpg|thumb| Figure 2: Graph showing LP Relaxation of convex hull reformulation in section "Numerical Example"]]
<math> 0\leq x_{11}\leq y_{1}*M_1 </math>

<math> 0\leq x_{21}\leq y_{1}*M_2 </math>

<math> 0\leq x_{12}\leq y_{2}*M_3 </math>

<math> 0\leq x_{22}\leq y_{2}*M_4 </math>

If <math>y_2 = 0, x_{12}</math> & <math>x_{22}</math> will be constrained to 0 and <math>x_1</math> & <math>x_2</math> will be fully determined by <math>x_{12}</math> & <math>x_{21}</math>.

Next we must include our binary variable <math>M_i</math> values in order to render the inequality redundant. Keep in mind the <math>M_i</math> must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

<math> 0\leq x_{11}\leq y_{1}*3 </math>

<math> 0\leq x_{21}\leq y_{1}*4 </math>

<math> 5\leq x_{12}\leq y_{2}*9 </math>

<math> 4\leq x_{22}\leq y_{2}*6 </math>

The graphing result provided on figure 2 shows not only a feasible spacing but also shows the LP relaxation of the convex hull. In result, the inequality determined by the binary variables <math>M_i</math> & <math>y_i</math> will be valid while the other variables will be set to Zero.

==Applications==

[[File:Water.PNG|thumb|Figure 3: Wastewater system ]]
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 <math>A</math>, a new rectangle <math>B</math> must be above, below, to the left, or to the right of rectangle <math>A</math>. Each situation represents a unique inequality constraint; for example, if <math>B</math> is above <math>A</math>, then it must hold that the lower border of <math>B</math> is at a greater value than the lower border of <math>A</math> plus the height of <math>A</math>. This can be extended to remove symmetries and improve efficiency of the solutions as well<ref name=":7">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.</ref>. 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:

<math>Min Z = f(x) + \textstyle \sum_{k\epsilon K} c_k\displaystyle</math>

<math>s.t. g(x) \leq 0</math>

<math>\underset{i\epsilon D_i}{\lor} \begin{bmatrix} Y_{ki} \\ r_{ki} (x) \leq 0 \\ c_k = l_{ki} \end{bmatrix} k \epsilon K
</math>

<math> \veebar_{i\epsilon D_i} Y_{ki} </math>

In this general formulation, <math>c_k</math> represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above <ref name=":8">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.</ref>. 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.<ref name=":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. </ref> This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==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 <ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>. 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 <ref name=":5">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) </ref>. 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==

<references />

Disjunctive inequalities

2021-12-15T23:40:18Z

Dl976:

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>

== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>\sum_i y_i =1
</math>

<math>y_i \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''<math>y</math> Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''<math>\neg y</math> Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''<math>y</math> Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''<math>\neg y</math> Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented:

'''<math>y</math> Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''<math>\neg y</math> Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Numerical Example==
===Convex Hull Method===
Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

<math>\begin{bmatrix} y \\ 0\le x_1 \le3 \\ 0\le x_2 \le4 \end{bmatrix} \lor

\begin{bmatrix} \neg y \\ 5\le x_1 \le9 \\ 4\le x_2 \le6\ \end{bmatrix}

</math>

'''Using Convex Hull method:'''

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

<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Next we begin by grouping our <math>x_{ij}</math> values.

<math> x_1 = x_{11} + x_{12}</math>

<math> x_2 = x_{21} + x_{22}</math>

Next nullify the non-optimal variable sets with another binary variable large <math>M_i</math> variable to:
[[File:Convex hull relax.jpg|thumb| Figure 2: Graph showing LP Relaxation of convex hull reformulation in section "Numerical Example"]]
<math> 0\leq x_{11}\leq y_{1}*M_1 </math>

<math> 0\leq x_{21}\leq y_{1}*M_2 </math>

<math> 0\leq x_{12}\leq y_{2}*M_3 </math>

<math> 0\leq x_{22}\leq y_{2}*M_4 </math>

If <math>y_2 = 0, x_{12}</math> & <math>x_{22}</math> will be constrained to 0 and <math>x_1</math> & <math>x_2</math> will be fully determined by <math>x_{12}</math> & <math>x_{21}</math>.

Next we must include our binary variable <math>M_i</math> values in order to render the inequality redundant. Keep in mind the <math>M_i</math> must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

<math> 0\leq x_{11}\leq y_{1}*3 </math>

<math> 0\leq x_{21}\leq y_{1}*4 </math>

<math> 5\leq x_{12}\leq y_{2}*9 </math>

<math> 4\leq x_{22}\leq y_{2}*6 </math>

The graphing result provided on figure 2 shows not only a feasible spacing but also shows the LP relaxation of the convex hull. In result, the inequality determined by the binary variables <math>M_i</math> & <math>y_i</math> will be valid while the other variables will be set to Zero.

==Applications==

[[File:Water.PNG|thumb|Figure 3: Wastewater system ]]
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 <math>A</math>, a new rectangle <math>B</math> must be above, below, to the left, or to the right of rectangle <math>A</math>. Each situation represents a unique inequality constraint; for example, if <math>B</math> is above <math>A</math>, then it must hold that the lower border of <math>B</math> is at a greater value than the lower border of <math>A</math> plus the height of <math>A</math>. This can be extended to remove symmetries and improve efficiency of the solutions as well<ref name=":7">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.</ref>. 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:

<math>Min Z = f(x) + \textstyle \sum_{k\epsilon K} c_k\displaystyle</math>

<math>s.t. g(x) \leq 0</math>

<math>\underset{i\epsilon D_i}{\lor} \begin{bmatrix} Y_{ki} \\ r_{ki} (x) \leq 0 \\ c_k = l_{ki} \end{bmatrix} k \epsilon K
</math>

<math> \veebar_{i\epsilon D_i} Y_{ki} </math>

In this general formulation, <math>c_k</math> represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above <ref name=":8">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.</ref>. 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.<ref name=":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. </ref> This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==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 <ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>. 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 <ref name=":5">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) </ref>. 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==

<references />

Disjunctive inequalities

2021-12-15T23:39:03Z

Dl976:

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>

== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>\sum_i y_i =1
</math>

<math>y_i \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''<math>y</math> Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''<math>\neg y</math> Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''<math>y</math> Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''<math>\neg y</math> Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented:

'''<math>y</math> Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''<math>\neg y</math> Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Numerical Example==
===Convex Hull Method===
Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

<math>\begin{bmatrix} y \\ 0\le x_1 \le3 \\ 0\le x_2 \le4 \end{bmatrix} \lor

\begin{bmatrix} \neg y \\ 5\le x_1 \le9 \\ 4\le x_2 \le6\ \end{bmatrix}

</math>

'''Using Convex Hull method:'''

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

<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Next we begin by grouping our <math>x_{ij}</math> values.

<math> x_1 = x_{11} + x_{12}</math>

<math> x_2 = x_{21} + x_{22}</math>

Next nullify the non-optimal variable sets with another binary variable large <math>M_i</math> variable to:
[[File:Convex hull relax.jpg|thumb| Figure 2: Graph showing LP Relaxation of convex hull reformulation in section "Numerical Example"]]
<math> 0\leq x_{11}\leq y_{1}*M_1 </math>

<math> 0\leq x_{21}\leq y_{1}*M_2 </math>

<math> 0\leq x_{12}\leq y_{2}*M_3 </math>

<math> 0\leq x_{22}\leq y_{2}*M_4 </math>

If <math>y_2 = 0, x_{12}</math> & <math>x_{22}</math> will be constrained to 0 and <math>x_1</math> & <math>x_2</math> will be fully determined by <math>x_{12}</math> & <math>x_{21}</math>.

Next we must include our binary variable <math>M_i</math> values in order to render the inequality redundant. Keep in mind the <math>M_i</math> must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

<math> 0\leq x_{11}\leq y_{1}*3 </math>

<math> 0\leq x_{21}\leq y_{1}*4 </math>

<math> 5\leq x_{12}\leq y_{2}*9 </math>

<math> 4\leq x_{22}\leq y_{2}*6 </math>

The graphing result provided on figure 2 shows not only a feasible spacing but also shows the LP relaxation of the convex hull. In result, the inequality determined by the binary variables <math>M_i</math> & <math>y_i</math> will be valid while the other variables will be set to Zero.

==Applications==

[[File:Water.PNG|thumb|Figure 3: Wastewater system ]]
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 <math>A</math>, a new rectangle <math>B</math> must be above, below, to the left, or to the right of rectangle <math>A</math>. Each situation represents a unique inequality constraint; for example, if <math>B</math> is above <math>A</math>, then it must hold that the lower border of <math>B</math> is at a greater value than the lower border of <math>A</math> plus the height of <math>A</math>. This can be extended to remove symmetries and improve efficiency of the solutions as well<ref name=":7">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.</ref>. 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:

<math>Min Z = f(x) + \textstyle \sum_{k\epsilon K} c_k\displaystyle</math>

<math>s.t. g(x) \leq 0</math>

<math>\underset{i\epsilon D_i}{\lor} \begin{bmatrix} Y_{ki} \\ r_{ki} (x) \leq 0 \\ c_k = l_{ki} \end{bmatrix} k \epsilon K
</math>

<math> \veebar_{i\epsilon D_i} Y_{ki} </math>

In this general formulation, <math>c_k</math> represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above <ref name=":8">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.</ref>. 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.<ref name=":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. </ref> This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==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 <ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>. 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 <ref name=":5">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) </ref>. 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==

<references />

Disjunctive inequalities

2021-12-15T23:10:51Z

Dl976: /* Introduction */

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>

== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>\sum_i y_i =1
</math>

<math>y_i \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''<math>y</math> Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''<math>\neg y</math> Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''<math>y</math> Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''<math>\neg y</math> Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented:

'''<math>y</math> Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''<math>\neg y</math> Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Numerical Example==

Given the following Disjunctive Inequality form below, reformulate the following problem using convex hull method:

<math>\begin{bmatrix} y \\ 0\le x_1 \le3 \\ 0\le x_2 \le4 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 5\le x_1 \le9 \\ 4\le x_2 \le6\ \end{bmatrix}

</math>

'''Using Covex Hull method:'''

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

<math>y_1 + y_2 = 1, y_1, y_2 \epsilon</math> {0,1}

Next we begin by grouping our <math>x_{ij}</math> values.

<math> x_1 = x_{11} + x_{12}</math>

<math> x_2 = x_{21} + x_{22}</math>

Now nullify the non-optimal variable sets with a another binary variable large M variable to:

<math> 0\leq x_{11}\leq y_{1}*M </math>

<math> 0\leq x_{21}\leq y_{1}*M </math>

<math> 0\leq x_{12}\leq y_{2}*M </math>

<math> 0\leq x_{22}\leq y_{2}*M </math>

If <math>y_2 = 0, x_{12}</math> & <math>x_{22}</math> will be constrained to 0 and <math>x_1</math> & <math>x_2</math> will be fully determined by <math>x_{12}</math> & <math>x_{21}</math>.

Now we must include our binary variable M values in order to render the inequality redundant. Keep in mind the <math>M_i</math> must be sufficiently large, too large of a value can yield to poor relaxation of the LP.

<math> 0\leq x_{11}\leq y_{1}*3 </math>

<math> 0\leq x_{21}\leq y_{1}*4 </math>

<math> 5\leq x_{12}\leq y_{2}*9 </math>

<math> 4\leq x_{22}\leq y_{2}*6 </math>

The graphing on provided shows not only a feasible spacing but also shows the LP relaxation of the convex hull. In result, the inequality determined by the binary variables M & y will be valid while the other variables will be set to Zero.

==Applications==

[[File:Water.PNG|thumb|Figure 2: Wastewater system ]]
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 <math>A</math>, a new rectangle <math>B</math> must be above, below, to the left, or to the right of rectangle <math>A</math>. Each situation represents a unique inequality constraint; for example, if <math>B</math> is above <math>A</math>, then it must hold that the lower border of <math>B</math> is at a greater value than the lower border of <math>A</math> plus the height of <math>A</math>. This can be extended to remove symmetries and improve efficiency of the solutions as well<ref name=":7">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.</ref>. 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:

<math>Min Z = f(x) + \textstyle \sum_{k\epsilon K} c_k\displaystyle</math>

<math>s.t. g(x) \leq 0</math>

<math>\underset{i\epsilon D_i}{\lor} \begin{bmatrix} Y_{ki} \\ r_{ki} (x) \leq 0 \\ c_k = l_{ki} \end{bmatrix} k \epsilon K
</math>

<math> \veebar_{i\epsilon D_i} Y_{ki} </math>

In this general formulation, <math>c_k</math> represents the cost of enforcing a term, continuous variables represent system parameters, and constraints represent thermodynamic and resource constraints as described above <ref name=":8">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.</ref>. 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.<ref name=":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. </ref> This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==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 <ref name=":1">You, Fengqi. (2021). "Mixed-Integer Linear Programming." </ref>. 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 <ref name=":5">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) </ref>. 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==

<references />

Disjunctive inequalities

2021-12-15T05:18:35Z

Dl976: /* Conclusion */

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>y_1 + y_2 =1
</math>

<math>y_1 , y_2 \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Examples==

===== Example 1: Locating a Farmer Market =====
An example of a disjunctive inequality that involves m possible locations for a Farmers Market and n customers who would like to purchase produce from those Farmers. This is convenient for customers who want to purchase produces from local farmers. There is a fix cost to supplying each farmers market with produce from local farmers as well as a capacity. There are also demands from customers on what produces they want. This example of disjunctive inequality is to determine why a farmers market is needed at location i for customers j.

<math>\begin{bmatrix} \sum_j x_{ij} \leq L_i \\ 0 \leq x_{ij} \leq P_{ij} , \forall j \\ G_i \leq f_i + \sum_j l_{ij} \end{bmatrix} \lor \begin{bmatrix} x_{ij} = 0, \forall j \\ G_i \geq 0 \end{bmatrix}

</math>

<math>P_{ij} = </math> is the capacity of the transportation from farmer market i to customer j

<math>x_{ij} = </math> is the number of produced bought by the customer j from the farmer market i

<math>G_{i} = </math> is the amount of purchases at farmer markets i

<math>f_{i} = </math> is the fixed cost for farmers market i

<math>L_{i} = </math> is the capacity amount of farmer markets i

<math>l_{ij} = </math> is the fixed cost for transportation from farmers market i to customer j

This problem can be reformulated using the Convex Hull method.

<math> x_{ij} = x_{ij1} + x_{ij2}</math>

<math> G_{i} = G_{i1} + G_{i2}</math>

<math>x_{ij1} = G_{i1} + G_{i2}</math>

<math>x_{ij2} = G_{i1}+G_{i2}</math>

<math>0 \leq x_{ij1} \leq y_1</math>

<math>0 \leq x_{ij2} \leq y_2</math>

<math>0 \leq G_{j1} \leq y_1</math>

<math>0 \leq G_{j2} \leq y_2</math>

<math>0 \leq x_{ij2} \leq P_{ij}</math>

<math>\sum_j x_{ij1} \leq L_i </math>

<math>G_i \geq f_i + \sum_j L_{ij}</math>

<math>G_{i2} \geq 0</math>

<math>x_{ij2} = 0 </math>

====== Example 2: Using Big-M ======
Using Big-M Method, solve the following given problem below:

<math>Max Z = 6 x_1 + 4 x_2

</math>

Subject to.
<math>2 x_1 + 3 x_2 \leq 30 </math> (1)

<math>3 x_1 + 2 x_2 \leq 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2 \geq 0</math>

To begin solving this problem, we must add the slack variables to rows (1) and row (2).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2, S_1, S_2 \geq 0</math>

After adding the slack variables, we begin to subtract row (3) by the surplus variable and adding artificial variable to row (3).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

We now have the problem in Big-M format below:

<math>Max Z = 6 x_1 + 4 x_2 + S_1 + S_2 + S_3 + MA_1

</math>

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

'Finally we beginning iterating our new formulated problem with the following tables below:

{| class="wikitable"
|+ Iteration 1
|-
! !! !! <math>C_j</math> !! 6 !! 4 !! 0 !! 0 !! 0 !! -M !!
|-
| B || <math>C_B</math> || <math>X_B</math> || <math>x_1</math> || <math>x_2</math> || <math>S_1</math> || <math>S_2</math> || <math>S_3</math> || <math>A_1</math>|| MinRatio <math> x_1 </math>
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|}

==Applications==

[[File:Water.PNG|thumb|Figure 2: Wastewater system ]]
GDP formulations can be used to identify real world problems. Below in Figure 2, shows a wastewater network that removes pollutants from its mixture. The task is to figure out the total cost to discharge the pollution.<ref name=":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. </ref>

This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==Conclusion==
As shown, disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed-integer program. Two methods that are used to reformulate the problem are Convex Hull and Big-M formulations. 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 <ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>. Implementing the Big-M method generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method. Disjunctive inequalities can be used to improve the performance of any general purpose Branch-and-Cut algorithm as shown on the research from Balas and Bonami <ref name=":5">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) </ref>. Most of the real world problems that can be solved through disjunctive inequalities are in chemical engineering or involve process synthesis where a logic decision has to be made to optimize the solution.

==References==

<references />

Disjunctive inequalities

2021-12-15T01:24:12Z

Dl976: /* Conclusion */

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>y_1 + y_2 =1
</math>

<math>y_1 , y_2 \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Examples==

===== Example 1: Locating a Farmer Market =====
An example of a disjunctive inequality that involves m possible locations for a Farmers Market and n customers who would like to purchase produce from those Farmers. This is convenient for customers who want to purchase produces from local farmers. There is a fix cost to supplying each farmers market with produce from local farmers as well as a capacity. There are also demands from customers on what produces they want. This example of disjunctive inequality is to determine why a farmers market is needed at location i for customers j.

<math>\begin{bmatrix} \sum_j x_{ij} \leq L_i \\ 0 \leq x_{ij} \leq P_{ij} , \forall j \\ G_i \leq f_i + \sum_j l_{ij} \end{bmatrix} \lor \begin{bmatrix} x_{ij} = 0, \forall j \\ G_i \geq 0 \end{bmatrix}

</math>

<math>P_{ij} = </math> is the capacity of the transportation from farmer market i to customer j

<math>x_{ij} = </math> is the number of produced bought by the customer j from the farmer market i

<math>G_{i} = </math> is the amount of purchases at farmer markets i

<math>f_{i} = </math> is the fixed cost for farmers market i

<math>L_{i} = </math> is the capacity amount of farmer markets i

<math>l_{ij} = </math> is the fixed cost for transportation from farmers market i to customer j

This problem can be reformulated using the Convex Hull method.

<math> x_{ij} = x_{ij1} + x_{ij2}</math>

<math> G_{i} = G_{i1} + G_{i2}</math>

<math>x_{ij1} = G_{i1} + G_{i2}</math>

<math>x_{ij2} = G_{i1}+G_{i2}</math>

<math>0 \leq x_{ij1} \leq y_1</math>

<math>0 \leq x_{ij2} \leq y_2</math>

<math>0 \leq G_{j1} \leq y_1</math>

<math>0 \leq G_{j2} \leq y_2</math>

<math>0 \leq x_{ij2} \leq P_{ij}</math>

<math>\sum_j x_{ij1} \leq L_i </math>

<math>G_i \geq f_i + \sum_j L_{ij}</math>

<math>G_{i2} \geq 0</math>

<math>x_{ij2} = 0 </math>

====== Example 2: Using Big-M ======
Using Big-M Method, solve the following given problem below:

<math>Max Z = 6 x_1 + 4 x_2

</math>

Subject to.
<math>2 x_1 + 3 x_2 \leq 30 </math> (1)

<math>3 x_1 + 2 x_2 \leq 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2 \geq 0</math>

To begin solving this problem, we must add the slack variables to rows (1) and row (2).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2, S_1, S_2 \geq 0</math>

After adding the slack variables, we begin to subtract row (3) by the surplus variable and adding artificial variable to row (3).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

We now have the problem in Big-M format below:

<math>Max Z = 6 x_1 + 4 x_2 + S_1 + S_2 + S_3 + MA_1

</math>

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

'Finally we beginning iterating our new formulated problem with the following tables below:

{| class="wikitable"
|+ Iteration 1
|-
! !! !! <math>C_j</math> !! 6 !! 4 !! 0 !! 0 !! 0 !! -M !!
|-
| B || <math>C_B</math> || <math>X_B</math> || <math>x_1</math> || <math>x_2</math> || <math>S_1</math> || <math>S_2</math> || <math>S_3</math> || <math>A_1</math>|| MinRatio <math> x_1 </math>
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|}

==Applications==

[[File:Water.PNG|thumb|Figure 2: Wastewater system ]]
GDP formulations can be used to identify real world problems. Below in Figure 2, shows a wastewater network that removes pollutants from its mixture. The task is to figure out the total cost to discharge the pollution.<ref name=":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. </ref>

This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==Conclusion==
As shown, disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed-integer program. 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 <ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>. To reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method. The ability to assign a binary variable written in the term of disjunctive inequalities optimizing the problem and converting it into a single stage MILP. Disjunctive inequalities can be used to improve the performance of any general purpose Branch-and-Cut algorithm as shown on the research from Balas and Bonami <ref name=":5">Balas, E., Bonami, P. "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) </ref>. Most of the real world problems that can be solved through disjunctive inequalities are in chemical engineering or involve process synthesis.

==References==

<references />

Disjunctive inequalities

2021-12-15T01:23:47Z

Dl976: /* Conclusion */

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.<ref name=":0">E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.</ref> 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.<ref name=":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</ref>
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. </math><ref name=":0" /> In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as <math>M_1
</math> and <math>M_2
</math>, and a binary variable y for each inequality. This is shown below by <math>M
</math>, <math>y_1
</math>, and <math>y_2
</math>:

<math>f_1(x) \le M\ast(1-y_1)</math>

<math>f_2(x) \le M\ast(1-y_2)</math>

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}.

<math>y_1 + y_2 =1
</math>

<math>y_1 , y_2 \ \epsilon\ \{ 0,1\}\ \
</math>

===Big-M Reformulation<ref name=":0" /><ref name=":2" />===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, <math>M
</math>, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “<math>M * (1 - y)
</math>” 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.<ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>

For example, given a solution space <math>\begin{bmatrix} y \\ 2\le x_1 \le6 \\ 5\le x_2 \le9 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ 8\le x_1 \le11 \\ 10\le x_2 \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation<ref name=":0" /><ref name=":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 (<math>x_1</math> → <math>x_{11}</math> + <math>x_{12}</math>). 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 <math>x_{11}</math> and <math>x_{12}</math>. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y_1\le\ x_{21}\ \le9\ast y_1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.<ref name=":1" />

==Examples==

===== Example 1: Locating a Farmer Market =====
An example of a disjunctive inequality that involves m possible locations for a Farmers Market and n customers who would like to purchase produce from those Farmers. This is convenient for customers who want to purchase produces from local farmers. There is a fix cost to supplying each farmers market with produce from local farmers as well as a capacity. There are also demands from customers on what produces they want. This example of disjunctive inequality is to determine why a farmers market is needed at location i for customers j.

<math>\begin{bmatrix} \sum_j x_{ij} \leq L_i \\ 0 \leq x_{ij} \leq P_{ij} , \forall j \\ G_i \leq f_i + \sum_j l_{ij} \end{bmatrix} \lor \begin{bmatrix} x_{ij} = 0, \forall j \\ G_i \geq 0 \end{bmatrix}

</math>

<math>P_{ij} = </math> is the capacity of the transportation from farmer market i to customer j

<math>x_{ij} = </math> is the number of produced bought by the customer j from the farmer market i

<math>G_{i} = </math> is the amount of purchases at farmer markets i

<math>f_{i} = </math> is the fixed cost for farmers market i

<math>L_{i} = </math> is the capacity amount of farmer markets i

<math>l_{ij} = </math> is the fixed cost for transportation from farmers market i to customer j

This problem can be reformulated using the Convex Hull method.

<math> x_{ij} = x_{ij1} + x_{ij2}</math>

<math> G_{i} = G_{i1} + G_{i2}</math>

<math>x_{ij1} = G_{i1} + G_{i2}</math>

<math>x_{ij2} = G_{i1}+G_{i2}</math>

<math>0 \leq x_{ij1} \leq y_1</math>

<math>0 \leq x_{ij2} \leq y_2</math>

<math>0 \leq G_{j1} \leq y_1</math>

<math>0 \leq G_{j2} \leq y_2</math>

<math>0 \leq x_{ij2} \leq P_{ij}</math>

<math>\sum_j x_{ij1} \leq L_i </math>

<math>G_i \geq f_i + \sum_j L_{ij}</math>

<math>G_{i2} \geq 0</math>

<math>x_{ij2} = 0 </math>

====== Example 2: Using Big-M ======
Using Big-M Method, solve the following given problem below:

<math>Max Z = 6 x_1 + 4 x_2

</math>

Subject to.
<math>2 x_1 + 3 x_2 \leq 30 </math> (1)

<math>3 x_1 + 2 x_2 \leq 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2 \geq 0</math>

To begin solving this problem, we must add the slack variables to rows (1) and row (2).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 \geq 3 </math> (3)

<math>x_1 , x_2, S_1, S_2 \geq 0</math>

After adding the slack variables, we begin to subtract row (3) by the surplus variable and adding artificial variable to row (3).

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

We now have the problem in Big-M format below:

<math>Max Z = 6 x_1 + 4 x_2 + S_1 + S_2 + S_3 + MA_1

</math>

Subject to.
<math>2 x_1 + 3 x_2 + S_1 = 30 </math> (1)

<math>3 x_1 + 2 x_2 + S_2 = 28 </math> (2)

<math>x_1 + x_2 - S_3 + A_1 = 3 </math> (3)

<math>x_1 , x_2, S_1, S_2, S_3, A_1 \geq 0</math>

'Finally we beginning iterating our new formulated problem with the following tables below:

{| class="wikitable"
|+ Iteration 1
|-
! !! !! <math>C_j</math> !! 6 !! 4 !! 0 !! 0 !! 0 !! -M !!
|-
| B || <math>C_B</math> || <math>X_B</math> || <math>x_1</math> || <math>x_2</math> || <math>S_1</math> || <math>S_2</math> || <math>S_3</math> || <math>A_1</math>|| MinRatio <math> x_1 </math>
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|-
| Example || Example || Example || Example || Example || Example || Example || Example || Example || Example
|}

==Applications==

[[File:Water.PNG|thumb|Figure 2: Wastewater system ]]
GDP formulations can be used to identify real world problems. Below in Figure 2, shows a wastewater network that removes pollutants from its mixture. The task is to figure out the total cost to discharge the pollution.<ref name=":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. </ref>

This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:<ref name=":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. </ref>

<math>MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle</math>

<math>f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle </math> <math>\forall jk \in MU</math>

<math>\textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j</math> <math>\forall jk \in SU</math>

<math>\textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1</math> <math>k \in SU</math>

<math>f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle </math> <math>i \in S_k</math> <math>k \in SU</math>

<math>\underset{h\epsilon D_k}{\lor} \begin{bmatrix} y \\ f_i^j = \Beta_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
</math>

<math>0 \leq \zeta_i^k \leq 1</math> <math>\forall j, k</math>

<math>0 \leq f_i^j, f_k^j</math> <math>\forall i, j, k</math>

<math>0 \leq CP_k</math> <math>\forall k</math>

<math>YP_k^h \in </math> {True, False} <math>\forall h \in D_k \forall k \in PU
</math>

==Conclusion==
As shown, disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed-integer program. 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 <ref name=":1">You, Frengqi. (2021). "Mixed-Integer Linear Programming." </ref>. To reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method. The ability to assign a binary variable written in the term of disjunctive inequalities optimizing the problem and converting it into a single stage MILP. Disjunctive inequalities can be used to improve the performance of any general purpose Branch-and-Cut algorithm as shown on the research from Balas and Bonami <ref name=":1">Balas, E., Bonami, P. "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) </ref>. Most of the real world problems that can be solved through disjunctive inequalities are in chemical engineering or involve process synthesis.

==References==

<references />

Disjunctive inequalities

2021-12-14T21:47:30Z

Dl976:

Disjunctive inequalities

2021-12-12T18:43:58Z

Dl976: /* Conclusion */

Disjunctive inequalities

2021-12-12T18:35:12Z

Dl976:

Disjunctive inequalities

2021-11-29T04:42:29Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an Linear Programing has any constraints either > or =, a starting basic feasible solution may not be achieved. By adding "artificial" variables to the problem, the Big-M method helps draw to a finite conclusion. By modifying the original Linear Programing with the new 'artificial" variable it ensures they are all equal to 0 at the end of the simplex algorithm.

Steps

1. Modifying the constraints so that the Right Hand Side of each constraint is non-negative. Remember that if a inequality is multiplied by a negative number the direction if the inequality is reversed. After this modification, identify each constraint as <, >, or =.

2. Converting each inequality constraint to standard form (If constraint <math>i</math> is a < constraint, we add a slack variable <math>s_{i}</math>; and if constraint <math>i</math> is a > constraint, we subtract an excess variable <math>e_{i}</math>).

3. Adding an artificial variable <math>a_{i}</math> to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction <math>a_{i}</math> > 0.

4. If the Linear Programming is a max problem, add (for each artificial variable) <math>-Ma_i</math> to the objective function where M denotes a very large positive number.

5. If the Linear Programming is a min problem, add (for each artificial variable) <math>Ma_i</math> to the objective function.

6. Solving the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:37:22Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an Linear Programing has any constraints either > or =, a starting basic feasible solution may not be achieved. By adding "artificial" variables to the problem, the Big-M method helps draw to a finite conclusion. By modifying the original Linear Programing with the new 'artificial" variable it ensures they are all equal to 0 at the end of the simplex algorithm.

Steps

1. Modify the constraints so that the Right Hand Side of each constraint is nonnegative (This requires that each constraint with a negative Right Hand Side be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.

2. Convert each inequality constraint to standard form (If constraint <math>i</math> is a < constraint, we add a slack variable <math>s_{i}</math>; and if constraint <math>i</math> is a > constraint, we subtract an excess variable <math>e_{i}</math>).

3. Add an artificial variable <math>a_{i}</math> to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction <math>a_{i}</math> > 0.

4. If the Linear Programming is a max problem, add (for each artificial variable) <math>-Ma_i</math> to the objective function where M denotes a very large positive number.

5. If the Linear Programming is a min problem, add (for each artificial variable) <math>Ma_i</math> to the objective function.

6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:21:50Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an Linear Programing has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original Linear Programing must be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm.

Steps

1. Modify the constraints so that the Right Hand Side of each constraint is nonnegative (This requires that each constraint with a negative Right Hand Side be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.

2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a slack variable s_{i}; and if constraint i is a > constraint, we subtract an excess variable e_{i}).

3. Add an artificial variable a_{i} to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction a_{i} > 0.

4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denotes a very large positive number.

5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function.

6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:20:10Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an Linear Programing has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original Linear Programing must be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm.

Steps

1. Modify the constraints so that the Right Hand Side of each constraint is nonnegative (This requires that each constraint with a negative Right Hand Side be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.

2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a slack variable s_i; and if constraint i is a > constraint, we subtract an excess variable e_i).

3. Add an artificial variable ai to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction a_i > 0.

4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denotes a very large positive number.

5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function.

6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:17:50Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an Linear Programing has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original Linear Programing must be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm.

Steps

1. Modify the constraints so that the Right Hand Side of each constraint is nonnegative (This requires that each constraint with a negative Right Hand Side be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.

2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a slack variable si; and if constraint i is a > constraint, we subtract an excess variable ei).

3. Add an artificial variable ai to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction ai > 0.

4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denotes a very large positive number.

5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function.

6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:15:58Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an LP has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original LP must, of course, be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm.

Steps

1. Modify the constraints so that the RHS of each constraint is nonnegative (This requires that each constraint with a negative RHS be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.

2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a slack variable si; and if constraint i is a > constraint, we subtract an excess variable ei).

3. Add an artificial variable ai to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction ai > 0.

4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denotes a very large positive number.

5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function.

6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.

If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-29T04:14:02Z

Dl976:

Authors: Derek Moore (drm323), Grant Logan (gsl59), Matthew Dinh (md992), Daniel Ladron (dl976)

==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, which include the “Or” and “And” statements. In order to solve a disjunctive, the constraints have to be converted into multiple integer programming (MIP) 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.
== Method==

===General===
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0
</math>, the disjunctive form is given by: <math>\begin{bmatrix} y \\ f_1(x)\ \le\ 0 \end{bmatrix} \lor \begin{bmatrix} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} </math>. In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each inequality. This is shown below by M1, M2, y1, and y1:

<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math>

<math>f_2(x)\ \le\ M_2\ast(1-y_2)</math>

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}.

<math>y_1\ +y_2\ =\ 1
</math>

<math>y_1\ ,\ y_2\epsilon\ {0,1}\ \
</math>

===Big-M Reformulation===
[[File:Big-M-Convex-Hull Reformulation Example Solution Space.png|thumb|Figure 1: Disjunctive inequality solution space that can be solved via disjunction using the Big-M Reformulation or the Convex-Hull Reformulation ]]
For the Big-M reformulation, a sufficiently large number, M, is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “M*(1-y)” to the upper bound and lower bound constraints, respectively, with its respective binary variable. For example, given a solution space <math>\begin{bmatrix} y \\ 2\le\ x_1\ \le6 \\ 5\le\ x_2\ \le9 \end{bmatrix} \lor \begin{bmatrix} -y \\ 8\le\ x_1\ \le11 \\ 10\le\ x_2\ \le15\ \end{bmatrix}

</math>(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:

'''y Formulation'''

<math>2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)</math>

<math>5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1)
</math>

'''-y Formulation'''

<math>8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)</math>

<math>10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)</math>

===Convex-Hull Reformulation ===
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 (x1 → x11 + x12). 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 x11 and x12. For the problem show in Figure 1, the following variable constraints would be formulated:

'''y Formulation'''

<math>0 \leq x_{11} \leq M*y_1
</math>

<math>0 \leq x_{21} \leq M*y_1</math>

'''-y Formulation'''

<math>0 \leq x_{12} \leq M*y_2</math>

<math>0 \leq x_{22} \leq M*y_2</math>

Formulation of the numerical constraints would then be implemented: '''y Formulation'''

<math>2\ast y_1\le\ x_{11}\ \le6\ast y_1 </math>

<math>5\ast y1\le\ x_{21}\ \le9\ast y1</math>

'''-y Formulation'''

<math>8\ast y_2\le\ x_{12}\ \le11\ast y_2</math>

<math>10\ast y_2\le\ x_{22}\ \le15\ast y_2</math>

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.

==Examples==

A good example of solving a disjunctive inequalities is using the reformulation methods below:

<math>[x1 - x2 \leq - 1] V [-x1 + x2 \leq -1]</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4</math>

Using Big-M Formulation:

<math>x1 - x2 \leq -1 + M(1-y1)</math>

<math>-x1 + x2 \leq -1 + M(1-y2)</math>

<math>y1+y2=1, y1,y2 = 0,1</math>

<math>0 \leq x1 \leq 4, 0 \leq x2 \leq 4, M=10</math>

Using Convex-hull Formulation:

<math>x1 = z11 + z12, x2 = z21+z22</math>

<math>z11 - z12\leq -y1, -z12 - z12\leq -y1</math>

<math>1 = y1 + y2, y1,y2=0,1</math>

<math>0 \leq z11 \leq 4y1, 0 \leq z12 \leq 4y2</math>

<math>0 \leq z21 \leq 4y1, 0 \leq z22 \leq 4y2</math>

==Applications==
Applying Big-M Method

If an LP has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original LP must, of course, be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm.

Steps
1. Modify the constraints so that the RHS of each constraint is nonnegative (This requires that each constraint with a negative RHS be multiplied by - 1. Remember that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint.
2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a slack variable si; and if constraint i is a > constraint, we subtract an excess variable ei).
3. Add an artificial variable ai to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction ai > 0.
4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denotes a very large positive number.
5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function.
6. Solve the transformed problem with the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, remember that M is a very large positive number!).

If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem.
If any artificial variables are positive in the optimal solution, the original problem is infeasible

==Conclusion==
Disjunctive inequalities can be used to generate all valid inequalities for an integer program. A simple disjunctive procedure can be used to generate all valid inequalities for a 0 or 1 mixed integer program. 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. Another method to reformulate a disjunctive inequality is to implement the Big-M method which generates a much smaller MILP/MINLP with a tighter relaxation than the convex-hull method.

==References==
<ref>L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.</ref>
<ref>L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.</ref>

Disjunctive inequalities

2021-11-27T16:13:35Z

Dl976:

Disjunctive inequalities

2021-11-27T16:06:03Z

Dl976:

Disjunctive inequalities

2021-11-27T16:04:16Z

Dl976: