Building and solving large-scale stochastic programs on an affordable distributed computing system

被引:15
作者
Fragnière, E
Gondzio, J
Vial, JP
机构
[1] Univ Lausanne, HEC, CH-1015 Lausanne, Switzerland
[2] Univ Edinburgh, Dept Math & Stat, Edinburgh EH9 3JZ, Midlothian, Scotland
[3] Univ Geneva, Sect Management Studies, HEC, Logilab, CH-1211 Geneva 4, Switzerland
关键词
algebraic modeling language; decomposition methods; distributed systems; large-scale optimization; stochastic programming;
D O I
10.1023/A:1019245101545
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present an integrated procedure to build and solve big stochastic programming models. The individual components of the system - the modeling language, the solver and the hardware - are easily accessible, or a least affordable to a large audience. The procedure is applied to a simple financial model, which can be expanded to arbitrarily large sizes by enlarging the number of scenarios. We generated a model with one million scenarios, whose deterministic equivalent linear program has 1,111,112 constraints and 2,555,556 variables. We have been able to solve it on the cluster of ten PCs in less than 3 hours.
引用
收藏
页码:167 / 187
页数:21
相关论文
共 47 条
[1]  
[Anonymous], 1995, P INT C PAR PROC
[2]   ON THE AUGMENTED SYSTEM APPROACH TO SPARSE LEAST-SQUARES PROBLEMS [J].
ARIOLI, M ;
DUFF, IS ;
DERIJK, PPM .
NUMERISCHE MATHEMATIK, 1989, 55 (06) :667-684
[3]   PERFORMANCE OF A BENCHMARK PARALLEL IMPLEMENTATION OF THE VANSLYKE AND WETS ALGORITHM FOR 2-STAGE STOCHASTIC PROGRAMS ON THE SEQUENT BALANCE [J].
ARIYAWANSA, KA ;
HUDSON, DD .
CONCURRENCY-PRACTICE AND EXPERIENCE, 1991, 3 (02) :109-128
[4]  
BENDERS JF, 1962, NUMER MATH, V4, P238, DOI [10.1007/BF01386316, DOI 10.1007/BF01386316, DOI 10.1007/S10287-004-0020-Y]
[5]  
Birge J. R., 1997, INFORMS Journal on Computing, V9, P111, DOI 10.1287/ijoc.9.2.111
[6]   A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs [J].
Birge, JR ;
Donohue, CJ ;
Holmes, DF ;
Svintsitski, OG .
MATHEMATICAL PROGRAMMING, 1996, 75 (02) :327-352
[7]   COMPUTING BLOCK-ANGULAR KARMARKAR PROJECTIONS WITH APPLICATIONS TO STOCHASTIC-PROGRAMMING [J].
BIRGE, JR ;
QI, LQ .
MANAGEMENT SCIENCE, 1988, 34 (12) :1472-1479
[8]   DECOMPOSITION AND PARTITIONING METHODS FOR MULTISTAGE STOCHASTIC LINEAR-PROGRAMS [J].
BIRGE, JR .
OPERATIONS RESEARCH, 1985, 33 (05) :989-1007
[9]   A MULTICUT ALGORITHM FOR 2-STAGE STOCHASTIC LINEAR-PROGRAMS [J].
BIRGE, JR ;
LOUVEAUX, FV .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1988, 34 (03) :384-392
[10]  
BIRGE JR, 1988, COMMITTEE ALGORITHMS, V17, P1