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, İsveç, 20 - 22 Haziran 2005, cilt.3978 LNAI, ss.133-148 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 3978 LNAI
  • Doi Numarası: 10.1007/11754602_10
  • Basıldığı Şehir: Uppsala
  • Basıldığı Ülke: İsveç
  • Sayfa Sayıları: ss.133-148
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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.