A hybrid Benders' decomposition method for solving Stochastic Constraint Programs with linear recourse

S. Armagan Tarim, Ian Miguel

Research output: Book/ReportBook

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
PublisherUnknown Publisher
Number of pages16
Publication statusPublished - 2006

Keywords

  • LOCATION-PROBLEMS
  • ALGORITHM

Fingerprint

Dive into the research topics of 'A hybrid Benders' decomposition method for solving Stochastic Constraint Programs with linear recourse'. Together they form a unique fingerprint.

Cite this