Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

Fengqi You, Ignacio E. Grossmann

Research output: Contribution to journalArticlepeer-review

92 Scopus citations

Abstract

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm.

Original languageEnglish (US)
Pages (from-to)191-211
Number of pages21
JournalAnnals of Operations Research
Volume210
Issue number1
DOIs
StatePublished - Nov 2013

Funding

Acknowledgement We gratefully acknowledge financial support from the Dow Chemical Company, the Pennsylvania Infrastructure Technology Alliance (PITA), the National Science Foundation under Grant No. CMMI-0556090, and the U.S. Department of Energy under contract DE-AC02-06CH11357.

Keywords

  • Benders decomposition
  • Planning
  • Stochastic programming
  • Supply chain

ASJC Scopus subject areas

  • General Decision Sciences
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Multicut Benders decomposition algorithm for process supply chain planning under uncertainty'. Together they form a unique fingerprint.

Cite this