Disjunctive inequalities: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 113: Line 113:
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.  
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).  
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 ai > 0.  
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.
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.

Revision as of 00:20, 29 November 2021

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 , the disjunctive form is given by:  . 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:

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

Big-M Reformulation

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 (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

-y Formulation

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

-y Formulation

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

-y Formulation

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:


Using Big-M Formulation:


Using Convex-hull Formulation:

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

[1] [2]

  1. L.A. Wolsey, Integer Programming, pp 130 - 133. Wiley, 1998.
  2. L.T. Biegler, I.E. Grossmann, A.W. Westerberg, Systematic Methods of Chemical Process Design. Prentice Hall Press, 1997.