Abstract
Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then known symmetry handling techniques can be applied. We demonstrate the effect of symmetry handling on different types of MISDPs. To this end, our symmetry detection routine is implemented in the state-of-the-art MISDP solver SCIP-SDP. We obtain speed-ups similar to the mixed-integer linear case.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bai, Y., de Klerk, E., Pasechnik, D., Sotirov, R.: Exploiting group symmetry in truss topology optimization. Optim. Eng. 10(3), 331–349 (2009)
Bestuzheva, K., et al.: The SCIP Optimization Suite 8.0. Technical report, Optimization Online (2021). http://www.optimization-online.org/DB_HTML/2021/12/8728.html
Burer, S., Monteiro, R.D., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Program. 94, 137–166 (2022). https://doi.org/10.1007/s10107-002-0356-4
Color02 - computational symposium: graph coloring and its generalizations (2002). http://mat.gsia.cmu.edu/COLOR02
Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250–255 (1965). https://doi.org/10.1093/comjnl/8.3.250
de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122(2), 225–246 (2010)
Fiorini, S., Wilson, R.J.: Edge-colourings of graphs. No. 16 in Research Notes in Mathematics, Pitman Publishing Limited (1977)
Gally, T.: Computational Mixed-Integer Semidefinite Programming. Dissertation, TU Darmstadt (2019)
Gally, T., Pfetsch, M.E., Ulbrich, S.: A framework for solving mixed-integer semidefinite programs. Optim. Methods Softw. 33(3), 594–632 (2017). https://doi.org/10.1080/10556788.2017.1322081
Gamrath, G., et al.: The SCIP Optimization Suite 7.0. Technical report, Optimization Online (2020). http://www.optimization-online.org/DB_HTML/2020/03/7705.html
Gatermann, K., Parrilo, P.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192(1–3), 95–128 (2004)
Hojny, C., Pfetsch, M.E.: Polytopes associated with symmetry handling. Math. Program. 175(1), 197–240 (2019). https://doi.org/10.1007/s10107-018-1239-7
Hu, H., Sotirov, R., Wolkowicz, H.: Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs. Math. Program. (2022, to appear)
Isaacs, R.: Infinite families of nontrivial trivalent graphs which are not tait colorable. Am. Math. Mon. 82(3), 221–239 (1975). https://doi.org/10.1080/00029890.1975.11993805
Junttila, T., Kaski, P.: Bliss: a tool for computing automorphism groups and canonical labelings of graphs. https://users.aalto.fi/tjunttil/bliss/
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979)
Margot, F.: Exploiting orbits in symmetric ILP. Math. Program. 98(1–3), 3–21 (2003). https://doi.org/10.1007/s10107-003-0394-6
Margot, F.: Symmetry in integer linear programming. In: Jünger, M., et al. (eds.) 50 Years of Integer Programming 1958-2008, pp. 647–686. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-540-68279-0_17
Mars, S.: Mixed-Integer Semidefinite Programming with an Application to Truss Topology Design. Dissertation, FAU Erlangen-Nürnberg (2013)
Matter, F., Pfetsch, M.E.: Presolving for mixed-integer semidefinite optimization. INFORMS J. Optim. (2022, to appear). https://doi.org/10.1287/ijoo.2022.0079
McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94–112 (2014). https://doi.org/10.1016/j.jsc.2013.09.003
Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126(1), 147–178 (2011). https://doi.org/10.1007/s10107-009-0273-x
Pfetsch, M.E., Rehn, T.: A computational comparison of symmetry handling methods for mixed integer programs. Math. Program. Comput. 11(1), 37–93 (2018). https://doi.org/10.1007/s12532-018-0140-y
Pilanci, M., Wainwright, M.J., El Ghaoui, L.: Sparse learning via Boolean relaxations. Math. Program. 151(1), 63–87 (2015). https://doi.org/10.1007/s10107-015-0894-1
Project website: instance data, supplementary material. https://www2.mathematik.tu-darmstadt.de/pfetsch/MISDP-symmetries.html
Salvagnin, D.: A dominance procedure for integer programming. Master’s thesis, University of Padova, Padova, Italy (2005)
Wiese, S.: Symmetry detection in mixed-integer conic programming. Mosek Whitepaper (2022). https://docs.mosek.com/whitepapers/symmetry.pdf
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hojny, C., Pfetsch, M.E. (2023). Handling Symmetries in Mixed-Integer Semidefinite Programs. In: Cire, A.A. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023. Lecture Notes in Computer Science, vol 13884. Springer, Cham. https://doi.org/10.1007/978-3-031-33271-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-33271-5_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33270-8
Online ISBN: 978-3-031-33271-5
eBook Packages: Computer ScienceComputer Science (R0)