Difference between revisions of "Convex generalized disjunctive programming (GDP)"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 13: Line 13:
  
 
       s.t.g(x) \leq 0\\
 
       s.t.g(x) \leq 0\\
rki(x) \leg M^ki(1-yki)  
+
            r_{ki}(x) \leq M^{ki}(1-y_{ki})\quad k \in K,i \in D_k\\
  
       m_i\ge0,\quad \forall i \in I\\
+
       \sum_{i \in D_k} y_{ki} = 1\quad k \in K\\
 +
      Hy \geq h\\
 +
      x^{lo} \leq x \leq x^{up}\\
 +
      x \in \Re^n\\
 
        
 
        
       y_j\in {0,1},\quad \forall j \in J \end{align}</math>
+
       y_{ki} \in {0,1} \quad k \in K, i \in D_k \end{align}</math>
 +
 
 +
 
 +
Notice that the boolean term from the original GDP has been converted into a numerical {0,1}. The logic relations have also been converted into linear integer constraints (Hy).
 +
 
 +
(<nowiki>https://kilthub.cmu.edu/articles/journal_contribution/Improved_Big-M_Reformulation_for_Generalized_Disjunctive_Programs/6467063</nowiki>)
 +
 
 +
This MINLP reformulation can now be used in well-known solvers (list them here) to calculate a solution. 
  
 
== Numerical Example ==
 
== Numerical Example ==

Revision as of 17:23, 21 November 2020

Edited By: Nicholas Schafhauser, Blerand Qeriqi, Ryan Cuppernull

Introduction

Theory

Methodology

The two most common ways of reformulating a GDP problem into an MINLP are through Big-M (BM) and Hull Reformulation (HR). BM is the simpler of the two, while HR results in tighter relaxation (smaller feasible region) and faster solution times. (https://kilthub.cmu.edu/articles/A_hierarchy_of_relaxations_for_nonlinear_convex_generalized_disjunctive_programming/6466535)

Below is an example of the reformulation of the GDP problem from the Theory section reformulated into an MINLP by using the Big-M method.


Notice that the boolean term from the original GDP has been converted into a numerical {0,1}. The logic relations have also been converted into linear integer constraints (Hy).

(https://kilthub.cmu.edu/articles/journal_contribution/Improved_Big-M_Reformulation_for_Generalized_Disjunctive_Programs/6467063)

This MINLP reformulation can now be used in well-known solvers (list them here) to calculate a solution.

Numerical Example

Applications

Conclusion

References