Motivated by a class of chance-constrained optimization problems, we explore modifications of the (generalized) Benders' decomposition approach. The chance-constrained problems we consider involve a random variable with an underlying discrete distribution, are convex in the decision variable, but their probabilistic constraint is neither separable nor linear. The variants of Benders' approach we propose exploit advances in cutting-plane procedures developed for the convex case. Specifically, the approach is stabilized in the two ways; via a proximal term/trust region in the L1 norm, or via a level constraint. Furthermore, the approaches can use inexact oracles, in particular informative on-demand inexact ones. The simultaneous use of the two features requires a nontrivial convergence analysis; we provide it under what would seem to be the weakest possible assumptions on the handling of the two parameters controlling the oracle (target and accuracy), strengthening earlier know results. Numerical performance of the approaches are assessed on a class of hybrid robust and chance-constrained conic problems. The numerical results show that the approach has potential, especially for instances that are difficult to solve with standard techniques.
Inexact Stabilized Benders' Decomposition Approaches to Chance-constrained Problems with Finite Support
A Frangioni;
2015
Abstract
Motivated by a class of chance-constrained optimization problems, we explore modifications of the (generalized) Benders' decomposition approach. The chance-constrained problems we consider involve a random variable with an underlying discrete distribution, are convex in the decision variable, but their probabilistic constraint is neither separable nor linear. The variants of Benders' approach we propose exploit advances in cutting-plane procedures developed for the convex case. Specifically, the approach is stabilized in the two ways; via a proximal term/trust region in the L1 norm, or via a level constraint. Furthermore, the approaches can use inexact oracles, in particular informative on-demand inexact ones. The simultaneous use of the two features requires a nontrivial convergence analysis; we provide it under what would seem to be the weakest possible assumptions on the handling of the two parameters controlling the oracle (target and accuracy), strengthening earlier know results. Numerical performance of the approaches are assessed on a class of hybrid robust and chance-constrained conic problems. The numerical results show that the approach has potential, especially for instances that are difficult to solve with standard techniques.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.