Optimization Online


An Effective Heuristic for Multistage Stochastic Linear Programming

C. Beltran-Royo (cesar.beltran***at***urjc.es)
L. F. Escudero (laureano.escudero***at***urjc.es)
J. F. Monge (monge***at***umh.es)
R. E. Rodriguez-Ravines (romy.elena***at***gmail.com)

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

Download: [PDF]

Entry Submitted: 07/17/2013
Entry Accepted: 07/17/2013
Entry Last Modified: 09/02/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society