Disjunctive inequalities: Difference between revisions
| Line 103: | Line 103: | ||
Using Convex-hull Formulation: | Using Convex-hull Formulation: | ||
<math>x_1 = | <math>x_1 = z_{11} + z_{12}, x_2 = z_{21++z_{22}</math> | ||
<math> | <math>z_{11} - z_{12}\leq -y_1, -z_{12} - z_{12}\leq -y_1</math> | ||
<math>1 = y_1 + y_2, y_1,y_2=0,1</math> | <math>1 = y_1 + y_2, y_1,y_2=0,1</math> | ||
<math>0 \leq | <math>0 \leq z_{11} \leq 4y_1, 0 \leq z_{12} \leq 4y_2</math> | ||
<math>0 \leq | <math>0 \leq z_{21} \leq 4y_1, 0 \leq z_{22} \leq 4y_2</math> | ||
==Applications== | ==Applications== | ||
Revision as of 15:25, 12 December 2021
Authors: Derek Moore, Grant Logan, Matthew Dinh, Daniel Ladron (SYSEN 5800/CHEME 6800 Fall 2021)
Introduction
Disjunctive inequalities are a form of disjunctive constraints that can be applied to linear programming. Disjunctive constraints are applied in all disjunctive programming, which just refers to the use of logical constraints in linear inequalities, which include “Or,” And,” or "Complement of" statements.[1] In order to solve a disjunctive, the constraints have to be converted into mixed-integer programming (MIP) or mixed-inter linear programming (MILP) constraints, which is called disjunction. Disjunction involves the implementation of a binary variable to create a new set of constraints that can be solved easily. Two common methods for disjunction are the Big-M Reformulation and the Convex-Hull Reformulation.[2]
Method
General
When given a set of inequalities, such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1(x) \le 0\ \ \And \ \ f_2(x) \le 0 } , the disjunctive form is given by: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{bmatrix} y \\ f_1(x) \le 0 \end{bmatrix} \lor \begin{bmatrix} \neg y \\ f_2(x) \le 0 \end{bmatrix}. } [1] In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_1 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M_2 } , and a binary variable y for each inequality. This is shown below by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1 } , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_2 } :
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1(x) \le M\ast(1-y_1)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_2(x) \le M\ast(1-y_2)}
To set the binary variable to be mutually exclusive, the sum of the variables is set to 1 and the range is set to {0,1}.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1 + y_2 =1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1 , y_2 \ \epsilon\ \{ 0,1\}\ \ }
Big-M Reformulation[1][2]
For the Big-M reformulation, a sufficiently large number, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M } , is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M * (1 - y) } ” to the upper bound and lower bound constraints, respectively, with its respective binary variable. While choosing a large M value allows for isolation, the large value also yields poor relaxation of the model space.[3]
For example, given a solution space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} } (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
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 - M*(1-y_1) \leq x1 \leq 6 + M*(1-y_1)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5 - M*(1-y_1) \leq x2 \leq 9 + M*(1-y_1) }
-y Formulation
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8 - M*(1-y_2) \leq x1 \leq 11 + M*(1-y_2)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10 - M*(1-y_2) \leq x2 \leq 15 + M*(1-y_2)}
Convex-Hull Reformulation[1][2]
Similar to the Big-M reformulation, the convex-hull reformulation uses a binary variable, y, to constrain the set of inequalities. The first step in converting the problem into a solvable MILP is breaking all variables into a set of variables, such as (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} → Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{11}} + Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{12}} ). By adding these addition variables, it is possible to isolate what set of parameters provide for the optimal solution of the problem. Then, similar to the Big-M reformulation, a sufficiently large variable, M, is used to nullify the non-optimal variable set, such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{11}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{12}} . For the problem show in Figure 1, the following variable constraints would be formulated:
y Formulation
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{11} \leq M*y_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{21} \leq M*y_1}
-y Formulation
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{12} \leq M*y_2}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{22} \leq M*y_2}
Formulation of the numerical constraints would then be implemented: y Formulation
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\ast y_1\le\ x_{11}\ \le6\ast y_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5\ast y_1\le\ x_{21}\ \le9\ast y_1}
-y Formulation
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8\ast y_2\le\ x_{12}\ \le11\ast y_2}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10\ast y_2\le\ x_{22}\ \le15\ast y_2}
With the Convex-Hull transformation, the additional constraints confine the problem, such that a tighter (convex) solution space is examined compared to Big-M Formulation.[3]
Examples
A good example of solving a disjunctive inequalities is using the reformulation methods below:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [x_1 - x_2 \leq - 1] \lor [-x_1 + x_2 \leq -1]}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_1 \leq 4, 0 \leq x_2 \leq 4}
Using Big-M Formulation:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 - x_2 \leq -1 + M(1-y_1)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -x_1 + x_2 \leq -1 + M(1-y_2)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1+y_2=1, y_1,y_2 = 0,1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_1 \leq 4, 0 \leq x_2 \leq 4, M=10}
Using Convex-hull Formulation:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = z_{11} + z_{12}, x_2 = z_{21++z_{22}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_{11} - z_{12}\leq -y_1, -z_{12} - z_{12}\leq -y_1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 = y_1 + y_2, y_1,y_2=0,1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq z_{11} \leq 4y_1, 0 \leq z_{12} \leq 4y_2}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq z_{21} \leq 4y_1, 0 \leq z_{22} \leq 4y_2}
Applications
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.
This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle MinZ = \textstyle \sum_{k\epsilon P U} C P_k\displaystyle}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_k^j = \textstyle \sum_{i\epsilon M_k} f_i^j\displaystyle } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall jk \in MU}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_{i\epsilon S_k} f_i^j\displaystyle = f_k^j} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall jk \in SU}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_{i\epsilon S_k} \zeta_i^j\displaystyle = 1} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in SU}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_k^j = \textstyle \zeta_i^k f_k^j \forall_j\displaystyle } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in S_k} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in SU}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq \zeta_i^k \leq 1}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall j, k}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq f_i^j, f_k^j} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall i, j, k}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq CP_k} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall k}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle YP_k^h \in } {True, False} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall h \in D_k \forall k \in PU }
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 [3]. 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
- ↑ 1.0 1.1 1.2 1.3 E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.
- ↑ 2.0 2.1 2.2 Pedro M. Castro and Ignacio E. Grossmann. 'Generalized Disjunctive Programming as a Systematic Modeling Framework to Derive Scheduling Formulations." 2012 51 (16), 5781-5792 DOI: 10.1021/ie2030486
- ↑ 3.0 3.1 3.2 You, Frengqi. (2021). "Mixed-Integer Linear Programming."
- ↑ L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.
- ↑ L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.
- ↑ 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.