Optimization Online


Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems

Kibaek Kim (kimk***at***anl.gov)
Brian Dandurand (bdandurand***at***anl.gov)

Abstract: We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions of the Dantzig-Wolfe reformulation of the restricted master problem; and 2) using a more comprehensive (yet simple) measure for the dispersions associated with subproblem solution infeasibility. We prove that the proposed branching process leads to an algorithm that terminates finitely with optimal solutions feasible within a tolerance. We have implemented our new branching method, as well as the Caro e-Schultz method and a branch-and-price method. Using SIPLIB test instances, we present extensive numerical results to demonstrate that the proposed branching method yields significant reductions in the number of node subproblems and solution times.

Keywords: stochastic mixed-integer programming; branch-and-bound; dual decomposition; parallel computing

Category 1: Stochastic Programming

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

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Argonne National Laboratory, 10/2018

Download: [PDF]

Entry Submitted: 10/17/2018
Entry Accepted: 10/17/2018
Entry Last Modified: 02/19/2020

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