Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

被引:84
作者
You, Fengqi [1 ,2 ]
Grossmann, Ignacio E. [3 ]
机构
[1] Argonne Natl Lab, Argonne, IL 60439 USA
[2] Northwestern Univ, Evanston, IL 60208 USA
[3] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
基金
美国国家科学基金会;
关键词
Benders decomposition; Stochastic programming; Planning; Supply chain; STOCHASTIC-PROGRAMMING APPROACH; LINEAR-PROGRAMS;
D O I
10.1007/s10479-011-0974-4
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:191 / 211
页数:21
相关论文
共 33 条
[1]  
[Anonymous], 1997, Introduction to stochastic programming
[2]  
Archibald TW, 1999, J OPER RES SOC, V50, P468, DOI 10.1057/palgrave.jors.2600727
[3]   A CUTTING PLANE METHOD FROM ANALYTIC CENTERS FOR STOCHASTIC-PROGRAMMING [J].
BAHN, O ;
DUMERLE, O ;
GOFFIN, JL ;
VIAL, JP .
MATHEMATICAL PROGRAMMING, 1995, 69 (01) :45-73
[4]   Partitioning procedures for solving mixed-variables programming problems [J].
Benders, J. F. .
COMPUTATIONAL MANAGEMENT SCIENCE, 2005, 2 (01) :3-19
[5]   A MULTICUT ALGORITHM FOR 2-STAGE STOCHASTIC LINEAR-PROGRAMS [J].
BIRGE, JR ;
LOUVEAUX, FV .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1988, 34 (03) :384-392
[6]  
Contreras I., 2010, OPERATIONS IN PRESS
[7]   A two-stage stochastic integer programming approach as a mixture of Branch-and-Fix Coordination and Benders Decomposition schemes [J].
Eseudero, L. F. ;
Garin, A. ;
Merino, M. ;
Perez, G. .
ANNALS OF OPERATIONS RESEARCH, 2007, 152 (1) :395-420
[8]   Building and solving large-scale stochastic programs on an affordable distributed computing system [J].
Fragnière, E ;
Gondzio, J ;
Vial, JP .
ANNALS OF OPERATIONS RESEARCH, 2000, 99 (1-4) :167-187
[9]   STOCHASTIC DECOMPOSITION - AN ALGORITHM FOR 2-STAGE LINEAR-PROGRAMS WITH RECOURSE [J].
HIGLE, JL ;
SEN, S .
MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (03) :650-669
[10]  
Infanger G., 1993, Annals of Operations Research, V39, P69