Skip to content

Research at St Andrews

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

Research output: ResearchBook

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.

Close

Details

Original languageEnglish
PublisherUnknown Publisher
Number of pages16
StatePublished - 2006

    Research areas

  • LOCATION-PROBLEMS, ALGORITHM

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. A review of literature on parallel constraint solving

    Gent, I. P., McCreesh, C., Miguel, I. J., Moore, N., Nightingale, P. W., Prosser, P. & Unsworth, C. 30 Apr 2018 (Accepted/In press) In : Theory and Practice of Logic Programming.

    Research output: Research - peer-reviewArticle

  2. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P. Oct 2017 In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Research - peer-reviewArticle

  3. Cloud benchmarking for maximising performance of scientific applications

    Varghese, B., Akgun, O., Miguel, I. J., Thai, L. T. & Barker, A. D. 26 Aug 2016 In : IEEE Transactions on Cloud Computing. PP, 99, 7553491

    Research output: Research - peer-reviewArticle

  4. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W. 2016 Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892)

    Research output: ResearchConference contribution

  5. Automatically improving SAT encoding of constraint problems through common subexpression elimination in Savile Row

    Nightingale, P., Spracklen, P. & Miguel, I. J. Oct 2015 Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. Pesant, G. (ed.). Springer, Vol. 9255, p. 330-350 10 p. (Lecture Notes in Computer Science; vol. 9255)

    Research output: ResearchConference contribution

ID: 675532