Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming

Reformulations relaxations and cutting planes for linear generalized disjunctive programming l.jpg
1 / 55
0
0
846 days ago, 323 views
PowerPoint PPT Presentation
2. Blended Integer Program (MIP)- Most regular non-straight discrete/ceaseless improvement model.- Purely mathematical statement based.- If all capacities in MIP are direct ? MILP (nonlinear ? MINLP).. Disjunctive Programming (DP) - Developed by Balas E. (1979, 1985, 1998 (1974)) - Linear programming (LP) with disjunctive requirements..

Presentation Transcript

Slide 1

Reformulations, Relaxations and Cutting Planes for Linear Generalized Disjunctive Programming Ignacio E. Grossmann Nicolas Sawaya, Juan Pablo Ruiz Department of Chemical Engineering Center for Advanced Process Decision-production Carnegie Mellon University Pittsburgh, PA 15213, U.S.A. MIP-2008 Columbia University, New York, NY

Slide 2

Discrete/Continuous Optimization Models Mixed Integer Program (MIP) - Most regular non-straight discrete/ceaseless enhancement show. - Purely condition based. - If all capacities in MIP are direct → MILP (nonlinear → MINLP) . Disjunctive Programming (DP) - Developed by Balas E. (1979, 1985, 1998 (1974)) - Linear programming (LP) with disjunctive limitations. Summed up Disjunctive Program (GDP) - Linear: Raman, Grossmann (1994); Nonlinear: Turkay, Grossmann (1996) - Combination of arithmetical conditions, disjunctions and rationale recommendations. - Natural portrayal of building issues. Blended Logic Linear Programming Hooker and Osorio (1999)

Slide 3

Goal: To bind together GDP with DP keeping in mind the end goal to create MILP reformulations with enhanced relaxations for straight GDP To bring together direct GDP with DP to create - A chain of importance of LP relaxations for direct GDP - A group of disjunctive cutting planes for straight GDP Brief expansion to Nonlinear and Bilinear GDPs - Approximation of arched body and cutting plane calculation - Tightening limits of bilinear GDPs through fundamental strides

Slide 4

Continuous factors Linear Generalized Disjunctive Programming LGDP Model Raman R. what's more, Grossmann I.E. (1994) (LGDP) Objective capacity Common imperatives Disjunctive requirements Logic limitations Boolean factors Logical OR administrator

Slide 5

GDP demonstrate Process Network with settled charges LOGMIP-GAMS

Slide 6

Min Z = + d T x s.t. Bx  b A jk x  a jk - M jk (1-λ jk ) j  J k , k  K (BM) = 1 k  K Hλ  h x  R n , λ jk  {0,1} j  J k , k  K Big-M parameters LGDP to MILP Reformulations Big-M Reformulation Note: ( M jk = max LB  x  UB (A jk x - a jk ), j  J k and k  K ). Unwinding : λ jk  {0,1} gets to be 0  λ jk  1 in (BM)

Slide 7

LGDP to MILP Reformulations Convex Hull Reformulation Lee S. what's more, Grossmann I.E. (2000) Disaggregated factors Min Z = + d T x s.t. Bx  b A jk ν jk  a jk λ jk j  J k , k  K x = ν jk k  K (CH) 0  ν jk  λ jk U jk j  J k , k  K = 1 k  K Hλ  h x  R n , ν jk  R n + , λ jk  {0,1} j  J k , k  K Relaxation : λ jk  {0,1} gets to be 0  λ jk  1 in (CH)

Slide 8

Proposition: The Convex Hull of an arrangement of disjunctions is the littlest curved set that incorporates that set of disjunctions. Besides, t he anticipated unwinding of (CH) onto the space of (BM) is dependably as tight or more tightly than that of (BM) (Grossmann & Lee , 2002) x 2 Big-M Relaxed Feasible Region x 1 Convex Hull Relaxed Projected Feasible Region 1. More tightly practical locale/bring down bound  less hubs  diminish in computational arrangement time. 2. More factors and requirements  more emphasess  increment in computational arrangement time. Is Convex Hull best unwinding?

Slide 9

Disjunction: An arrangement of requirements associated with each other through the coherent OR administrator Conjunction: An arrangement of limitations associated with each other through the legitimate AND administrator Disjunctive Normal Form (DNF) . A disjunction whose terms don't contain assist disjunctions Conjunctive Normal Form (CNF) . A conjunction whose terms don't contain promote conjunctions Disjunctive Programming Constraint set of a DP can be communicated in two comparable outrageous structures

Slide 10

Boolean factors Linear Generalized Disjunctive Programming LGDP Model Raman R. also, Grossmann I.E. (1994) (LGDP) Objective capacity Common imperatives Disjunctive requirements Logic limitations How to manage Boolean and rationale limitations in Disjunctive Programming?

Slide 11

LDP LGDP Reformulating LGDP into Disjunctive Programming Formulation Sawaya N.W. also, Grossmann I.E. (2007) => Integrality  ensured Proposition. LGDP and LDP have identical arrangements.

Slide 12

Equivalent Forms in DP Through Basic Steps Thus the RF is: the place for There are many structures amongst CNF and DNF that are comparable Regular Form (RF): frame spoke to by crossing point of unions of polyhedra

Slide 13

Illustrative Example: Basic Steps Apply Basic Step to: We can then revamp Apply Basic Step to: We can then rework Then F can be conveyed to DNF through 2 fundamental strides. which is its equal DNF

