Optimization Online


A solution algorithm for chance-constrained problems with integer second-stage recourse decisions

Andrea Lodi(andrea.lodi***at***polymtl.ca)
Enrico Malaguti(enrico.malaguti***at***unibo.it)
Michele Monaci(michele.monaci***at***unibo.it)
Giacomo Nannicini(nannicini***at***us.ibm.com)
Paolo Paronuzzi(paolo.paronuzzi***at***unibo.it)

Abstract: We study a class of chance-constrained two-stage stochastic optimization problems where the second-stage recourse decisions belong to mixed-integer convex sets. Due to the nonconvexity of the second-stage feasible sets, standard decomposition approaches cannot be applied. We develop a provably convergent branch-and-cut scheme that iteratively generates valid inequalities for the convex hull of the second-stage feasible sets, resorting to spatial branching when cutting no longer suffices. We show that this algorithm attains an approximate notion of convergence, whereby the feasible sets are relaxed by some positive tolerance epsilon. Computational results on chance-constrained resource planning problems indicate that our implementation of the proposed algorithm is highly effective in solving this class of problems, compared to a state-of-the-art MIP solver and to a naive decomposition scheme.

Keywords: Chance-constrained mathematical program; Outer approximation; Branch-and-Cut; Convergence analysis; Computational experiments

Category 1: Stochastic Programming

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


Download: [PDF]

Entry Submitted: 07/23/2021
Entry Accepted: 07/23/2021
Entry Last Modified: 07/23/2021

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