Rotman School of Management, University of Toronto, 105 St. George St, Canada e-mail: AndreCire@rotman.utoronto.ca"/>
MAP  >  The Knowledge Engineering Review
2016 Volume 31
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Logic-based Benders decomposition for planning and scheduling: a computational analysis

  • 1.

    Rotman School of Management, University of Toronto, 105 St. George St, Canada e-mail: AndreCire@rotman.utoronto.ca

  • 2.

    Istanbul

  • 3.

    5000 Forbes Ave, Pittsburgh

More Information
  • Abstract: Logic-based Benders decomposition (LBBD) has improved the state of the art for solving a variety of planning and scheduling problems, in part by combining the complementary strengths of constraint programming and mixed integer programming (MIP). We undertake a computational analysis of specific factors that contribute to the success of LBBD, to provide guidance for future implementations. We study a problem class that assign tasks to multiple resources and poses a cumulative scheduling problem on each resource. We find that LBBD is at least 1000 times faster than state-of-the-art MIP on larger instances, despite recent advances in the latter. Further, we conclude that LBBD is most effective when the planning and scheduling aspects of the problem are roughly balanced in difficulty. The most effective device for improving LBBD is the inclusion of a subproblem relaxation in the master problem. The strengthening of Benders cuts also plays an important role when the master and subproblem complexity are properly balanced. These findings suggest future research directions.
  • 加载中
  • Baptiste P., Le Pape C. & Nuijten W. 2001. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer.

    Google Scholar

    Benders J. F. 1962. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4, 238–252.

    Google Scholar

    Benini L., Bertozzi D., Guerri A. & Milano M. 2005. Allocation and scheduling for MPSoCs via decomposition and no-good generation. In Principles and Practice of Constraint Programming (CP 2005), 107–121. Springer.

    Google Scholar

    Cambazard H., Hladik P.-E., Déplanche A.-M., Jussien N. & Trinquet Y. 2004. Decomposition and learning for a hard real time task allocation problem. In Principles and Practice of Constraint Programming (CP 2004), Wallace, M. (eds). Springer, 153–167.

    Google Scholar

    Chu Y. & Xia Q. 2004. Generating Benders cuts for a class of integer programming problems. In CPAIOR 2004 Proceedings, Regin, J. C. & Rueher, M. (eds). Springer, 127–141.

    Google Scholar

    Ciré A., Coban E. & Hooker J. N. 2013. Mixed integer programming vs logic-based Benders decomposition for planning and scheduling. In CPAIOR 2013 Proceedings, Gomes, C. & Sellmann, M. (eds). Springer, 325–331.

    Google Scholar

    Ciré A. & Hooker J. N. 2012. A heuristic logic-based Benders method for the home health care problem. In Presented at Matheuristics 2012.

    Google Scholar

    Çoban E. & Hooker J. N. 2013. Single-facility scheduling by logic-based Benders decomposition. Annals of Operations Research 210, 245–272.

    Google Scholar

    Corréa A. I., Langevin A. & Rousseau L. M. 2004. Dispatching and conflict-free routing of automated guided vehicles: a hybrid approach combining constraint programming and mixed integer programming. In CPAIOR 2004 Proceedings, Regin, J. C. & Rueher, M. (eds). Springer, 370–378.

    Google Scholar

    Fazel-Zarandi M. M. & Beck J. C. 2009. Solving a location-allocation problem with logic-based Benders decomposition. In Principles and Practice of Constraint Programming (CP 2009), Gent, I. P. (ed.). Springer, 344–351.

    Google Scholar

    Geoffrion A. M. 1972. Generalized Benders decomposition. Journal of Optimization Theory and Applications 10, 237–260.

    Google Scholar

    Harjunkoski I. & Grossmann I. E. 2001. A decomposition approach for the scheduling of a steel plant production. Computers and Chemical Engineering 25, 1647–1660.

    Google Scholar

    Harjunkoski I. & Grossmann I. E. 2002. Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods. Computers and Chemical Engineering 26, 1533–1552.

    Google Scholar

    Heching A. & Hooker J. N. 2016. Scheduling home hospice care with logic-based Benders decomposition. In CPAIOR 2016 Proceedings, Gendron, B. (ed.). Springer, 187–197.

    Google Scholar

    Hooker J. N. 1995. Logic-based Benders decomposition. In INFORMS National Meeting (INFORMS 1995).

    Google Scholar

    Hooker J. N. 1996. Inference duality as a basis for sensitivity analysis. In Principles and Practice of Constraint Programming (CP 1996), Freuder, E. C. (ed.). Springer, 224–236.

    Google Scholar

    Hooker J. N. 2000. Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley.

    Google Scholar

    Hooker J. N. 2004. A hybrid method for planning and scheduling. In Principles and Practice of Constraint Programming (CP 2004), Wallace, M. (ed.). Springer, 305–316.

    Google Scholar

    Hooker J. N. 2005a. Planning and scheduling to minimize tardiness. In Principles and Practice of Constraint Programming (CP 2005), 314–327. Springer.

    Google Scholar

    Hooker J. N. 2005b. A hybrid method for planning and scheduling. Constraints 10, 385–401.

    Google Scholar

    Hooker J. N. 2006. An integrated method for planning and scheduling to minimize tardiness. Constraints 11, 139–157.

    Google Scholar

    Hooker J. N. 2007. Planning and scheduling by logic-based Benders decomposition. Operations Research 55, 588–602.

    Google Scholar

    Hooker J. N. 2012. Integrated Methods for Optimization, 2nd edition. Springer.

    Google Scholar

    Hooker J. N. & Ottosson G. 2003. Logic-based Benders decomposition. Mathematical Programming 96, 33–60.

    Google Scholar

    Jain V. & Grossmann I. E. 2001. Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing 13, 258–276.

    Google Scholar

    Maravelias C. T. & Grossmann I. E. 2004. Using MILP and CP for the scheduling of batch chemical processes. In CPAIOR 2004 Proceedings, Regin, J. C. & Rueher, M. (eds). Springer, 1–20.

    Google Scholar

    Terekhov D., Beck J. C. & Brown K. N. 2007. Solving a stochastic queueing design and control problem with constraint programming. In Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI2007), 1, 261–266. AAAI Press.

    Google Scholar

    Thorsteinsson E. 2001. Branch and check: a hybrid framework integrating mixed integer programming and constraint logic programming. In Principles and Practice of Constraint Programming (CP2001), Walsh, T. (ed.). Springer, 16–30.

    Google Scholar

    Timpe C. 2002. Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum 24, 431–448.

    Google Scholar

    Yunes T. H., Aron I. & Hooker J. N. 2010. An integrated solver for optimization problems. Operations Research 58, 342–356.

    Google Scholar

  • Cite this article

    Andre A. Ciré, Elvin Çoban, John N. Hooker. 2016. Logic-based Benders decomposition for planning and scheduling: a computational analysis. The Knowledge Engineering Review 31(5)440−451, doi: 10.1017/S0269888916000254
    Andre A. Ciré, Elvin Çoban, John N. Hooker. 2016. Logic-based Benders decomposition for planning and scheduling: a computational analysis. The Knowledge Engineering Review 31(5)440−451, doi: 10.1017/S0269888916000254
    shu