Slide 14

LGDP LDP All conceivable proportional structures for GDP, got through any number of essential strides, are spoken to by: LDP' Equivalent Forms for GDP

Slide 15

disaggregated factors Converting LDP to MIP reformulations => Convex Hull => MIP portrayal

Slide 16

LDP' General layout for any MILP reformulation MIP' Family of MIP Reformulations For GDP

Slide 17

Particular case: Convex Hull Reformulation of LGDP Lee S. also, Grossmann I.E. (2000) (CH) Disaggregated factors While this MILP plan has more grounded unwinding than huge M, it is not most grounded!!

Slide 18

Let us take the accompanying disjunctive set: Then the structure unwinding compares to: A Hierarchy of Relaxations for DP Hull Relaxation (Balas, 1985):

Slide 19

A Hierarchy of Relaxations for GDP

Slide 20

Convex Hull of disjunction Application of 2 Basic Steps Convex Hull of disjunction Illustrative Example: Hierarchy of Relaxations LP Relaxation Tighter Relaxation!

Slide 21

(0,0) (x i ,y i ) y j W i x L = ? Set of little rectangles Numerical Example: Strip-pressing issue Problem proclamation: Hifi (1998) - Given a s et of little rectangles with width H i and length L i . - Large rectangular segment of settled width W and obscure length L. - Objective is to fit little rectangles onto strip without cover and pivot while limiting length L of the strip. i j

Slide 22

Objective capacity Minimize length Disjunctive requirements No cover between rectangles Bounds on factors GDP/DP Model for Strip-pressing issue

Slide 23

Original CH detailing Strengthened plan 102 factors (24 0-1), 143 imperatives LP unwinding = 4, No.nodes= 45 Optimum min L=8 170 factors (60 0-1), 347 limitations LP unwinding = 8, No.nodes= 0 Optimum min L = 8 DP Model For 4 Rectangle Strip-pressing Problem

Slide 24

25 Rectangle Problem Optimal solution= 31 Original CH 1,112 0-1 factors 4,940 cont vars 7,526 limitations LP unwinding = 9 Strengthened 1,112 0-1 factors 5,783 cont vars 8,232 limitations LP unwinding = 27! => 31 Rectangle Problem Optimal solution= 38 Original CH 2,256 0-1 factors 9,716 cont vars 14,911 limitations LP unwinding = 10.64 Strengthened 2,256 0-1 factors 11,452 cont vars 15,624 requirements LP unwinding = 33! =>

Slide 25

Motivation for Cutting Plane Method 1. More tightly achievable district/bring down bound  less hubs  diminish in computational arrangement time. 2. More factors and limitations  more cycles  increment in computational arrangement time. Attainable district as tight as full space AND less factors and limitations

Slide 26

Reverse Polar Cone DERIVATION OF CUTTING PLANES: Dual point of view

Slide 27

Reverse Polar Cone DERIVATION OF CUTTING PLANES: Dual viewpoint

Slide 28

Normalization set Balas, Ceria, Cornuejols (1993) Reverse Polar Cone CUT GENERATION PROBLEM: Dual viewpoint

Slide 29

Infinity Norm Hull-unwinding CUT GENERATION PROBLEM: Primal point of view

Slide 30

Hull Relaxation for Lee & Grossmann Cut Generation Problem for Lee & Grossmann (Separation Problem) Primal point of view partition issue Sawaya, Grossmann (2006)

Slide 31

Derivation of Cutting Planes: Primal viewpoint

Slide 32

(2) Let  (z)  ║z - z bm ║ inf  max i  z i - z i bm  . At that point,   ( + -  - ) Min u s.t u  z i - z i bm i  I u  z i bm - z i  I Feasible district of (SEP) Lagrange Multipliers  +  - Lagrange Multipliers  +  - (3) Let  (z)  ║z - z bm ║ 1   z i - z i bm  . At that point,   ( + -  - ) Min u s.t u i  z i - z i bm i  I u i  z i bm - z i  I Feasible locale of (SEP) Cutting Plane Method Derivation of Cutting Planes Propositions 12, 13, 14: (1) Let  (z)  ║z - z bm ║ 2  ( z – z bm ) T (z – z bm ). At that point,     = ( z – z bm )

Slide 33

This yields z BM . Objective relates to discovering point in body unwinding nearest to z BM . This yields z SEP . z 1 z BM Strengthened Big-M Relaxed Feasible Region z SEP z Big-M Relaxed Feasible Region z 2 Cutting Plane Hull unwinding Projected Feasible Region 1. Settle loose Big-M MILP. CUTTING PLANE METHOD 2. Take care of partition issue. Possible district relates to loose body unwinding. 3. Cutting plane is produced and added to loose huge M MILP. 4. Settle reinforced loose Big-M MILP. Go to 2.

Slide 34

NUMERICAL RESULTS 21-RECTANGLE STRIP PACKING PROBLEM Table 3 Results for twenty one-rectangle strip-pressing issue (CPLEX v. 8.1, default MIP choices turned on) * Total arrangement time incorporates times for loose MIP(s) + LP(s) from detachment issue + MIP

Slide 35

NUMERICAL RESULTS 21-RECTANGLE STRIP PACKING PROBLEM Table 3 Results for twenty one-rectangle strip-pressing issue (CPLEX v. 8.1, default MIP select

SPONSORS