Disjunctive inequalities: Difference between revisions

Revision as of 14:18, 24 November 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, 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 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} -y \\ f_2(x)\ \le\ 0 \end{bmatrix} } . 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:

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_1\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_2\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

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

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) \leq x1 \leq 6 + M*(1-y)}

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) \leq x2 \leq 9 + M*(1-y) }

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) \leq x1 \leq 11 + M*(1-y)}

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) \leq x2 \leq 15 + M*(1-y)}

Convex-Hull Reformulation

Examples

Applications

Conclusion

References

Authors: Daniel Ladron, Grant Logan, Matthew Dinh, Derek Moore (CBE/SysEn 6800, Fall 2021)

@@ Line 21: / Line 21: @@
 === 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}
@@ Line 26: / Line 27: @@
 <math>2 - M*(1-y) \leq x1 \leq 6 +  M*(1-y)</math>
 <math>5 - M*(1-y) \leq x2 \leq 9 + M*(1-y)
 </math>
+<math>8 - M*(1-y) \leq x1 \leq 11 + M*(1-y)</math>
+<math>10 - M*(1-y) \leq x2 \leq 15 + M*(1-y)</math>
 === Convex-Hull Reformulation ===