A scenario decomposition algorithm for 0-1 stochastic programs

被引：60

作者：

Ahmed, Shabbir ^{[1
]}

机构：

[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 06期

基金：

美国国家科学基金会;

关键词：

0-1 stochastic programs; Scenario/dual decomposition; Parallel computation; COMBINATORIAL OPTIMIZATION; DUAL DECOMPOSITION;

D O I：

10.1016/j.orl.2013.07.009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 [运筹学与控制论]; 120117 [社会管理工程];

摘要：

We propose a scenario decomposition algorithm for stochastic 0-1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：565 / 569

页数：5

共 15 条

[1]

Maximizing a class of submodular utility functions [J].

Ahmed, Shabbir ;

Atamtuerk, Alper .

MATHEMATICAL PROGRAMMING, 2011, 128 (1-2) :149-169

[2]

BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs [J].

Alonso-Ayuso, A ;

Escudero, LF ;

Ortuño, MT .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 151 (03) :503-519

[3]

Angulo Gustavo, 2013, WORKING PAPER

[4]

[Anonymous], 1999, Athena scientific Belmont

[5]

Dual decomposition in stochastic integer programming [J].

Caroe, CC ;

Schultz, R .

OPERATIONS RESEARCH LETTERS, 1999, 24 (1-2) :37-45

[6]

Progressive Hedging-Based Metaheuristics for Stochastic Network Design [J].

Crainic, Teodor Gabriel ;

Fu, Xiaorui ;

Gendreau, Michel ;

Rei, Walter ;

Wallace, Stein W. .

NETWORKS, 2011, 58 (02) :114-124

[7]

Gabriel E, 2004, LECT NOTES COMPUT SC, V3241, P97

[8]

The sample average approximation method for stochastic discrete optimization [J].

Kleywegt, AJ ;

Shapiro, A ;

Homem-De-Mello, T .

SIAM JOURNAL ON OPTIMIZATION, 2001, 12 (02) :479-502

[9]

Lokketangen A., 1996, Journal of Heuristics, V2, P111, DOI 10.1007/BF00247208

[10]

On parallelizing dual decomposition in stochastic integer programming [J].

Lubin, Miles ;

Martin, Kipp ;

Petra, Cosmin G. ;

Sandikci, Burhaneddin .

OPERATIONS RESEARCH LETTERS, 2013, 41 (03) :252-258

← 1 2 →