Optimization Online


Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs

Shabbir Ahmed (sahmed***at***isye.gatech.edu)
James Luedtke (jrluedt1***at***wisc.edu)
Yongjia Song (ysong3***at***vcu.edu)
Weijun Xie (wxie33***at***gatech.edu)

Abstract: We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.

Keywords: Chance constraints, Lagrangian duality, Nonanticipative relaxations

Category 1: Stochastic Programming

Citation: Working paper.

Download: [PDF]

Entry Submitted: 07/17/2014
Entry Accepted: 07/17/2014
Entry Last Modified: 01/23/2016

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