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 e. 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.

Lodi, A., Malaguti, E., Monaci, M., Nannicini, G., Paronuzzi, P. (2023). A solution algorithm for chance-constrained problems with integer second-stage recourse decisions. MATHEMATICAL PROGRAMMING, Early Access, 1-33 [10.1007/s10107-023-01984-y].

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

Lodi, Andrea;Malaguti, Enrico;Monaci, Michele;Paronuzzi, Paolo
2023

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 e. 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.
2023
Lodi, A., Malaguti, E., Monaci, M., Nannicini, G., Paronuzzi, P. (2023). A solution algorithm for chance-constrained problems with integer second-stage recourse decisions. MATHEMATICAL PROGRAMMING, Early Access, 1-33 [10.1007/s10107-023-01984-y].
Lodi, Andrea; Malaguti, Enrico; Monaci, Michele; Nannicini, Giacomo; Paronuzzi, Paolo
File in questo prodotto:
File Dimensione Formato  
a solution algorithm for chance constrained problems post print.pdf

Open Access dal 16/06/2024

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 580.73 kB
Formato Adobe PDF
580.73 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/962521
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact