Optimization Online


On Adaptive Multicut Aggregation for Two-Stage Stochastic Linear Programs with Recourse

Svyatoslav Trukhanov(slavik***at***tamu.edu)
Lewis Ntaimo(ntaimo***at***tamu.edu)
Andrew Schaefer(schaefer***at***ie.pitt.edu)

Abstract: Outer linearization methods for two-stage stochastic linear programs with recourse, such as the L-shaped algorithm,generally apply a single optimality cut on the nonlinear objective at each major iteration, while the multicut version of the algorithm allows for several cuts to be placed at once. In general, the L-shaped algorithm tends to have more major iterations than the multicut algorithm. However, the tradeoffs in terms of computational time is problem dependent. This paper investigates the computational trade-offs of adjusting the level of optimality cut aggregation from single cut to pure multicut. Specifically, an adaptive multicut algorithm that dynamically adjusts the aggregation level of the optimality cuts in the master program, is presented and tested on standard large scale instances from the literature. The computational results reveal that a cut aggregation level that is between the single cut and the multicut results in computational times of up to over 50% reduction compared to the single cut method.

Keywords: Stochastic programming, multicut aggregation, adaptive cuts

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 11/29/2007
Entry Accepted: 11/29/2007
Entry Last Modified: 11/29/2007

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 Programming Society