Disjunctive inequalities: Difference between revisions
No edit summary |
|||
Line 6: | Line 6: | ||
=== General === | === General === | ||
When given a set of inequalities, such as <math>f_1(x)\ \le\ 0\ \And \ f_2(x)\ \le\ 0 | 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} </math>. The constraints would be created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each set of inequality constraints, such as y1 & y2 for the example shown below: | </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>. The constraints would be created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each set of inequality constraints, such as y1 & y2 for the example shown below: | ||
<math>f_1(x)\ \le\ M_1\ast(1-y_1)</math> | <math>f_1(x)\ \le\ M_1\ast(1-y_1)</math> |
Revision as of 13:39, 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 , the disjunctive form is given by: . The constraints would be created by using sufficiently large numbers, such as M1 and M2, and a binary variable y for each set of inequality constraints, such as y1 & y2 for the example shown below:
Big-M Reformulation
Convex-Hull Reformulation
Examples
Applications
Conclusion
References
Authors: Daniel Ladron, Grant Logan, Matthew Dinh, Derek Moore (CBE/SysEn 6800, Fall 2021)