An Effective Heuristic for Multistage Stochastic Linear Programming
C. Beltran-Royo (cesar.beltranurjc.es)
Abstract: The Multistage Stochastic Linear Programming (SLP) problem may become numerically intractable for huge instances, in which case one can solve an approximation as for example the well known Expected Value (EV) problem. In this paper we introduce a new approximation to the SLP problem that we call the Event Linear Programming (ELP) problem. Based in this problem we derive the ELP heuristic that produces a lower and an upper bound for the SLP problem. We have assessed the validity of the ELP heuristic by solving large scale instances of the network revenue management problem for the fight tickets selling (up to 98 millions of variables and almost 90 millions of constraints). The average CPLEX time for the EV, ELP and SLP approaches has been 89, 142 and 1816 seconds, respectively, for the instances of the testbed we have experimented with (CPLEX has failed to solve 19% of the SLP instances within a time limit of two hours). The average worst case optimality gap for the EV and ELP approaches, has been 3.63% and 0.45%, respectively. Thus, regarding the capacity to deal with uncertainty and the numerical tractability, the ELP approach lies between the SLP and the EV approaches.
Keywords: Multistage stochastic programming, constraint aggregation, conditional expectation, scenario tree, revenue management.
Category 1: Stochastic Programming
Citation: Working Paper, 28/05/2013, Statistics and Operations Research, Rey Juan Carlos University, Madrid, Spain
Entry Submitted: 07/17/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|