tag:blogger.com,1999:blog-8781383461061929571.post8923887849130396095..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Separable Benders DecompositionPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8781383461061929571.post-63389559715743723482013-01-27T01:10:11.534-05:002013-01-27T01:10:11.534-05:00My sub-problem is as follows (using slightly diffe...My sub-problem is as follows (using slightly different notations):<br /><br />Maximize c2' * y<br />Subject To: <br />A*y <= B (Itinerary demand constraints)<br />C*y <= D (Leg capacity constraints)<br /><br />Each leg capacity constraint could be decomposed into a Zj. But there are few ys that are common in more than one leg. So it's not very cleanly decomposable. Following would be a Benders cut for each leg:<br /><br />Zj <= Sum{A * Pd * Yj} + Sum{C * Pc * Xj}<br /><br />Where: <br />Pd is the dual of the demand constraints<br />Yj is the primal solution for the list of y variables present in the leg j<br />Pc is the dual of the capacity constraints<br />Xj is the list of x variables associated with leg j<br /><br />This way of decomposing the Zj helps in solving larger problems very fast. But optimality is not guaranteed always. I get within 1% of the optimal solution most of the time.<br /><br />Thanks,<br />Vivek.<br />Verittaashttps://www.blogger.com/profile/07883764897988078532noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-1725388279655800802013-01-26T10:15:08.302-05:002013-01-26T10:15:08.302-05:00If the subproblem was not decomposable, how did yo...If the subproblem was not decomposable, how did you split the objective contribution ($c_2^\prime y$) into components ($z_j$)?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47173139554206672972013-01-26T08:57:14.049-05:002013-01-26T08:57:14.049-05:00I found that solving the decomposable sub-problems...I found that solving the decomposable sub-problems as a whole LP but still dividing the Zs into constituent Zs worked out much better. Having Zs like this helped in faster convergence. In my problem, there wasn't clear decomposable sub-problems. Few variables were common to more than one sub-problem. But this still helped in getting solutions very close to optimality!<br /><br />Regards,<br />Vivek.Verittaashttps://www.blogger.com/profile/07883764897988078532noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6317194455066031052013-01-26T08:53:34.633-05:002013-01-26T08:53:34.633-05:00This comment has been removed by the author.Verittaashttps://www.blogger.com/profile/07883764897988078532noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-16651761881845130072012-09-23T15:40:07.236-04:002012-09-23T15:40:07.236-04:00Thomas,
Thanks for pointing that out. You are of ...Thomas,<br /><br />Thanks for pointing that out. You are of course correct (and Benders originally intended his approach for an NLP/LP combination).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-7918522112610704322012-09-23T14:30:28.939-04:002012-09-23T14:30:28.939-04:00You should also mention that this is not only corr...You should also mention that this is not only correct if x is an integer-valued variable. This is also interesting for pure stochastic linear programming and also for more general settings, e.g. where the master problem is a MIP or even a nonlinear problem.<br /><br />Best regards,<br />ThomasThomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.com