Download PDF

Article Metrics

Article views(30) PDF downloads(286)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Logic-based Benders decomposition for planning and scheduling: a computational analysis

  • 1.

    Rotman School of Management, University of Toronto, 105 St. George St, Canada e-mail: AndreCire@rotman.utoronto.ca

  • 2.

    Istanbul

  • 3.

    5000 Forbes Ave, Pittsburgh

  • Published online: 20 December 2016
The Knowledge Engineering Review  31,  2016, 31(5): 440−451  |  Cite this article

Abstract: Abstract: Logic-based Benders decomposition (LBBD) has improved the state of the art for solving a variety of planning and scheduling problems, in part by combining the complementary strengths of constraint programming and mixed integer programming (MIP). We undertake a computational analysis of specific factors that contribute to the success of LBBD, to provide guidance for future implementations. We study a problem class that assign tasks to multiple resources and poses a cumulative scheduling problem on each resource. We find that LBBD is at least 1000 times faster than state-of-the-art MIP on larger instances, despite recent advances in the latter. Further, we conclude that LBBD is most effective when the planning and scheduling aspects of the problem are roughly balanced in difficulty. The most effective device for improving LBBD is the inclusion of a subproblem relaxation in the master problem. The strengthening of Benders cuts also plays an important role when the master and subproblem complexity are properly balanced. These findings suggest future research directions.

    HTML

    Rights and permissions
    • © Cambridge University Press, 2016 2016Cambridge University Press
References (30)
  • About this article
    Cite this article
    Andre A. Ciré, Elvin Çoban, John N. Hooker. 2016. Logic-based Benders decomposition for planning and scheduling: a computational analysis. The Knowledge Engineering Review 31(5)440−451, doi: 10.1017/S0269888916000254
    Andre A. Ciré, Elvin Çoban, John N. Hooker. 2016. Logic-based Benders decomposition for planning and scheduling: a computational analysis. The Knowledge Engineering Review 31(5)440−451, doi: 10.1017/S0269888916000254
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return