A hybrid Benders' decomposition method for solving stochastic constraint programs with linear recourse

TARIM Ş. A., Miguel I.

Joint ERCIM/CoLogNET International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2005, Uppsala, Sweden, 20 - 22 June 2005, vol.3978 LNAI, pp.133-148 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 3978 LNAI
  • Doi Number: 10.1007/11754602_10
  • City: Uppsala
  • Country: Sweden
  • Page Numbers: pp.133-148
  • Hacettepe University Affiliated: Yes


We adopt Benders' decomposition algorithm to solve scenario-based Stochastic Constraint Programs (SCPs) with linear recourse. Rather than attempting to solve SCPs via a monolithic model, we show that one can iteratively solve a collection of smaller sub-problems and arrive at a solution to the entire problem. In this approach, decision variables corresponding to the initial stage and linear recourse actions are grouped into two sub-problems. The sub-problem corresponding to the recourse action further decomposes into independent problems, each of which is a representation of a single scenario. Our computational experience on stochastic versions of the well-known template design and warehouse location problems shows that, for linear recourse SCPs, Benders' decomposition algorithm provides a very efficient solution method. © Springer-Verlag Berlin Heidelberg 2006.