A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems. (English) Zbl 1440.90031

Summary: We consider a cutting-plane algorithm for solving mixed-integer semidefinite optimization (MISDO) problems. In this algorithm, the positive semidefinite (psd) constraint is relaxed, and the resultant mixed-integer linear optimization problem is solved repeatedly, imposing at each iteration a valid inequality for the psd constraint. We prove the convergence properties of the algorithm. Moreover, to speed up the computation, we devise a branch-and-cut algorithm, in which valid inequalities are dynamically added during a branch-and-bound procedure. We test the computational performance of our cutting-plane and branch-and-cut algorithms for three types of MISDO problem: random instances, computing restricted isometry constants, and robust truss topology design. Our experimental results demonstrate that, for many problem instances, our branch-and-cut algorithm delivered superior performance compared with general-purpose MISDO solvers in terms of computational efficiency and stability.


90C11 Mixed integer programming
90C22 Semidefinite programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41 (2009) · Zbl 1171.90476
[2] Aloise, D.; Hansen, P., A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering, Pesqui. Oper., 29, 3, 503-516 (2009)
[3] Anjos, Mf; Ghaddar, B.; Hupp, L.; Liers, F.; Wiegele, A.; Jünger, M.; Reinelt, G., Solving \(k\)-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method, Facets of Combinatorial Optimization, 355-386 (2013), Berlin: Springer, Berlin · Zbl 1317.90301
[4] Armbruster, M.; Fügenschuh, M.; Helmberg, C.; Martin, A., LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Math. Program. Comput., 4, 3, 275-306 (2012) · Zbl 1275.90053
[5] Baraniuk, Rg, Compressive sensing [lecture notes], IEEE Signal Process. Mag., 24, 4, 118-121 (2007)
[6] Benson, Sj; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim., 10, 2, 443-461 (2000) · Zbl 0997.90059
[7] Ben-Tal, A.; Nemirovski, A., Robust truss topology design via semidefinite programming, SIAM J. Optim., 7, 4, 991-1016 (1997) · Zbl 0899.90133
[8] Bertsimas, D.; Dunning, I.; Lubin, M., Reformulation versus cutting-planes for robust optimization, Comput. Manag. Sci., 13, 2, 195-217 (2016)
[9] Bertsimas, D.; King, A., Logistic regression: from art to science, Stat. Sci., 32, 3, 367-384 (2017) · Zbl 1442.62166
[10] Braun, G.; Fiorini, S.; Pokutta, S.; Steurer, D., Approximation limits of linear programs (beyond hierarchies), Math. Oper. Res., 40, 3, 756-772 (2015) · Zbl 1343.68308
[11] Cerveira, A.; Agra, A.; Bastos, F.; Gromicho, J., A new Branch and Bound method for a discrete truss topology design problem, Comput. Optim. Appl., 54, 1, 163-187 (2013) · Zbl 1267.90175
[12] Czyzyk, J.; Mesnier, Mp; Moré, Jj, The NEOS server, IEEE Comput. Sci. Eng., 5, 3, 68-75 (1998)
[13] Duran, Ma; Grossmann, Ie, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052
[14] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1-3, 327-349 (1994) · Zbl 0833.90088
[15] Foucart, S.; Lai, Mj, Sparsest solutions of underdetermined linear systems via \(\ell_q\)-minimization for \(0 < q \le 1\), Appl. Comput. Harmon. Anal., 26, 3, 395-407 (2009) · Zbl 1171.90014
[16] Gally, T., Pfetsch, M. E.: Computing restricted isometry constants via mixed-integer semidefinite programming. Optimization Online, http://www.optimization-online.org/DB_HTML/2016/04/5395.html (2016)
[17] Gally, T.; Pfetsch, Me; Ulbrich, S., A framework for solving mixed-integer semidefinite programs, Optim. Methods Softw., 33, 3, 594-632 (2018) · Zbl 1398.90109
[18] Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R. L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., Müller, B.: The SCIP optimization suite 5.0. Optimization Online, http://www.optimization-online.org/DB_HTML/2017/12/6385.html (2017)
[19] Horn, Ra; Johnson, Cr, Matrix Analysis (2013), Cambridge: Cambridge University Press, Cambridge
[20] Joshi, S.; Boyd, S., Sensor selection via convex optimization, IEEE Trans. Signal Process., 57, 2, 451-462 (2009) · Zbl 1391.90679
[21] Kelley, Je Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104
[22] Konno, H.; Gotoh, J.; Uno, T.; Yuki, A., A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis, J. Comput. Appl. Math., 146, 1, 141-154 (2002) · Zbl 1007.65042
[23] Konno, H.; Kawadai, N.; Tuy, H., Cutting plane algorithms for nonlinear semi-definite programming problems with applications, J. Glob. Optim., 25, 2, 141-155 (2003) · Zbl 1030.90078
[24] Krishnan, K.; Mitchell, Je, A unifying framework for several cutting plane methods for semidefinite programming, Optim. Methods Softw., 21, 1, 57-74 (2006) · Zbl 1181.90215
[25] Löfberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design, pp. 284-289 (2004)
[26] Lubin, M.; Yamangil, E.; Bent, R.; Vielma, Jp, Polyhedral approximation in mixed-integer convex optimization, Math. Program., 172, 1, 139-168 (2018) · Zbl 1401.90158
[27] Manousakis, N. M., Korres, G. N.: Semidefinite programming for optimal placement of PMUs with channel limits considering pre-existing SCADA and PMU measurements. In: Proceedings of the 2016 Power Systems Computation Conference, pp. 1-7 (2016)
[28] Mittelmann, Hd, An independent benchmarking of SDP and SOCP solvers, Math. Program., 95, 2, 407-430 (2003) · Zbl 1030.90080
[29] Noyan, N.; Balcik, B.; Atakan, S., A stochastic optimization model for designing last mile relief networks, Trans. Sci., 50, 3, 1092-1113 (2015)
[30] Peng, J.; Xia, Y.; Chu, W.; Young Lin, T., A new theoretical framework for k-means-type clustering, Foundations and Advances in Data Mining, 79-96 (2005), Berlin: Springer, Berlin · Zbl 1085.68132
[31] Philipp, A., Ulbrich, S., Cheng, Y., Pesavento, M.: Multiuser downlink beamforming with interference cancellation using a SDP-based branch-and-bound algorithm. In: Proceedings of the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 7724-7728 (2014)
[32] Quesada, I.; Grossmann, Ie, An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 10-11, 937-947 (1992)
[33] Rendl, F.; Jünger, M., Semidefinite relaxations for integer programming, 50 Years of Integer Programming 1958-2008, 687-726 (2010), Berlin: Springer, Berlin · Zbl 1187.90003
[34] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program., 121, 2, 307-335 (2010) · Zbl 1184.90118
[35] Rowe, C., Maciejowski, J.: An efficient algorithm for mixed integer semidefinite optimisation. In: Proceedings of the 2003 American Control Conference, vol. 6, pp. 4730-4735 (2003)
[36] Sotirov, R.; Anjos, M.; Lasserre, J., SDP relaxations for some combinatorial optimization problems, Handbook on Semidefinite, Conic and Polynomial Optimization, 795-819 (2012), Boston: Springer, Boston · Zbl 1334.90116
[37] Tamura, R.; Kobayashi, K.; Takano, Y.; Miyashiro, R.; Nakata, K.; Matsui, T., Best subset selection for eliminating multicollinearity, J. Oper. Res. Soc. Jpn., 60, 3, 321-336 (2017) · Zbl 1382.90068
[38] Taylor, Ja; Luangsomboon, N.; Fooladivanda, D., Allocating sensors and actuators via optimal estimation and control, IEEE Trans. Control Syst. Technol., 25, 3, 1060-1067 (2017)
[39] Todd, Mj, Semidefinite optimization, Acta Numer., 10, 515-560 (2001) · Zbl 1105.65334
[40] Torchio, M., Magni, L., Raimondo, D.M.: A mixed integer SDP approach for the optimal placement of energy storage devices in power grids with renewable penetration. In: Proceedings of the American Control Conference, pp. 3892-3897 (2015)
[41] Tóth, Sf; Mcdill, Me; Könnyü, N.; George, S., Testing the use of lazy constraints in solving area-based adjacency formulations of harvest scheduling models, For. Sci., 59, 2, 157-176 (2013)
[42] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 1, 49-95 (1996) · Zbl 0845.65023
[43] Williams, Hp, Model Building in Mathematical Programming (2013), Hoboken: Wiley, Hoboken
[44] Westerlund, T.; Pettersson, F., An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136 (1995)
[45] Yamashita, M.; Fujisawa, K.; Kojima, M., Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0), Optim. Methods Softw., 18, 4, 491-505 (2003) · Zbl 1106.90366
[46] Yokoyama, R.; Shinano, Y.; Taniguchi, S.; Ohkura, M.; Wakui, T., Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation, Energy Convers. Manag., 92, 92-104 (2015)
[47] Yonekura, K.; Kanno, Y., Global optimization of robust truss topology via mixed integer semidefinite programming, Optim. Eng., 11, 3, 355-379 (2010) · Zbl 1273.74393
[48] Zhang, Y.; Shen, S.; Erdogan, Sa, Solving 0-1 semidefinite programs for distributionally robust allocation of surgery blocks, Optim. Lett., 12, 7, 1503-1521 (2018) · Zbl 1407.90246
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.