Skip to content

Research at St Andrews

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

Research output: Book/ReportBook

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. Modelling Langford's Problem: a viewpoint for search

    Akgün, Ö. & Miguel, I. 27 Aug 2018 The Seventeenth Workshop on Constraint Modelling and Reformulation (ModRef 2018), Proceedings. 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. A review of literature on parallel constraint solving

    Gent, I. P., Miguel, I. J., Nightingale, P. W., McCreesh, C., Prosser, P., Moore, N. & Unsworth, C. 2 Aug 2018 In : Theory and Practice of Logic Programming. First View, 34 p.

    Research output: Contribution to journalArticle

  3. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Automatic generation and selection of streamlined constraint models via Monte Carlo search on a model lattice

    Spracklen, P., Akgun, O. & Miguel, I. J. 2018 Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Cham: Springer, p. 362-372 (Lecture Notes in Computer Science; vol. 11008)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W. 2018 Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

ID: 675532