A multiplicative weights update algorithm for MINLP. (English) Zbl 1396.90050
Summary: We discuss an application of the well-known multiplicative weights update (MWU) algorithm to non-convex and mixed-integer non-linear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of Markowitz’ portfolio selection problems. The interest of the MWU with respect to one of its closest competitors (classic multi-start) is that it provides a relative approximation guarantee on a certain quality measure of the solution.
Keywords:
multiplicative weights update algorithm; distance geometry problem; hydro unit commitment problemReferences:
| [1] | Arora S, Hazan E, Kale S (2005) Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In: Foundations of Computer Science, vol 46. FOCS, IEEE, New York, pp 339-348 · Zbl 1014.91053 |
| [2] | Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: a meta-algorithm and applications. Theory Comput 8:121-164 · Zbl 1283.68414 · doi:10.4086/toc.2012.v008a006 |
| [3] | Bahr A, Leonard J, Fallon M (2009) Cooperative localization for autonomous underwater vehicles. Int J Robot Res 28(6):714-728 · doi:10.1177/0278364908100561 |
| [4] | Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069-1072 · doi:10.1057/jors.1990.166 |
| [5] | Beasley JE (1996) Obtaining test problems via internet. J Glob Optim 8(4):429-433 · Zbl 0848.90126 · doi:10.1007/BF02404002 |
| [6] | Beeker, N.; Gaubert, S.; Glusa, C.; Liberti, L.; Mucherino, A. (ed.); Lavor, C. (ed.); Liberti, L. (ed.); Maculan, N. (ed.), Is the distance geometry problem in NP? (2013), New York · Zbl 1271.68111 |
| [7] | Berman H, Westbrook J, Feng Z, Gilliland G, Bhat T, Weissig H, Shindyalov IN, Bourne P (2000) The protein data bank. Nucl Acid Res 28:235-242 · doi:10.1093/nar/28.1.235 |
| [8] | Bienstock D (1996) Computational study of a family of mixed-integer quadratic programming problems. Math Program 74(2):121-140 · Zbl 0855.90090 · doi:10.1007/BF02592208 |
| [9] | Bonami P, Lee J (2007) BONMIN user’s manual. Technical report, IBM Corporation |
| [10] | Bonami P, Lee J, Leyffer S, Waecher A (2011) More Branch-and-Bound experiments in convex nonlinear integer programming. Preprint ANL/MCS-P1949-0911. Argonne National Laboratory, Mathematics and Computer Science Division · Zbl 1032.91074 |
| [11] | Borghetti A, D’Ambrosio C, Lodi A, Martello S (2015) Optimal scheduling of a multiunit hydro power station in a short-term planning horizon. In: Murty KG (ed) Case studies in operations research. International series in operations research & management science, vol 212, pp 167-181. Springer, New York · Zbl 0981.90063 |
| [12] | Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [13] | Chang T-J, Meade N, Beasley JE, Sharaiha YM (2000) Heuristics for cardinality constrained portfolio optimization. Comput Oper Res 27(13):1271-1302 · Zbl 1032.91074 · doi:10.1016/S0305-0548(99)00074-X |
| [14] | COIN-OR (2006) Introduction to IPOPT: a tutorial for downloading, installing, and using IPOPT · Zbl 0848.90126 |
| [15] | Costa A, Hansen P, Liberti L (2010) Formulation symmetries incircle packing. In: Mahjoub R (ed) Proceedings of the international symposium on combinatorial optimization. Electronic notes in discrete mathematics, vol 36. Elsevier, Amsterdam, pp 1303-1310 · Zbl 1274.90500 |
| [16] | D’Ambrosio C, Ky Vu, Lavor C, Liberti L, Maculan N (2014) Solving distance geometry problems with interval data using formulation-based methods. Technical report, LIX Ecole Polytechnique (working paper) · Zbl 1358.05085 |
| [17] | D’Ambrosio C, Mencarelli L (2014) Complex portfolio selection via convex mixed-integer quadratic approaches: a survey. Technical report, LIX, École Polytechnique (working paper) · Zbl 1162.90531 |
| [18] | Ding Y, Krislock N, Qian J, Wolkowicz H (2010) Sensor network localization, Euclidean distance matrix completions, and graph realization. Optim Eng 11:45-66 · Zbl 1273.74387 · doi:10.1007/s11081-008-9072-0 |
| [19] | Du H, Alechina N, Stock K, Jackson M (2013) The logic of NEAR andFAR. In: Tenbrink T et al (ed) COSIT. LNCS, vol 8116. Springer, Switzerland, pp 475-494 |
| [20] | Fischetti M, Lodi A (2003) Local branching. Math Program Ser B 98(1-3):23-47 · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5 |
| [21] | Frangioni A, Gentile C (2006) Perspective cuts for a class of convex 0-1 mixed integer programs. Math Program Ser A 106(2):225-236 · Zbl 1134.90447 · doi:10.1007/s10107-005-0594-3 |
| [22] | Gupta OK, Ravindran A (1985) Branch-and-Bound experiments in convex nonlinear integer programming. Manag Sci 31(12):1533-1546 · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533 |
| [23] | Hansen P, Mladenović N (2001) Variable neighbourhood search: principles and applications. Eur J Oper Res 130:449-467 · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4 |
| [24] | IBM (2010) ILOG CPLEX 12.2 User’s Manual, IBM |
| [25] | Kannan R, Monma CL (1978) On the computational complexity of integer programming problems. In: Henn R, Korte B, Oettli W (eds) Optimization and operations research. Lecture notes in economics and mathematical systems, vol 157, pp 161-172. Springer, Berlin · Zbl 0409.90066 |
| [26] | Konno H, Wijayanayake A (2001) Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints. Math Program Ser B 89(2):233-250 · Zbl 1014.91053 · doi:10.1007/PL00011397 |
| [27] | Lavor, C.; Liberti, L.; Maculan, N.; Pintér, J. (ed.), Computational experience with the molecular distance geometry problem, 213-225 (2006), Berlin · Zbl 1129.90389 · doi:10.1007/0-387-30927-6_9 |
| [28] | Liberti L (2009) Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43(1):55-86 · Zbl 1158.90390 · doi:10.1051/ro/2009005 |
| [29] | Liberti L, Lavor C, Maculan N, Mucherino A (2014) Euclidean distance geometry and applications. SIAM Rev 56(1):3-69 · Zbl 1292.51010 · doi:10.1137/120875909 |
| [30] | Malliavin, T.; Mucherino, A.; Nilges, M.; Mucherino, A. (ed.); Lavor, C. (ed.); Liberti, L. (ed.); Maculan, N. (ed.), Distance geometry in structural biology (2013), New York · Zbl 1366.92095 |
| [31] | Maniezzo V, Stützle T, Voß S (eds) (2009) Hybridizing metaheuristics and mathematical programming. Annals of information systems, vol 10. Springer, New York · Zbl 1179.90007 |
| [32] | Markowitz HM (1952) Portfolio selection. J Finan 7(1):77-91 |
| [33] | Plotkin S, Shmoys D, Tardos É (1995) Fast approximation algorithm for fractional packing and covering problems. Math Oper Res 20:257-301 · Zbl 0837.90103 · doi:10.1287/moor.20.2.257 |
| [34] | Saxe J (1979) Embeddability of weighted graphs in \[k\] k-space is strongly NP-hard. In: Proceedings of 17th Allerton conference in communications, control and computing, pp 480-489 · Zbl 1134.90447 |
| [35] | Scherer B, Martin D (2005) Introduction to modern portfolio optimization. Springer, Berlin · Zbl 1104.90002 · doi:10.1007/978-0-387-27586-4 |
| [36] | Schlick T (2002) Molecular modelling and simulation: an interdisciplinary guide. Springer, New York · Zbl 1011.92019 · doi:10.1007/978-0-387-22464-0 |
| [37] | Shaw DK, Liu S, Kopman L (2008) Lagrangian relaxation procedure for cardinality-constrained portfolio optimization. Optim Methods Softw 23(3):411-420 · Zbl 1162.90531 · doi:10.1080/10556780701722542 |
| [38] | Singer A (2011) Angular synchronization by eigenvectors and semidefinite programming. Appl Comput Harmonic Anal 30:20-36 · Zbl 1206.90116 · doi:10.1016/j.acha.2010.02.001 |
| [39] | Sun X, Zheng X, Li D (2013) Recent advances in mathematical programming with semi-continuous variables and cardinality constraint. J Oper Res Soc China 1(1):55-77 · Zbl 1277.90001 · doi:10.1007/s40305-013-0004-0 |
| [40] | Tahanan M, van Ackooij W, Frangioni A, Lacalandra F (2015) Large-scale unit commitment under uncertainty: a literature survey. 4OR 13:115-171 · Zbl 1321.90007 · doi:10.1007/s10288-014-0279-y |
| [41] | Xue H-G, Xu G-X, Feng Z-X (2006) Mean-variance portfolio optimal problem under concave transaction cost. Appl Math Comput 174(1):1-12 · Zbl 1168.91406 |
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.
