Optimization Online


Multicut decomposition methods with cut selection for multistage stochastic programs

Vincent Guigues (vincent.guigues***at***gmail.com)
Michelle Bandarra (michelle.bandarra***at***gmail.com)

Abstract: We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates strategies to select the most relevant cuts of the approximate recourse functions. We prove the convergence of the method in a finite number of iterations and use it to solve six portfolio problems with direct transaction costs under return uncertainty and six inventory management problems under demand uncertainty. On all problem instances CuSMuDA is much quicker than MuDA: between 5.1 and 12.6 times quicker for the porfolio problems considered and between 6.4 and 15.7 times quicker for the inventory problems.

Keywords: Stochastic programming; Stochastic Dual Dynamic Programming; Multicut Decomposition Algorithm; Portfolio selection; Inventory management

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 05/24/2017
Entry Accepted: 05/26/2017
Entry Last Modified: 03/01/2018

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