×

A practicable robust counterpart formulation for decomposable functions: a network congestion case study. (English) Zbl 1455.90118

Summary: Robust optimization is a powerful means to handle optimization problems where there is a set of parameters that are uncertain. The effectiveness of the method is especially noticeable when these parameters are only known to lie inside some uncertainty region. Unfortunately, there are important computational considerations that have prevented the methodology from being fully adopted in fields of practice where the cost function that needs to be robustified is nonlinear with respect to such parameters. In this paper, we propose a new robust optimization formulation that circumvent the computational burden in problems where the cost decomposes as the sum of costs that each involve a single decision variable. This is done by exploiting the fact that in this formulation the worst-case cost function can be expressed as a convex combination between a nominal and an upper-bounding cost function. One can still control the conservatism of the robust solution by adjusting how many terms of this total cost can simultaneously reach their respective most pessimistic value. To demonstrate the potential of this “practicable robust counterpart” formulation, we present how it can be employed for the robust optimization of packet routing on a telecommunication network with congestion. In such problems, an important source of uncertainty stems from the queueing delay, which is usually approximated by a nonlinear convex function using the theory of M/M/1 queues. Computational results on a large number of problem instances of realistic size confirm that it is possible to identify robust solutions that significantly outperform a deterministic approach in terms of both the amount of congestion and the risks of excessive congestion. Moreover, our proposed method also improves significantly the quality of solutions that are obtained using two other natural approximation schemes.

MSC:

90C17 Robustness in mathematical programming
90B18 Communication networks in operations research
90B22 Queues and service in operations research

Software:

SNDlib
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Addis B, Capone A, Carello G, Gianoli LG, Sansò B (2013) A robust optimization approach for energy-aware routing in MPLS networks. Proc. Internat. Conf. Comput., Networking Comm., ICNC (IEEE Computer Society, Washington, DC), 567-572.Google Scholar
[2] Addis B, Capone A, Carello G, Gianoli LG, Sansò B (2014) On the energy cost of robustness and resiliency in IP networks. Comput. Networks 75, Part A:239-259.Crossref, Google Scholar · doi:10.1016/j.comnet.2014.10.004
[3] Altin A, Fortz B, Ümit H (2012) Oblivious OSPF routing with weight optimization under polyhedral demand uncertainty. Networks 60(2):132-139.Google Scholar · Zbl 1251.90076
[4] Altın A, Amaldi E, Belotti P, Pınar M (2007) Provisioning virtual private networks under traffic uncertainty. Networks 49(1):100-115.Crossref, Google Scholar · Zbl 1131.90012 · doi:10.1002/net.20145
[5] Ardestani-Jaafari A, Delage E (2014) The value of flexibility in robust location-transportation problem. Cahier du GERAD G-2014-83.Google Scholar
[6] Ardestani-Jaafari A, Delage E (2016) Robust optimization of sums of piecewise linear functions with application to inventory problems. Oper. Res. 64(2):474-494.Link, Google Scholar · Zbl 1342.90222
[7] Ben-Ameur W, Kerivin H (2005) Routing of uncertain traffic demands. Optim. Engrg. 6(3):283-313.Crossref, Google Scholar · Zbl 1166.90318 · doi:10.1007/s11081-005-1741-7
[8] Ben-Tal A, den Hertog D (2011) Immunizing conic quadratic optimization problems against implementation errors. Technical report, CentER Discussion Paper Series 2012-053.Google Scholar
[9] Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769-805.Link, Google Scholar · Zbl 0977.90052
[10] Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1-13.Crossref, Google Scholar · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4
[11] Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming 88(3):411-424.Crossref, Google Scholar · Zbl 0964.90025 · doi:10.1007/PL00011380
[12] Ben-Tal A, Nemirovski A (2002) Robust optimization—Methodology and applications. Math. Programming 92(3):453-480.Crossref, Google Scholar · Zbl 1007.90047 · doi:10.1007/s101070100286
[13] Ben-Tal A, Nemirovski A (2003) On approximate robust counterparts of uncertain semidefinite and conic quadratic programs. Sachs EW, Tichatschke R, eds. System Modeling and Optimization XX (Springer, New York), 1-22.Crossref, Google Scholar · Zbl 1095.90588 · doi:10.1007/978-0-387-35699-0_1
[14] Ben-Tal A, den Hertog D, Vial J-P (2012) Deriving robust counterparts of nonlinear uncertain inequalities. Technical report, CentER Discussion Paper Series 2012-053.Google Scholar
[15] Ben-Tal A, El Ghaoui L, Lebret H (1998) Robust semidefinite programming. Handbook on Semidefinite Programming, Vol. 27 (Springer, New York),.Google Scholar
[16] Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · Zbl 1221.90001 · doi:10.1515/9781400831050
[17] Bertsimas D, Brown DB (2009) Constructing uncertainty sets for robust linear optimization. Oper. Res. 57(6):1483-1495.Link, Google Scholar · Zbl 1228.90061
[18] Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1):49-71.Crossref, Google Scholar · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4
[19] Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35-53.Link, Google Scholar · Zbl 1165.90565
[20] Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464-501.Crossref, Google Scholar · Zbl 1233.90259 · doi:10.1137/080734510
[21] Bertsimas D, Gupta V, Kallus N (2014) Data-driven robust optimization. Preprint arXiv:1401.0212.Google Scholar
[22] Bertsimas D, Nohadani O, Teo KM (2010) Robust optimization for unconstrained simulation-based problems. Oper. Res. 58(1):161-178.Link, Google Scholar · Zbl 1226.90074
[23] Campi MC, Garatti S (2008) The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3):1211-1230.Crossref, Google Scholar · Zbl 1180.90235 · doi:10.1137/07069821X
[24] Coudert D, Koster AM, Phan TK, Tieves M (2013) Robust redundancy elimination for energy-aware routing. Proc. IEEE Internat. Conf. Green Comput. Comm. IEEE Internet of Things and IEEE Cyber, Physical Soc. Comput. (IEEE, Piscataway, NJ), 179-186.Google Scholar
[25] Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1(3-4):197-206.Link, Google Scholar · Zbl 0995.90589
[26] El Ghaoui L, Lebret H (1997) Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18(4):1035-1064.Crossref, Google Scholar · Zbl 0891.65039 · doi:10.1137/S0895479896298130
[27] Fortz B, Thorup M (2004) Increasing Internet capacity using local search. Comput. Optim. Appl. 29(1):13-48.Crossref, Google Scholar · Zbl 1069.90024 · doi:10.1023/B:COAP.0000039487.35027.02
[28] Gabrel V, Murat C, Thiele A (2014) Recent advances in robust optimization: An overview. Eur. J. Oper. Res. 235(3):471-483.Crossref, Google Scholar · Zbl 1305.90390 · doi:10.1016/j.ejor.2013.09.036
[29] Gendreau M, Sansò B, Stanford DA (1996) Optimizing routing in packet-switched networks with non-Poisson offered traffic. Telecomm. Systems-Modeling, Anal., Design and Management 5(2):323-340.Crossref, Google Scholar · doi:10.1007/BF02112521
[30] Gorissen BL, den Hertog D (2013) Robust counterparts of inequalities containing sums of maxima of linear functions. Eur. J. Oper. Res. 227(1):30-43.Crossref, Google Scholar · Zbl 1292.90316 · doi:10.1016/j.ejor.2012.10.007
[31] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169-197.Crossref, Google Scholar · Zbl 0492.90056 · doi:10.1007/BF02579273
[32] Hijazi H, Bonami P, Ouorou A (2013) Robust delay-constrained routing in telecommunications. Ann. Oper. Res. 206(1):163-181.Crossref, Google Scholar · Zbl 1271.90021 · doi:10.1007/s10479-013-1371-y
[33] Hiriart-Urruty J-B, Lemaréchal C (2001) Fundamentals of Convex Analysis, Grundlehren Text, ed. (Springer, Berlin).Crossref, Google Scholar · Zbl 0998.49001 · doi:10.1007/978-3-642-56468-0
[34] Hsiung KL, Kim SJ, Boyd S (2008) Tractable approximate robust geometric programming. Optim. Engrg. 9(2)95-118.Crossref, Google Scholar · Zbl 1176.90399 · doi:10.1007/s11081-007-9025-z
[35] Iancu DA, Trichakis N (2014) Pareto efficiency in robust optimization. Management Sci. 60(1):130-147.Link, Google Scholar
[36] Koenker R (2005) Quantile Regression (Cambridge University Press, New York).Crossref, Google Scholar · Zbl 1111.62037 · doi:10.1017/CBO9780511754098
[37] Li M, Gabriel SA, Shim Y, Azarm S (2011) Interval uncertainty-based robust optimization for convex and non-convex quadratic programs with applications in network infrastructure planning. Networks and Spatial Econom. 11(1):159-191.Crossref, Google Scholar · Zbl 1213.90191 · doi:10.1007/s11067-010-9150-7
[38] Mak H-Y, Rong Y, Zhang J (2015) Appointment scheduling with limited distributional information. Management Sci. 61(2):316-334.Link, Google Scholar
[39] Mattia S (2013) The robust network loading problem with dynamic routing. Computational Optim. Appl. 54(3):619-643.Crossref, Google Scholar · Zbl 1271.90099 · doi:10.1007/s10589-012-9500-0
[40] Mulyana E, Killat U (2005) Optimizing IP networks for uncertain demands using outbound traffic constraints. Proc. 2nd INOC, 695-701.Google Scholar
[41] Orlowski S, Wessäly R, Pióro M, Tomaszewski A (2010) Sndlib 1.0 survivable network design library. Networks 55(3):276-286.Google Scholar
[42] Ouorou A (2011) Affine decision rules for tractable approximations to robust capacity planning in telecommunications. Network Optimization (Springer, Berlin), 277-282.Crossref, Google Scholar · Zbl 1345.90037 · doi:10.1007/978-3-642-21527-8_32
[43] Ouorou A (2013) Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty. Comput. Oper. Res. 40(1):318-327.Crossref, Google Scholar · Zbl 1349.90187 · doi:10.1016/j.cor.2012.07.001
[44] Plante M, Sansò B (2002) A typology for multi-technology, multi-service broadband network synthesis. Telecomm. Systems 19(1):39-73.Crossref, Google Scholar · doi:10.1023/A:1012290229844
[45] Poss M, Raack C (2013) Affine recourse for the robust network design problem: Between static and dynamic routing. Networks 61(2):180-198.Crossref, Google Scholar · Zbl 1269.90025 · doi:10.1002/net.21482
[46] Restrepo JCC, Gruber CG, Machuca CM (2009) Energy profile aware routing. IEEE Internat. Conf. Comm. Workshops (IEEE, Piscataway, NJ), 1-5.Google Scholar
[47] Rockafellar RT (1997) Convex Analysis (Princeton University Press, Princeton, NJ).Google Scholar · Zbl 0932.90001
[48] Sansò B, Mellah H (2009) On reliability, performance and Internet power consumption. Proc. 7th Internat. Worshop Design Reliable Comm. Networks, DRCN ’09 (IEEE, Piscataway, NJ), 259-264.Google Scholar
[49] Shawe-Taylor J, Cristianini N (2003) Estimating the moments of a random vector with applications. Siemons J, ed. Proc. GRETSI 2003 Conf., 47-52.Google Scholar
[50] Soyster AL (1973) Technical note—Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5):1154-1157.Link, Google Scholar · Zbl 0266.90046
[51] Takeda A, Taguchi S, Tanaka T (2010) A relaxation algorithm with a probabilistic guarantee for robust deviation optimization. Comput. Optim. Appl. 47(1):1-31.Crossref, Google Scholar · Zbl 1226.90133 · doi:10.1007/s10589-008-9212-7
[52] Van Eijl CA (2002) Capacity planning for carrier-scale IP networks. BT Tech. J. 20(3):116-123.Crossref, Google Scholar · doi:10.1023/A:1020855928538
[53] Zeng B, · Zbl 1286.90143 · doi:10.1016/j.orl.2013.05.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.