×

A framework for solving mixed-integer semidefinite programs. (English) Zbl 1398.90109

Summary: Mixed-integer semidefinite programs (MISDPs) arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components such as dual fixing, branching rules, and primal heuristics are presented. We show the applicability of an implementation of the proposed methods on three kinds of problems. The results show the positive computational impact of the different solver components, depending on the semidefinite programming solver used. This demonstrates that practically relevant MISDPs can successfully be solved using a general purpose solver.

MSC:

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

References:

[1] Achterberg, T., Constraint Integer Programming, PhD thesis, TU Berlin, 2007. · Zbl 1430.90427
[2] Achterberg, T., SCIP: Solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[3] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 42-54 (2004) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[4] Alon, U.; Barkai, N.; Notterman, D. A.; Gish, K.; Ybarra, S.; Mack, D.; Levine, A. J., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Proc.Nat. Acad. Sci. USA, 96, 6745-6750 (1999) · doi:10.1073/pnas.96.12.6745
[5] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; Mckenney, A.; Sorensen, D., LAPACK Users’ Guide (1999), SIAM: SIAM, Philadelphia, PA · Zbl 0934.65030
[6] Anjos, M.F., Ghaddar, B., Hupp, L., Liers, F., and Wiegele, A., Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method, in Facets of Combinatorial Optimization - Festschrift for Martin Grötschel, M. Jünger and G. Reinelt, eds., Springer, Berlin, 2013, pp. 355-386. · Zbl 1317.90301
[7] 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 · doi:10.1007/s12532-012-0040-5
[8] Atamtürk, A.; Narayanan, V., Conic mixed-integer rounding cuts, Math. Program., 122, 1, 1-20 (2010) · Zbl 1184.90112 · doi:10.1007/s10107-008-0239-4
[9] Bellman, R. and Fan, K., On systems of linear inequalities in Hermitian matrix variables, in Convexity, Proceedings of Symposia in Pure Mathematics, Vol. 7, American Mathematical Society, Providence, RI, V.L. Klee, ed., 1963, pp. 1-11. · Zbl 0148.26001
[10] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton University Press · Zbl 1221.90001
[11] Ben-Tal, A.; Nemirovski, A., Robust truss topology design via semidefinite programming, SIAM J. Optim., 7, 4, 991-1016 (1997) · Zbl 0899.90133 · doi:10.1137/S1052623495291951
[12] Bendsøe, M. P.; Sigmund, O., Topology Optimization: Theory, Methods and Applications (2003), Springer: Springer, Berlin · Zbl 0957.74037
[13] Benson, H. Y.; Shanno, D. F., An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl., 38, 8, 371-399 (2007) · Zbl 1171.90546 · doi:10.1007/s10589-007-9048-6
[14] Benson, S. J.; Ye, Y., Algorithm 875: DSDP5-software for semidefinite programming, ACM Trans. Math. Softw., 34, 4, Article 16, 20 pages (2008) · Zbl 1291.65173
[15] Berthold, T., Heuristic algorithms in global MINLP solvers, PhD thesis, TU Berlin, 2014.
[16] Berthold, T., RENS - the optimal rounding, Math. Program. Comput., 6, 1, 33-54 (2014) · Zbl 1304.90147 · doi:10.1007/s12532-013-0060-9
[17] Berthold, T., Heinz, S., Pfetsch, M.E., and Vigerske, S., Large neighborhood search beyond MIP, in Proceedings of the 9th Metaheuristics International Conference (MIC 2011), D. Gaspero, A. Schaerf, and T. Stützle, eds., Dipartimento di Ingegneria Elettrica, Gestionale e Meccanica - Università degli Studi di Udine, Udine, 2011, pp. 51-60.
[18] Borwein, J.; Wolkowicz, H., Regularizing the abstract convex program, J. Math. Anal. Appl., 83, 2, 495-530 (1981) · Zbl 0467.90076 · doi:10.1016/0022-247X(81)90138-4
[19] 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 · doi:10.1287/moor.2014.0694
[20] Çezik, M. T.; Iyengar, G., Cuts for mixed 0−1 conic programming, Math. Program., 104, 179-202 (2005) · Zbl 1159.90457 · doi:10.1007/s10107-005-0578-3
[21] Dakin, R. J., A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 3, 250-255 (1965) · Zbl 0154.42004 · doi:10.1093/comjnl/8.3.250
[22] Danna, E.; Rothberg, E.; Pape, C. L., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 1, 71-90 (2004) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7
[23] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[24] Drewes, S.; Pokutta, S., Symmetry-exploiting cuts for a class of mixed-0/1 second-order cone programs, Discret. Optim., 13, 23-35 (2014) · Zbl 1308.90109 · doi:10.1016/j.disopt.2014.04.002
[25] Eisenblätter, A., Frequency Assignment in GSM Networks: Models, heuristics, and lower bounds, PhD thesis, TU Berlin, 2001.
[26] Eisenblätter, A., The semidefinite relaxation of the k-partition polytope is strong, in Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, W.J. Cook and A.S. Schulz, eds., Lecture Notes in Computer Science 2337, Springer, Berlin, 2002, pp. 273-290. · Zbl 1049.90136
[27] Ferreira, C. E.; Martin, A.; De Souza, C. C.; Weismantel, R.; Wolsey, L. A., The node capacitated graph partitioning problem: A computational study, Math. Program., 81, 229-256 (1998) · Zbl 0919.90139
[28] Ferreira, C.E., Martin, A., De Souza, C.C., Weismantel, R., and Wolsey, L.A., The node capacitated graph partitioning problem – benchmark instances. Available at . Accessed March 2016.
[29] Fischetti, M.; Lodi, A., Local branching, Math. Program. Ser. B, 98, 1-3, 23-47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[30] Fischetti, M. and Lodi, A., Heuristics in mixed integer programming, in Wiley Encyclopedia of Operations Research and Management Science, J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh, and J.C. Smith, eds., John Wiley & Sons, New York, 2010.
[31] Friberg, H.A., Facial reduction heuristics and the motivational example of mixed-integer conic optimization, Technical report, Optimization-Online, 2016.
[32] Gamrath, G., Fischer, T., Gally, T., Gleixner, A.M., Hendel, G., Koch, T., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J.T., and Witzig, J., The SCIP optimization suite 3.2, Technical report, ZIB-Report (15-60), 2016.
[33] Ghaddar, B.; Anjos, M. F.; Liers, F., A semidefinite programming branch-and-cut algorithm for the minimum k-partition problem, Ann. Oper. Res., 188, 1, 155-174 (2011) · Zbl 1225.90144 · doi:10.1007/s10479-008-0481-4
[34] Ghosh, S., DINS, a MIP improvement heuristic, in Integer Programming and Combinatorial Optimization (IPCO 2007), M. Fischetti and D.P. Williamson, eds., Lecture Notes in Computer Science, Vol. 4513, Springer, Berlin, 2007, pp. 310-323. · Zbl 1136.90419
[35] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42, 1115-1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[36] Gondzio, J., Warm start of the primal-dual method applied in the cutting plane scheme, Math. Program., 83, 1, 125-143 (1998) · Zbl 0920.90102
[37] Helmberg, C., Fixing variables in semidefinite relaxations, SIAM J. Matrix Anal. Appl., 21, 3, 952-969 (2000) · Zbl 0961.90075 · doi:10.1137/S089547989631442X
[38] Helmberg, C., Semidefinite programming for combinatorial optimization. Habilitationsschrift, TU Berlin, ZIB-Report ZR-00-34, Zuse-Institue Berlin, January 2000.
[39] Helmberg, C.; Rendl, F., Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Math. Program., 82, 291-315 (1998) · Zbl 0919.90112
[40] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM J. Optim., 10, 3, 673-696 (2000) · Zbl 0960.65074 · doi:10.1137/S1052623497328987
[41] Hocking, R. R., The analysis and selection of variables in linear regression, Biometrics, 32, 1, 1-49 (1976) · Zbl 0328.62042 · doi:10.2307/2529336
[42] Kann, V.; Khanna, S.; Lagergren, J.; Panconesi, A., On the hardness of approximating MAX k-CUT and its dual, Chicago J. Theoret. Comput. Sci., 1997, 2, 1-18 (1997) · Zbl 0924.68013 · doi:10.4086/cjtcs.1997.002
[43] Krishnan, K. and Mitchell, J.E., A linear programming approach to semidefinite programming problems, Technical report, Dept. of Mathematical Sciences, RPI, Troy, 2001.
[44] Krishnan, K.; Mitchell, J. E., A unifying framework for several cutting plane methods for semidefinite programming, Optim. Methods Softw., 21, 1, 57-74 (2006) · Zbl 1181.90215 · doi:10.1080/10556780500065283
[45] Land, A. H.; Doig, A. G., An automatic method of solving discrete programming problems, Econometrica, 28, 3, 497-520 (1960) · Zbl 0101.37004 · doi:10.2307/1910129
[46] Lengauer, T., Combinatorial Algorithms for Integrated Circuit Layout (1990), John Wiley & Sons: John Wiley & Sons, Chichester · Zbl 0709.68039
[47] Liers, F., Jünger, M., Reinelt, G., and Rinaldi, G., Computing exact ground states of hard Ising spin glass problems by branch-and-cut, in New Optimization Algorithms in Physics, A. Hartmann and H. Rieger, eds., Wiley, Weinheim, 2004, pp. 47-68. · Zbl 1059.90147
[48] Löfberg, J., YALMIP: a toolbox for modeling and optimization in MATLAB, in IEEE International Symposium on Computer Aided Control Systems Design, 2004, pp. 284-289.
[49] Löfberg, J., YALMIP. Available at , Accessed February 2016.
[50] Mars, S., Mixed-integer semidefinite programming with an application to truss topology design, PhD thesis, FAU Erlangen-Nürnberg, 2013.
[51] Mars, S. and Schewe, L., An SDP-package for SCIP, Technical report, TU Darmstadt and FAU Erlangen-Nürnberg, August 2012.
[52] Mitchell, J. E., Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Eur. J. Oper. Res., 97, 139-148 (1997) · Zbl 0923.90121 · doi:10.1016/0377-2217(95)00373-8
[53] Modaresi, S.; Kılınç, M. R.; Vielma, J. P., Split cuts and extended formulations for mixed integer conic quadratic programming, Oper. Res. Lett., 43, 1, 10-15 (2015) · Zbl 1408.90201 · doi:10.1016/j.orl.2014.10.006
[54] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), John Wiley & Sons: John Wiley & Sons, New York · Zbl 0469.90052
[55] Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), SIAM: SIAM, Philadelphia · Zbl 0824.90112
[56] Permenter, F., Friberg, H.A., and Andersen, E.D., Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach, Technical report, Optimization-Online, 2015. · Zbl 1368.90123
[57] Philipp, A., Ulbrich, S., Cheng, Y., and Pesavento, M., Multiuser downlink beamforming with interference cancellation using a SDP-based branch-and-bound algorithm, in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Process (ICASSP), Florence. IEEE, New York, 2014, pp. 7724-7728.
[58] Pilanci, M.; Wainwright, M. J.; El Ghaoui, L., Sparse learning via Boolean relaxations, Math. Program. Ser. B, 151, 1, 62-87 (2015) · Zbl 1328.90106 · doi:10.1007/s10107-015-0894-1
[59] Porkolab, L.; Khachiyan, L., On the complexity of semidefinite programs, J. Global Optim., 10, 351-365 (1997) · Zbl 0881.90127 · doi:10.1023/A:1008203903341
[60] Rendl, F., Semidefinite relaxations for integer programming, In 50 Years of Integer Programming 1958-2008, M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, eds., Springer, Berlin, 2009, pp. 687-726. · Zbl 1187.90003
[61] 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 · doi:10.1007/s10107-008-0235-8
[62] Rudy, G. Rinaldi, Available at . Accessed March 2016.
[63] Rothberg, E., An evolutionary algorithm for polishing mixed integer programming solutions, INFORMS J. Comput., 19, 4, 534-541 (2007) · Zbl 1241.90092 · doi:10.1287/ijoc.1060.0189
[64] Savelsbergh, M. W.P., Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 4, 445-454 (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445
[65] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley, Chichester · Zbl 0665.90063
[66] SCIP-Solving Constraint Integer Programs. Available at . Accessed March 2016.
[67] SCIP-SDP. Available at . Accessed March 2016.
[68] Shapiro, A. and Scheinberg, K., Duality and optimality conditions, in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, New York, 2000, pp. 67-110. · Zbl 0957.90517
[69] Sotirov, R., SDP relaxations for some combinatorial optimization problems, in Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, M. Anjos and J. Lasserre, eds., International Series in Operational Research and Management Science, Vol. 166, Springer, New York, 2012, pp. 795-820. · Zbl 1334.90116
[70] Todd, M. J., Semidefinite optimization, Acta Numer., 10, 515-560 (2001) · Zbl 1105.65334 · doi:10.1017/S0962492901000071
[71] Vigerske, S., Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming, PhD thesis, HU Berlin, 2012.
[72] Wainwright, M. J., Sharp thresholds for high-dimensional and noisy sparsity recovery using \(####\)-constrained quadratic programming (Lasso), IEEE Trans. Inform. Theory, 55, 5, 2183-2202 (2009) · Zbl 1367.62220 · doi:10.1109/TIT.2009.2016018
[73] Yamashita, M.; Fujisawa, K.; Kojima, M., Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0), Optim. Methods Softw., 18, 491-505 (2003) · Zbl 1106.90366 · doi:10.1080/1055678031000118482
[74] Yamashita, M., Fujisawa, K., Nakata, K., Nakata, M., Fukuda, M., Kobayashi, K., and Goto, K., A high-performance software package for semidefinite programs: SDPA 7, Research Report B-460, Department of Mathematical and Computing Science, Tokyo Institute of Technology, September 2010.
[75] Ye, Y., Interior Point Algorithms: Theory and Analysis (1997), John Wiley & Sons: John Wiley & Sons, New York · Zbl 0943.90070
[76] Ye, Y.; Todd, M. J.; Mizuno, S., An \(####\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 53-67 (1994) · Zbl 0799.90087 · doi:10.1287/moor.19.1.53
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.