Abstract
We consider a general robust block-structured optimization problem, coming from applications in network and energy optimization. We propose and study an iterative cutting-plane algorithm, generic for a large class of uncertainty sets, able to tackle large-scale instances by leveraging on their specific structure. This algorithm combines known techniques (cutting-planes, proximal stabilizations, efficient heuristics, warm-started bundle methods) in an original way for better practical efficiency. We provide a theoretical analysis of the algorithm and connections to existing literature. We present numerical illustrations on real-life problems of electricity generation under uncertainty. These clearly show the advantage of the proposed regularized algorithm over classic cutting plane approaches. We therefore advocate that regularized cutting plane methods deserve more attention in robust optimization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bandi C, Bertsimas D (2012) Tractable stochastic analysis in high dimensions via robust optimization. Math Program 134(1):23–70
Ben Amor H, Desrosiers J, Frangioni A (2009) On the choice of explicit stabilizing terms in column generation. Discret Appl Math 157(6):1167–1184
Ben-Salem S (2011) Gestion Robuste de la production électrique à horizon court-terme. PhD thesis, Ecole Centrale Paris, Mars
Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math Oper Res 23(4):769–805
Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper Res Lett 25(1):1–13
Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton University Press, Princeton
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238–252
Bertsimas D, Sim M (2006) Tractable approximations to robust conic optimization problems. Math Program 107(1):5–36
Bertsimas D, Brown D, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464–501
Bertsimas D, Litvinov E, Sun XA, Zhao J, Zheng T (2013) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans Power Syst 28(1):52–63
Bertsimas D, Dunning I, Lubin M (2016) Reformulation versus cutting-planes for robust optimization. Comput Manag Sci 13(2):195–217
Borghetti A, Frangioni A, Lacalandra F, Nucci CA (2003) Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment. IEEE Trans Power Syst 18:313–323
Briant O, Lemaréchal C, Meurdesoif Ph, Michel S, Perrot N, Vanderbeck F (2008) Comparison of bundle and classical column generation. Math Program 113(2):299–344
Caroe CC, Tind J (1998) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math Program 83:451–464
Chatzipanagiotis N, Dentcheva D, Zavlanos MM (2015) An augmented lagrangian method for distributed optimization. Math Program 152(1):405–434
Clarke FH (1987) Optimisation and nonsmooth analysis. Society for Industrial and Applied Mathematics, Classics in applied mathematics
Codato G, Fischetti M (2006) Combinatorial benders’ cuts for mixed-integer linear programming. Oper Res 54(4):756–766
Correa R, Lemaréchal C (1993) Convergence of some algorithms for convex minimization. Math Program 62(2):261–275
de Oliveira W, Eckstein J (2015) A bundle method for exploiting additive structure in difficult optimization problems, pp 1–18. http://www.optimization-online.org/DB_HTML/2015/05/4935.html
de Oliveira W, Sagastizábal C (2014) Level bundle methods for oracles with on demand accuracy. Optim Methods Softw 29(6):1180–1209
de Oliveira W, Sagastizábal CA, Scheimberg S (2011) Inexact bundle methods for two-stage stochastic programming. SIAM J Optim 21(2):517–544
de Oliveira W, Sagastizábal C, Lemaréchal C (2014) Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math Prog Ser B 148:241–277
Dubost L, Gonzalez R, Lemaréchal C (2005) A primal-proximal heuristic applied to french unitcommitment problem. Math Program 104(1):129–151
El Ghaoui L, Lebret H (2006) Robust solutions to least-squares problems with uncertain data. SIAM J Matrix Anal Appl 18(4):1035–1064
El Ghaoui L, Oustry F, Lebret H (1998) Robust solutions to uncertain semidefinite programs. SIAM J Optim 9(1):33–52
Feltenmark S, Kiwiel KC (2000) Dual applications of proximal bundle methods, including lagrangian relaxation of nonconvex problems. SIAM J Optim 10(3):697–721
Frangioni A, Gentile C, Lacalandra F (2011) Sequential Lagrangian-MILP approaches for unit commitment problems. Int J Electr Power Energy Syst 33:585–593
Geoffrion AM (1972) Generalized benders decomposition. J Optim Theory Appl 10(4):237–260
Guo S, Xu H, Zhang L (2017) Convergence analysis for mathematical programs with distributionally robust chance constraint. SIAM J Optim 27(2):784–816
Hare W, Sagastizábal C, Solodov M (2016) A proximal bundle method for nonconvex functions with inexact oracles. Comput Optim Appl 63(1):1–28
Heitsch H, Römisch W (2007) A note on scenario reduction for two-stage stochastic programs. Oper Res Lett 35(6):731–738
Hiriart-Urruty JB, Lemaréchal C (1996a) Convex analysis and minimization algorithms II. Number 306 in Grundlehren der mathematischen Wissenschaften, 2nd edn. Springer, Berlin
Hiriart-Urruty JB, Lemaréchal C (1996b) Convex analysis and minimization algorithms I. Number 305 in Grundlehren der mathematischen Wissenschaften, 2nd edn. Springer, Berlin
Hooker JN, Ottosson G (2003) Logic-based benders decomposition. Math. Program 96:33–60
Kelley JE (1960) The cutting-plane method for solving convex programs. J Soc Ind Appl Math 8(4):703–712
Kiwiel KC (1986) A method for solving certain quadratic programming problems arising in non-smooth optimization. IMA J Numer Anal 6(2):137–152
Kiwiel KC (1994) A cholesky dual method for proximal piecewise linear programming. Numer Math 68:325–340
Kiwiel KC (2006) A proximal bundle method with approximate subgradient linearizations. SIAM J Optim 16(4):1007–1023
Kolokolov A, Kosarev N (2006) Analysis of decomposition algorithms with benders cuts for \(p\)-median problem. J Math Model Algorithms 5(2):189–199
Lemaréchal C (1975) An extension of davidon methods to nondifferentiable problems. Math Program Study 3:95–109
Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math Program 69(1):111–147
Malick J, de Oliveira W, Zaourar S (2017) Uncontrolled inexact information within bundle methods. EURO J Comput Optim 5(1):5–29
Minoux M (2014) Two-stage robust optimization, state-space representable uncertainty and applications. RAIRO-Oper Res 48:455–475
Pagès G, Printems J (2003) Optimal quadratic quantization for numerics: the Gaussian case. Monte Carlo Methods Appl 9(2):135–166
Rockafellar RT, Wets RJ-B (2009) Variational analysis, volume 317 of Grundlehren der mathematischen Wissenschaften, 3rd edn. Springer, Berlin
Sahiridis GKD, Minoux M, Ierapetritou MG (2010) Accelerating benders method using covering cut bundle generation. Int Trans Oper Res 17:221–237
Sherali HD, Lunday BJ (2013) On generating maximal nondominated benders cuts. Ann Oper Res 210(1):57–72
Song Y, Luedtke J (2015) An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. SIAM J Optim 25(3):1344–1367
Tahanan M, van Ackooij W, Frangioni A, Lacalandra F (2015) Large-scale unit commitment under uncertainty: a literature survey. 4OR 13(2):115–171
Takriti S, Birge JR (2000) Using integer programming to refine lagrangian-based unit commitment solutions. IEEE Trans Power Syst 15(1):151–156
van Ackooij W (2014) Decomposition approaches for block-structured chance-constrained programs with application to hydro-thermal unit commitment. Math Methods Oper Res 80(3):227–253
van Ackooij W (2017) A comparison of four approaches from stochastic programming for large-scale unit-commitment. EURO J Comput Optim 5(1):119–147
van Ackooij W, de Oliveira W (2014) Level bundle methods for constrained convex optimization with various oracles. Comput Optim Appl 57(3):555–597
van Ackooij W, Sagastizábal C (2014) Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J Optim 24(2):733–765
van Ackooij W, Frangioni A (2016) Incremental bundle methods using upper models. Submitted paper; Technical report, pp 1–25. http://eprints.adm.unipi.it/2357/
van Ackooij W, Malick J (2016) Decomposition algorithm for large-scale two-stage unit-commitment. Ann Oper Res 238(1):587–613
van Ackooij W, Henrion R, Möller A, Zorgati R (2014) Joint chance constrained programming for hydro reservoir management. Optim Eng 15:509–531
van Ackooij W, Frangioni A, de Oliveira W (2016a) Inexact stabilized Benders’ decomposition approaches: with application to chance-constrained problems with finite support. Comput Optim Appl 65(3):637–669
van Ackooij W, de Oliveira W, Song Y (2016b) An adaptive partition-based level decomposition for solving two-stage stochastic programs with fixed recourse. Informs J Comput 1–18 (to appear)
van Ackooij W, Berge V, de Oliveira W, Sagastizábal C (2017) Probabilistic optimization via approximate p-efficient points and bundle methods. Comput Oper Res 77:177–193
Van Dinter J, Rebenack S, Kallrath J, Denholm P, Newman A (2013) The unit commitment model with concave emissions costs: a hybrid benders’ decomposition with nonconvex master problems. Ann Oper Res 210(1):361–386
van Slyke RM, Wets RJ-B (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J Appl Math 17:638–663
Wentges P (1996) Accelerating benders’ decomposition for the capacitated facility location problem. Math Methods Oper Res 44(2):267–290
Yang Y, Lee JM (2012) A tighter cut generation strategy for acceleration of benders decomposition. Comput Chem Eng 44:84–93
Zakeri G, Philpott A, Ryan DM (2000) Inexact cuts in benders decomposition. SIAM J Optim 10(3):643–657
Zaourar S (2014) Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle. PhD thesis, University of Grenoble
Zaourar S, Malick J (2014) Quadratic stabilization of benders decomposition. Privately communicated, Draft submitted, pp 1–22
Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper Res Lett 41(5):457–461
Zverovich V, Fábián CI, Ellison EFD, Mitra G (2012) A computational study of a solver system for processing two-stage stochastic lps with enhanced benders decomposition. Math Program Comput 4(3):211–238
Acknowledgements
Part of this work was done during the second author’s internship at EDF R&D. The first and the third author gratefully acknowledge the support of PGMO project “advanced nonsmooth optimization methods for stochastic programming”.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: Brief overview of bundle methods in nonsmooth optimization
This appendix provides a brief description of bundle methods using standard notation and terminology, which are also the ones of this paper. For an in-depth description, we refer to the textbook (Hiriart-Urruty and Lemaréchal 1996b) and the recent article (de Oliveira et al. 2014).
We are interested in solving \(\min _{x} f(x)\), where \(f : \mathbb {R}^n \rightarrow \mathbb {R}\) is a nonsmooth convex mapping known through an “oracle” returning, for a given \(x \in \mathbb {R}^n\) as an input, the value f(x) and a subgradient \(g \in \partial f(x)\) (or approximations of them). Given a set of iterates \(x^1,\ldots ,x^k\) for which the oracle has been called, we can set up the cutting plane model \(\check{f}_k\) for f by defining
where \(g^\ell \in \partial f(x^\ell )\). The cutting-plane algorithm, which can be traced back to Kelley (1960), consists of defining the next iterate by solving \(\min _{x} \check{f}_k(x)\), which can be formulated as a linear problem.
The cutting-plane method suffers from various drawbacks (including stability and memory issues) and an improved scheme is available: regularized cutting-plane methods or so-called bundle methods, dating back to the seminal work of Lemaréchal (1975). These methods use a quadratic stabilization to ensure that the next iterate is not far from the best current iterate, called stability center \(\hat{x}\). The next iterate is the solution of
which is a convex quadratic program (easy to solve by specialized methods Kiwiel 1986, 1994). The predicted decrease \(\delta _k:= f(\hat{x}^k) - \check{f}_k(x^{k+1})\) is then used to update the stability center: if enough decrease is observed, i.e. the inequality
holds, the new iterate \(x^{k+1}\) becomes the new stability center \(\hat{x}^{k+1}\); Otherwise the information from the oracle is just used to improve the cutting plane model. From a variational analysis perspective, bundle methods are thus damped proximal algorithms where the inner proximal iterations are stopped whenever sufficient decrease is observed on f.
Note that the proximal parameter \(t_k\) is basically free: for exact oracles, convergence is guaranteed if \(t_k\) stays within bounds (see Correa and Lemaréchal 1993). In practice, \(t_k\) can be arbitrary if the stability center was changed; \(t_k\) should not increase if the stability center was not changed; \(t_k\) should strictly increase if the oracle is subject to imprecise calculations during noise detection steps [see e.g., van Ackooij and Sagastizábal 2014, eq. (2.16)]. A complete description of asymptotical rules can be found in van Ackooij and Frangioni (2016).
On top of stabilizing iterates, bundle methods also come up with the possibility of aggregating cutting-plane information into an aggregate cut. In theory, we can delete all but two cutting planes (the aggregate cut and the cut belonging to the current stability center).
Appendix B: Benders decomposition: terminology and references
The so-called Benders decomposition hinges on the observation that fixing some variables makes certain problems much easier. This observation, originally made for problems with an underlying linear structure (Benders 1962) potentially with stochastic aspects (Slyke and Wets 1969), was generalized to problems with some underlying convexity in the seminal work (Geoffrion 1972). We recall in this appendix the terminology and some important references about this classical method in operation research in a broad sense.
The slave problem consists in the resulting problem with the fixed variables. The master problem is related to finding the optimal allocation of the previously fixed variables. Since the domain of the value function need not be the whole space, the master problem is augmented with the so called feasibility cuts (i.e., an outer approximation of the convex domain of the value function). The master problem is also enriched with optimality cuts, as a matter of fact, a cutting-plane model of the value function. Benders algorithm is thus as a variant of the cutting-plane method, presented previously, and therefore subject to the well-known oscillation effect and slow convergence. Regularized Benders algorithms have been recently proposed (Zaourar and Malick 2014; van Ackooij et al. 2016a).
Many articles, including Sherali and Lunday (2013), Sahiridis et al. (2010), Wentges (1996), Van Dinter et al. (2013), Yang and Lee (2012) concretely deal with strategies for generating good (optimality) cuts, occasionally with a problem-dependent flavour. The authors of Codato and Fischetti (2006) are concerned with generating strong feasibility cuts and provide an important contribution in this view. Further improvements to the general scheme are concerned with a relaxation of the convexity assumption of the slave problem by allowing for integer variables (Caroe and Tind 1998) or the use of generalized “logic” duality (called inference duality) in Hooker and Ottosson (2003). In Zakeri et al. (2000), it is moreover suggested to inexactly solve the slave problem to compute some inexact but “cheap” cuts. In general, an appropriate choice of cuts (approximating the value function) is crucial, as illustrated in Kolokolov and Kosarev (2006).
Let us finally illustrate optimality and feasibility cuts more specifically on the following parametrized linear program:
The inequality system \(Wy \le b - Tx\) need not admit a solution for all x and that consequently \(\psi (x) = \infty \) may happen for some x. Minimizing the convex mapping \(\psi \) then amounts to handling also the hidden constraints \(x \in \mathrm {dom}\,{\psi }\). By strong duality, we have \(\psi (x) = \max _{\lambda \ge 0} \left\{ \lambda ^\mathsf {T}(b - Tx): W^\mathsf {T}\lambda \ge q\right\} \), so that any optimal dual multiplier \(\lambda ^*\) satisfies \(-T^\mathsf {T}\lambda ^* \in \partial \psi (x)\). When \(Wy \le b - Tx\) does not admit a feasible solution, by Farkas Lemma an unbounded ray can be identified and used to define an outer linearization for \(\mathrm {dom}\,{\psi }\). Note finally that, in the general non-linear situation, first order information about \(\psi \) can also be identified with tools from nonsmooth analysis (e.g., Rockafellar and Wets 2009, Theorem 10.13), but feasibility cuts will need to be derived by solving an auxiliary problem typically involving the minimization of slack variables.
Appendix C: A rich but computationally cheap model of uncertainty
For our numerical experiments, we choose to use the uncertainty set \(\mathcal {D}\) introduced by Minoux (2014). This so-called “state-space represented” model has a rich expressivity while being computationally easy to manipulate. This model has an exponential number of scenarios expressing temporal dependencies, while preserving a very fast computability by basic dynamic programming. We refer to Minoux (2014) more details and a complete analysis. This model is illustrated in Fig. 6. Yet, for the convenience of the reader, we describe here the main ideas briefly.
Illustration of the uncertainty model used in the numerical experiments
At each time step \(t \in \tau \), we set up a set of nodes \(E_t\) containing both a value for \(d_t\) and a weight \(w_t\). This set of nodes is assumed to be sorted according to increasing values for \(d_t\). Using this set of nodes we set up a graph (G, V), with \(G = \bigcup _{t \in \tau } E_t\), such that V connects all nodes in \(E_t\) to those in \(E_{t+1}\) that are not further apart than H, i.e., node \(i \in E_t\) is connected to node \(j \in E_{t+1}\) if and only if their local labels \(\left| \mathcal {L}(i)-\mathcal {L}(j) \right| \le H\). At least one of the nodes in \(E_t\) is assumed to have a zero weight and H is assumed to be such that each node is connected to the node of zero weight. The set \(\mathcal {D}\) is now given by all paths in (G, V) satisfying \(\sum _{t \in \tau } w_t \le W_\mathtt{max}\) for a given maximum budget of uncertainty \(W_\mathtt{max}\). As a consequence, \(\left| \mathcal {D} \right| \) is huge, but computing the sup over \(\mathcal {D}\) amounts to applying a simple 1-dimensional dynamic programming principle.
Rights and permissions
About this article
Cite this article
van Ackooij, W., Lebbe, N. & Malick, J. Regularized decomposition of large scale block-structured robust optimization problems. Comput Manag Sci 14, 393–421 (2017). https://doi.org/10.1007/s10287-017-0281-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-017-0281-x
Keywords
- Large scale block-structured problems
- Robust optimization
- Cutting-plane methods
- Bundle methods
- Unit-commitment