IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v171y2009i1p27-4310.1007-s10479-008-0383-5.html
   My bibliography  Save this article

On the separability of subproblems in Benders decompositions

Author

Listed:
  • Marco Cadoli
  • Fabio Patrizi

Abstract

Benders decomposition is a well-known procedure for solving a combinatorial optimization problem by defining it in terms of a master problem and a slave problem. Its effectiveness relies, among other factors, on the possibility of synthesizing Benders cuts that rule out not only one, but a large class of trial values for the master problem. In turn, for the class of problems we consider (i.e., optimization plus constraint satisfaction) the possibility of separating the slave problem into several subproblems—i.e., problems exhibiting strong intra-relationships and weak inter-relationships—can be exploited for improving searching procedures efficiency. The notion of separation is typically given informally, or relying on syntactical aspects. This paper formally addresses the notion of slave problem separability by giving a semantic definition and exploring it from the computational point of view. Several examples of separable problems are provided, including some proving that a semantic notion of separability is much more helpful than a syntactic one. We show that separability can be formally characterized as equivalence of logical formulae, and prove the undecidability of the separability check problem. Finally, we show how there are cases where automated tools can still be used for checking subproblem separability. Copyright Springer Science+Business Media, LLC 2009

Suggested Citation

  • Marco Cadoli & Fabio Patrizi, 2009. "On the separability of subproblems in Benders decompositions," Annals of Operations Research, Springer, vol. 171(1), pages 27-43, October.
    • Handle: RePEc:spr:annopr:v:171:y:2009:i:1:p:27-43:10.1007/s10479-008-0383-5
    DOI: 10.1007/s10479-008-0383-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0383-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0383-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Roberto Rossi & S. Armagan Tarim & Brahim Hnich & Steven Prestwich & Semra Karacaer, 2010. "Scheduling internal audit activities: a stochastic combinatorial optimization problem," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 325-346, April.
    2. Riise, Atle & Mannino, Carlo & Lamorgese, Leonardo, 2016. "Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling," European Journal of Operational Research, Elsevier, vol. 255(3), pages 719-728.
    3. Castro, Pedro M. & Oliveira, José F., 2011. "Scheduling inspired models for two-dimensional packing problems," European Journal of Operational Research, Elsevier, vol. 215(1), pages 45-56, November.
    4. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    5. Li, Haitao & Womer, Keith, 2012. "Optimizing the supply chain configuration for make-to-order manufacturing," European Journal of Operational Research, Elsevier, vol. 221(1), pages 118-128.
    6. Fan Yang & Roel Leus, 2021. "Scheduling hybrid flow shops with time windows," Journal of Heuristics, Springer, vol. 27(1), pages 133-158, April.
    7. Inkyung Sung & Taesik Lee, 2018. "Scenario-based approach for the ambulance location problem with stochastic call arrivals under a dispatching policy," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 153-170, June.
    8. Rasmussen, Rasmus V. & Trick, Michael A., 2007. "A Benders approach for the constrained minimum break problem," European Journal of Operational Research, Elsevier, vol. 177(1), pages 198-213, February.
    9. Maryam Daryalal & Hamed Pouya & Marc Antoine DeSantis, 2023. "Network Migration Problem: A Hybrid Logic-Based Benders Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 593-613, May.
    10. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    11. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    12. Enayaty-Ahangar, Forough & Rainwater, Chase E. & Sharkey, Thomas C., 2019. "A Logic-based Decomposition Approach for Multi-Period Network Interdiction Models," Omega, Elsevier, vol. 87(C), pages 71-85.
    13. Michela Milano & Mark Wallace, 2010. "Integrating Operations Research in Constraint Programming," Annals of Operations Research, Springer, vol. 175(1), pages 37-76, March.
    14. Abdelmonem M. Ibrahim & Mohamed A. Tawhid, 2023. "An improved artificial algae algorithm integrated with differential evolution for job-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 34(4), pages 1763-1778, April.
    15. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    16. Amine Lamine & Mahdi Khemakhem & Brahim Hnich & Habib Chabchoub, 2016. "Solving constrained optimization problems by solution-based decomposition search," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 672-695, October.
    17. Tallys Yunes & Ionuţ D. Aron & J. N. Hooker, 2010. "An Integrated Solver for Optimization Problems," Operations Research, INFORMS, vol. 58(2), pages 342-356, April.
    18. Yannis Pavlis & Will Recker, 2009. "A Mathematical Logic Approach for the Transformation of the Linear Conditional Piecewise Functions of Dispersion-and-Store and Cell Transmission Traffic Flow Models into Linear Mixed-Integer Form," Transportation Science, INFORMS, vol. 43(1), pages 98-116, February.
    19. Pascal Van Hentenryck, 2002. "Constraint and Integer Programming in OPL," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 345-372, November.
    20. Luca Benini & Michele Lombardi & Michela Milano & Martino Ruggiero, 2011. "Optimal resource allocation and scheduling for the CELL BE platform," Annals of Operations Research, Springer, vol. 184(1), pages 51-77, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:171:y:2009:i:1:p:27-43:10.1007/s10479-008-0383-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.