Optimization Online


A Stabilised Scenario Decomposition Algorithm Applied to Stochastic Unit Commitment Problems

Tim Schulze (t.schulze-2***at***sms.ed.ac.uk)
Andreas Grothey (a.grothey***at***ed.ac.uk)
Ken McKinnon (k.mckinnon***at***ed.ac.uk)

Abstract: In recent years the expansion of energy supplies from volatile renewable sources has triggered an increased interest in stochastic optimization models for hydro-thermal unit commitment. Several studies have modelled this as a two-stage or multi-stage stochastic mixed-integer optimization problem. Solving such problems directly is computationally intractable for large instances, and alternative approaches are required. In this paper we use a Dantzig-Wolfe reformulation to decompose the stochastic problem by scenarios. We derive and implement a column generation method with dual stabilisation1 and novel primal and dual initialisation techniques. A fast, novel schedule combination heuristic is used to construct very good primal solutions, and numerical results show that knowing these from the start improves the convergence of the column generation method significantly. We test our method on a central scheduling model based on the British National Grid and illustrate that convergence to within 0.1% of optimality can be achieved quickly.

Keywords: Stochastic unit commitment, Dantzig-Wolfe decomposition, Lagrangian relaxation, mixed-integer column generation, proximal bundle methods, heuristics

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical report ERGO 15-009, July 2015, The University of Edinburgh, School of Mathematics, Peter Guthrie Tait Road, Edinburgh, EH9 3FD, United Kingdom

Download: [PDF]

Entry Submitted: 07/06/2015
Entry Accepted: 07/06/2015
Entry Last Modified: 02/04/2017

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