Disjunctive inequalities

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Revision as of 17:47, 14 December 2021 by Dl976 (talk | contribs)
Jump to navigation Jump to search

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 , the disjunctive form is given by:  [1] In order to turn the problem into a solvable MIP or MILP, logical constraints are created by using sufficiently large numbers, such as and , and a binary variable y for each inequality. This is shown below by , , and :

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[1][2]

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, , is used to nullify one set of constraints. This is accomplished by adding or subtracting the term “” 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 (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[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 ( + ). 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 and . 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.[3]

Examples

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.


represents the capacity of the farmers market, X is the number of produced bought by the customer from the farmer market, G is the amount of purchases at farmer markets i, L is th

This problem can be reformulated using the Convex Hull method.

,

Applications

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.[4]

This wastewater system can be reformulated into a non-convex General Disjunction Programming problem shown below:[4]



{True, False}

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]. 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. Most of the real world problems that can be solved through disjunctive inequalities are in chemical engineering or involve process synthesis.

References

  1. 1.0 1.1 1.2 1.3 E. Balas, “Disjunctive programming,” Annals of Discr. Math., vol. 5, pp. 6-11, 1979.
  2. 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. 3.0 3.1 3.2 You, Frengqi. (2021). "Mixed-Integer Linear Programming."
  4. 4.0 4.1 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.