Linear Programming MA 505
Popular in Course
Popular in Mathematics (M)
This 23 page Class Notes was uploaded by Braeden Lind on Thursday October 15, 2015. The Class Notes belongs to MA 505 at North Carolina State University taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/223715/ma-505-north-carolina-state-university in Mathematics (M) at North Carolina State University.
Reviews for Linear Programming
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/15/15
Benders7 Decomposition Methods for Structured Optimization including Stochastic Optimization Robert Mi Freund April 297 2004 2004 Massachusetts Institute of Technology 1 Block Ladder Structure We consider the solution of a linear optimization model of the basic format minimize ch ny st Am b Bx Dy d m 2 0 y 2 0 Here the variables x can be thought of as stage 1 decisions governed by constraints Am b x 2 0 and with cost function ch Once the z variables have been chosen the y variables are chosen next subject to the constraints Dy d 7 Bx y 2 0 and with cost function ny We also consider the more complex format associated with two stage optimization under uncertainty minimize cTz alflTyl OzszTyz aKnyK 7 3417 7 34K st Am b 3190 Diyi d1 B2 Dzyg d2 BKQE DKyK dK 7y17y277yK20 Actually each of these formats can be thought of as a special case of the other format The more complex format above is known as block ladder and is illustrated in Figure 1 tr L tate2 T Figure 1 Block ladder structure of two stage stochastic linear optimization 2 Reformulation 0f the Basic Model The basic model format is VAL minimumm ch ny st Ax b Whose optimal objective value is denoted by VAL We rewrite this as VAL minimumm cTz st Am b m 2 0 where P2 minimumy ny st Dy d 7 Bm y 2 0 We call this problem P2 because it represents the stage 2 decision problem once the stage1 variables x have been chosen Applying duality we can also construct through the dual of P2 which we denote by D2 D2 maximump pTd 7 Bx st DTp f The feasible region of D2 is the set 792plDTpgf Whose extreme points and extreme rays can be enumerated are the extreme points of 732 and are the extreme rays of 732 If we use an algorithm to solve D2 exactly one of two cases will arise D2 is unbounded from above or D2 has an optimal solution In the rst case the algorithm will nd that D2 is unbounded from above and it will return one of the extreme rays 77 r7 for some j with the property that HTd 7 B95 gt 0 in which case 00 In the second case the algorithm will solve D2 and it will return one of the extreme points 15 pi for some i as well as the optimal objective function value which will satisfy PiTd 7 Bm krnlax1pkTd 7 Bx Therefore we can rewrite D2 again as the following problem D2 minimumz 2 st piTd7Bm z i1 A O m l l H MW e Bx This problem simply states that the value of D2 is just the dual objective function evaluated at the best extreme point of the dual feasible region pro vided that the objective function makes an obtuse angle with every extreme ray of the dual feasible region We now take this reformulation of and place it in the orginal prob lem FM VAL minimumm ch 2 st Am b m 2 0 piTd7Bx z 11 r7Td7Bz 0 j1J We call this problem FM for the full master problem Comparing FM to the original version of the problem we see that we have eliminated the variables y from the problem we have added a single scalar variable 2 and we have also added a generically extremely large number of constraints 3 Delayed Constraint Generation The idea behind delayed constraint generation is to try to solve FMP using only a small subset of the constraints and to check afterward whether any of the non included constraints are violated Consider the Testricted master problem RM composed of only k of the extreme point extreme ray constraints from FMP RMPk VALk minimummgtz ch z We solve this problem7 obtaining the optimal objective value VALk and the solution 72 that is optimal for this problem We rst observe that VALk is a lower bound on VAL7 ie VALk VAL In order to check whether the solution 12 is optimal for the full mas ter problem7 we must check whether 12 Violates any of the non included constraints We check for this by solving the linear optimization problem Qi maximump pTd 7 Bi minimumy ny st 13 g f st Dy d 7 Bi yZU lf Qi is unbounded7 the algorithm will return an extreme ray 77 r7 for some j where i will satisfy HTd 7 B92 gt 0 We therefore have found that i has Violated the constraint TjTd 390 S 07 and so we add this constraint to RM and resolve RMP lf Qi has an optimal solution7 the algorithm will return an optimal extreme point 15 pi for some i as well as the optimal solution y to the minimization problem of Now notice rst from Qi that i g is feasible for the original problem Therefore if UB is a previously computed upper bound on VAL we can update the upper bound and our best feasible solution as follows If 932 ng UB then BESTSOL Spay UB e minUBcTaE 1 Also notice that if piTd Bi gt 57 then we have found that i 2 has Violated the constraint piTd 395 S 27 and so we add this constraint to RM and resolve RMP lf piTd 7 Bi 2 then we have max1ltpkgtTltd 7 Bi WM 7 Bi 2 and so 12 is feasible and hence optimal for FMP and so y is optimal for the original problem and so we terminate the algorithm By our construction of upper and lower bounds on VAL we can also terminate the algorithm whenever UB iVALk a for a pre speci ed tolerance 8 31 Delayed Constraint Generation Algorithm Here is a formal description of the algorithm just described 0 Set LB 700 and U13 00 1 A typical iteration starts with the relaxed master problem RMPk7 in which only k constraints of the full master problem FM are included An optimal solution i 2 to the relaxed master problem is computed We update the lower bound on VAL LB lt7 VALk 2 Solve the subproblem Qi Qi maximump pTd 7 Bi minimumy ny st 13 f st Dyd7Bi y 2 0 3 If Qi has an optimal solution7 let 15 and y be the primal and dual solutions of If 15Td 7 Bi 2 then i 2 satis es all constraints of FM7 and so i E is optimal for FMP Furthermore7 this implies that i g is optimal for the original problem If 15Td 7 Bi gt 2 then we add the constraint 15Td 7 Bm z to the restricted master problem RMP Update the upper bound and the best solution If 91 1 UB then BESTSOL Spay UB lt minUB GTE 1 If UB 7 LB 6 then terminate Otherwise7 return to step 1 4 If Qi is unbounded from above7 let 77 be the extreme ray generated by the algorithm that solves Add the constraint Td 7 Bx 0 to the restricted master problem RM7 and return to step 1 This algorithm is known formally as Benders decomposition The Ben ders decomposition method was developed in 1962 27 and is described in many sources on large scale optimization and stochastic programming A general treatment of this method can be found in 37 4 The algorithm can be initialized by rst computing any i that is feasible for the rst stage7 that is7 Ai bi 2 O7 and by choosing the value of 2 to be foo or any suitably small number This will force 12 to violate some constraints of FMP Notice that the linear optimization problems solved in Benders decom position are small relative to the size of the original problem We need to solve RMPk once every outer iteration and we need to solve Qi once every outer iteration Previous optimal solutions of RMPk and Qi can serve as a starting basis for the current versions of RMPk and Qi if we use the simplex method Because interior point methods do not have the capability of starting from a previous optimal solution7 we should think of Benders decomposition as a method to use in conjunction with the simplex method primarily lncidentally7 one can show that Benders decomposition method is the same as Dantzig Wolfe decomposition applied to the dual problem 10 4 Benders Decomposition for Problems with Block Ladder Structure Suppose that our problem has the complex block ladder structure of the following optimization model that we see for two stage optimization under uncertainty VAL minimize cTz 041 flTyl angTyg aKnyK 7 3417 7 9K st Am b 3190 Diyi d1 3290 Dzyz d2 BKQE DKyK dK 7y17y277yK Z 0 Whose optimal objective value is denoted by VAL We re write this as K VAL minimumm cTz Z awzw w1 st Am b where P2w zwz minimumyw 1 ny st Dwyw dw 7 Bum ya 2 0 We call this problem 1377 because it represents the stage2 decision prob lem under scenario w once the stage 1 variables x have been chosen Ap plying duality we can also construct 2w through the dual of P2w which we denote by D2w D2w zwz maximumpm p dw 7 sz st DEM fw The feasible region of D2w is the set i T DLZ 39 pm l prw fax 7 whose extreme points and extreme rays can be enumerated 1 Lu pm 7 71 are the extreme points of D5 and are the extreme rays of Dg If we use an algorithm to solve D2w exactly one of two cases will arise D2w is unbounded from above or D2w has an optimal solution In the rst case the algorithm will nd that D2w is unbounded from above and it will return one of the extreme rays 77w 71 for some j with the property that 12 mimmgto in which case zwz 00 In the second case7 the algorithm will solve D2m7 and it will return one of the extreme points 15w pi for some i as well as the optimal objective function value 2w which will satisfy ZLLIW POTMM 7 Bum k1111 1wpfzTdw 7 Bum 39 Therefore we can rewrite D2w again as the following problem D2w zwz minimumzw 2w st paTdwisz 2w 1Iw MVmiam 0 jLWL This problem simply states that the value of D2w is just the dual objective function evaluated at the best extreme point of the dual feasible region7 pro vided that the objective function makes an obtuse angle with every extreme ray of the dual feasible region We now take this reformulation of zwz and place it in the orginal problem K FMP VAL minimum 0 Z 04sz w1 m21 2K st Am b zgt0 piTdewz 2w i1Iww1K TlTdwiwa 0 j1Jww1 We call this problem FM for the full master problem Comparing FM to the original version of the problem we see that we have eliminated the vector variables y1 yK from the problem we have added K scalar variables 2w for w 1 K and we have also added a generically extremely large number of constraints As in the basic model we consider the Testricted master problem RM composed of only k of the extreme point extreme ray constraints from K RMPk VALk minimum 0 Z 04sz w1 m21 2K st Am b PDTWUJ Box S 2w for some 2 and w mTdm mm S 0 for somei and w where there are a total of k of the inequality constraints We solve this prob lem obtaining the optimal objective value VALk and the solution i 21 2K 14 that is optimal for this problem We rst observe that VALk is a lower bound on VAL ie VALk VAL In order to check whether the solution i 1 K is optimal for the full master problem we must check whether i 21 EK Violates any of the non included constraints We check for this by solving the K linear optimization problems QM maximumpm p dw 7 Bwi minimumyw 1 ny st Dgpw fw st Dwyw dw 7 By ya 2 0 If QLd is unbounded the algorithm will return an extreme ray 77w W for some j where i will satisfy TTdw 7 ME gt 0 We therefore have found that i has Violated the constraint TQTMM 7 Bum g 0 7 and so we add this constraint to RMP lf Qw has an optimal solution the algorithm will return an optimal extreme point 15w pi for some i as well as the optimal solution gw of the minimization problem of Qw lf 1 pLTdw we gt 2w 7 15 then we have found that i 2w has violated the constraint 139 T Pm dw 7 Bum g 2w 7 and so we add this constraint to RMP lf Qw has nite optimal objective function values for all an 1 K then 1311 ng satis es all of the constraints of the original problem Therefore if UB is a previously computed upper bound on VAL we can update the upper bound and our best feasible solution as follows 7 K If CTEZawfngw UB then BESTSOL 9ig1gK mil K UB e minUB GTE Z awfwT w w1 lf 1de 7 Bwi id for all an 1 K then we have gm MW 7 m lt 3gtTltdw i m g a for an w 17K7 vvvv gt m and so i 21 EK satis es all ofthe constraints in FMP Therefore i 21 EK is feasible and hence optimal for FMP and so i g1 gK is optimal for the original problem and we can terminate the algorithm Also by our construction of upper and lower bounds on VAL we can also terminate the algorithm whenever UB iVALk a for a pre speci ed tolerance 8 41 The Delayed Constraint Generation Algorithm for Prob lems With BlockLadder Structure Here is a formal description of the algorithm just described for problems with block ladder structure 0 Set LB 700 and U13 00 1 A typical iteration starts with the relaxed master problem RMPk7 in which only k constraints of the full master problem FM are included An optimal solution 12172K to the relaxed master problem is computed We update the lower bound on VAL LB lt7 VALk 2 For no 17 WK solve the subproblem Qw Qw maximumpm p dw 7 Bwi minimumyw fwTyw st 13ng fw st Dwyw dw 7 Bwi ya 2 0 7 If Qw is unbounded from above7 let m be the extreme ray generated by the algorithm that solves Add the constraint i dw 7 BM 0 to the restricted master problem RMP 7 If Qw has an optimal solution7 let 15w and gw be the primal and dual solutions of Qw If 1de 7 mi gt 2w then we add the constraint 7 Bw gt 2w to the restricted master problem RMP 3 If paTdw 7 Bwi 2w for all w then ig1gK is optimal for the original problem7 and the algorithm terminates 4 If Qd has an optimal solution for all w 17 7 K then update the upper bound on VAL as follows K If CTEZawfngw UB then BESTSOL Roughnng w1 K UB lt minUBcTiZO wfwT w w1 lf UB 7 LB 6 then terminate Otherwise7 add all of the new constraints to RM and return to step 1 In this version of Benders7 decomposition7 we might add as many as K new constraints per major iteration 5 The Power Plant Investment Model Recall the power plant investment model described earlier The full model is 4 125 5 5 15 11in 2 mm Z 04w 2 Z Z 001fiwhjyijkw i1 01 i1 j1 151 4 st Eelz 10000 Budget constraint 11 4 50 Hydroelectric constraint gig1W z for i 1 4 all j kw Capacity constraints 5 Zyi w Z D77W for all j kw Demand constraints 11 zZQ 920 1 where 0 is the probability of scenario w and D w is the power demand in block j and year k under scenario w This model has 4 stage1 variables and 46875 stage2 variables Further more other than nonnegativity constraints there are 2 stage 1 constraints and 375 constraints for each of the 125 scenarios in stage 2 This yields a total of 46 877 constraints It is typical for problems of this type to be solved by Benders7 decomposition which exploits the problem structure by decomposing it into smaller problems Consider a xed x which is feasible ie z 2 0 and satis es the budget constraint and hydroelectric constraint Then the optimal second stage variables gigkw can be determined by solving for each 51 the problem 5 5 15 mm min 2 Z Z 001whykw y 11 j1 51 subject to gigkw M for i 1 4 all j k Capacity constraints 5 Ziamm Z Djkw for all j k Demand constraints 11 240 2 Although this means solving 125 problems one for each scenario each subproblem has only 375 variables and 375 constraints Furthermore the structure of this problem lends itself to a simple greedy optimal solution The dual of the subproblem 2 is 4 5 15 5 15 zwz max 2 Z Z mpijkw Z Z Djkwqjkw m i1 j1 k1 j1 k1 subject to mm gm 001wh 2 14 for all j k 3 mm S 0 qjkw Z 0 6 Computational Results All models were solved in OPLStudio on a Sony Viao Laptop with a Pentium 111 750 MHZ Processor Running Windows 2000 Table 1 shows the number of iterations taken by the simplex method to solve the original model Original Model CPT Time lterations minutesseconds Simplex 41334 503 Table 1 lterations to solve the original model We next solved the problem using Benders7 decomposition using a du ality gap tolerance of 6 10 We rst solved the model treating all stage 2 variables and constraints as one large block using the basic Ben ders7 decomposition algorithm We next solved the model treating each of the 125 stage2 scenarios as a separate block using the more advanced ver sion of Benders7 decomposition that takes full advantage of the block ladder structure The number of master iterations and the number of constraints 20 generated by the two different solution methods are shown in Table 2 Notice that while the block ladder version generates more constraints7 it requires fewer major iterations Table 3 shows the computation times of all of the solution methods From this table7 it is evident that the method that takes full advantage of the block ladder structure was the most ef cient solution method Table 2 Master iterations and generated constraints for the two implemen tations of Benders decomposition No Decomposition Benders Decomposition Original Model Basic 1 Block Block Ladder 125 Blocks CPU Time minsec 503 322 127 Table 3 Computation times minsec for the original model and the two implementations of Benders decomposition Figure 2 shows the the upper and lower bounds generated by Benders decomposition at each iteration Notice that there is initial rapid conver gence of the bounds to the optimal objective function value7 followed by very slow convergence thereafter This is typical pattern that is observed in decomposition methods in general Figure 3 shows the duality gap between the upper and lower bounds on a logarithmic scale Here we see that the convergence rate of the duality gap is roughly linear 21 n BlockLadder 125 Block A A Begichiock w o l Bound5m billion 55 N o I I a Aquot E A 10 39 i 5 10 15 terauon Figure 2 Upper and lower bounds for Benders decomposition 7 Exercise The current version of the powerplant planning model uses the strategy of adding one constraint for every scenario in the model at each iteration of the Benders decomposition method This means that k 125 new constraints are added to the model at each outer iteration of the method As discussed in class7 this strategy outperforms the alternative strategy of adding only k 1 new constraint at each outer iteration of the model In this question7 you are asked to explore intermediate strategies that might improve computation time for solving the powerplant planning model using Benders decomposition By adding your own control logic in the region indicated in the script le7 bender1osc7 experiment with different strategies for limiting andor controlling the number of new constraints added to the model at each outer iteration You may also modify the model les or the data le if neces sary One strategy that you might try would be to add a xed number of 22 105 32 a BlockLadder125 Blockl A A Basic 1 Block 1 A 10 DaAAA 393 A A 103 3 AA A g nq AA g 39AA 2 2 39a 39A 910 7 AAA 7 i 39A 2 D 39A 3 1 quotn 39A39A 8 10 1AA A 2 a 392 3 10 E 39 E n 10quot 10 2 I I I l l 5 10 15 2o 25 30 35 4 terauon Figure 3 Gap between upper and lower bounds for Benders7 decomposition constraints7 say k 107 207 or 307 etc7 constraints per outer iteration References 1 D Anderson Models for determining least cost investments in electric ity supply The Bell Journal of Economics 326772997 1972 2 J Benders Partitioning procedures for solving mixed variables pro gramming problems Numerische Mathematik 423872527 1962 3 D Bertsimas and J Tsitisklis Introduction to Linear Optimization Athena Scienti c7 1997 4 J Birge and F Louveaux Introduction to Stochastic Programming Springer Verlag7 1997 23
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'