Presolving for Mixed-Integer Semidefinite Optimization

References

• Achterberg T (2007a) Conflict analysis in mixed integer programming. Discrete Optim. 4(1):4–20.Google Scholar
• Achterberg T (2007b) Constraint integer programming. Unpublished dissertation, Technische Universität Berlin, Germany.Google Scholar
• Achterberg T, Wunderling R (2013) Mixed integer programming: Analyzing 12 years of progress. Jünger M, Reinelt G, eds. Facets of Combinatorial Optimization (Springer, Berlin, Heidelberg), 449–481.Google Scholar
• Achterberg T, Bixby RE, Gu Z, Rothberg E, Weninger D (2020) Presolve reductions in mixed integer programming. INFORMS J. Comput. 32(2):473–506.Link, Google Scholar
• Atamtürk A, Gómez A (2020) Safe screening rules for L0-regression from perspective relaxations. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (PMLR), 421–430.Google Scholar
• Belotti P, Cafieri S, Lee J, Liberti L (2010) Feasibility-based bounds tightening via fixed points. Wu W, Daescu O, eds. Combin. Optim. Appl. Fourth Internat. Conf., Lecture Notes in Computer Science, vol. 6508 (Springer), 65–76.Google Scholar
• Belotti P, Kirches C, Leyffer S, Linderoth J, Luedtke J, Mahajan A (2013) Mixed-integer nonlinear optimization. Acta Numerica, vol. 22, 1–131.Google Scholar
• Ben-Tal A, Nemirovski A (1997) Robust truss topology design via semidefinite programming. SIAM J. Optim. 7(4):991–1016.Google Scholar
• Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• Bertsimas D, Van Parys B (2020) Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. Ann. Statist. 48(1):300–323.Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J (2022) Solving large-scale sparse PCA to certifiable (near) optimality. J. Machine Learn. Res. 23(13):1–35.Google Scholar
• Bestuzheva K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2021) The SCIP Optimization Suite 8.0. Technical report, Optimization Online. http://www.optimization-online.org/DB_HTML/2021/12/8728.html.Google Scholar
• Bixby R, Rothberg E (2007) Progress in computational mixed integer programming—A look back from the other side of the tipping point. Ann. Oper. Res. 149:37–41.Google Scholar
• Bordeaux L, Katsirelos G, Narodytska N, Vardi MY (2011) The complexity of integer bound propagation. J. Artificial Intelligence Res. 40(1):657–676.Google Scholar
• Boyd S, Vandenberghe L (2009) Convex Optimization 7th ed. (Cambridge University Press, Cambridge, UK).Google Scholar
• Braun G, Pokutta S, Zink D (2019) Affine reductions for LPs and SDPs. Math. Programming 173:281–312.Google Scholar
• Braun G, Fiorini S, Pokutta S, Steurer D (2015) Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3):756–772.Link, Google Scholar
• Brearley AL, Mitra G, Williams HP (1975) Analysis of mathematical programming problems prior to applying the simplex algorithm. Math. Programming 8(1):54–83.Google Scholar
• Coey C, Lubin M, Vielma JP (2020) Outer approximation with conic certificates for mixed-integer convex problems. Math. Programming Comput. 12:249–293.Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• Dakin RJ (1965) A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3):250–255.Google Scholar
• Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36:307–339.Google Scholar
• Eisenblätter A (2001) Frequency assignment in GSM networks: Models, heuristics, and lower bounds. Dissertation, Technische Universität Berlin, Germany.Google Scholar
• Eisenblätter A (2002) The semidefinite relaxation of the k-partition polytope is strong. Cook WJ, Schulz AS, eds. Proc. 9th Internat. IPCO Conf. Integer Programming Combin. Optim., Lecture Notes in Computer Science, vol. 2337 (Springer, Berlin, Heidelberg), 273–290.Google Scholar
• Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II (Springer).Google Scholar
• Foucart S, Rauhut H (2013) A Mathematical Introduction to Compressive Sensing (Birkhäuser, Basel, Switzerland).Google Scholar
• Fritz C (2002) Some fixed point basics. Grädel E, Thomas W, Wilke T, eds. Automata Logics and Infinite Games: A Guide to Current Research (Springer, Berlin, Heidelberg), 359–364.Google Scholar
• Gally T (2019) Computational mixed-integer semidefinite programming. Dissertation, Technische Universität Darmstadt, Germany.Google Scholar
• Gally T, Pfetsch ME (2016) Computing restricted isometry constants via mixed-integer semidefinite programming. Technical report, Optimization Online. http://www.optimization-online.org/DB_HTML/2016/04/5395.html.Google Scholar
• Gally T, Pfetsch ME, Ulbrich S (2017) A framework for solving mixed-integer semidefinite programs. Optim. Methods Software 33(3):594–632.Google Scholar
• Gemander P, Chen WK, Weninger D, Gottwald L, Gleixner A, Martin A (2020) Two-row and two-column mixed-integer presolve using hashing-based pairing methods. EURO J. Comput. Optim. 8:205–240.Google Scholar
• Gleixner AM, Berthold T, Müller B, Weltge S (2017) Three enhancements for optimization-based bound tightening. J. Global Optim. 67(4):731–757.Google Scholar
• Helmberg C (2000) Semidefinite programming for combinatorial optimization. Habilitation, Technische Universität Berlin, Germany.Google Scholar
• Higham NJ, Strabić N, Sego V (2016) Restoring definiteness via shrinking, with an application to correlation matrices with a fixed block. SIAM Rev. 58(2):245–263.Google Scholar
• Jiang R, Li D, Wu B (2018) SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices. Math. Programming 169:531–563.Google Scholar
• Kobayashi K, Takano Y (2020) A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems. Comput. Optim. Appl. 75:493–513.Google Scholar
• Krishnan K, Mitchell JE (2006) A unifying framework for several cutting plane methods for semidefinite programming. Optim. Methods Software 21(1):57–74.Google Scholar
• Lancaster P, Rodman L (2005) Canonical forms for Hermitian matrix pairs under strict equivalence and congruence. SIAM Rev. 47(3):407–443.Google Scholar
• Li Y, Xie W (2020) Exact and approximation algorithms for sparse PCA. Technical report, Optimization Online. http://www.optimization-online.org/DB_HTML/2020/05/7802.html.Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. IEEE Internat. Sympos. Comput. Aided Control Systems Design, 284–289.Google Scholar
• Lubin M, Yamangil E, Bent R, Vielma JP (2018) Polyhedral approximation in mixed-integer convex optimization. Math. Programming 172:139–168.Google Scholar
• Mahajan A (2011) Presolving mixed-integer linear programs. Wiley Encyclopedia of Operations Research and Management Science (American Cancer Society, Atlanta).Google Scholar
• Mars S (2013) Mixed-integer semidefinite programming with an application to truss topology design. Dissertation, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen–Nuremberg, Germany.Google Scholar
• Nohra CJ, Raghunathan AU, Sahinidis N (2021) Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs. SIAM J. Optim. 31(1):142–171.Google Scholar
• Permenter F, Parrilo PA (2018) Partial facial reduction: Simplified, equivalent SDPs via approximations of the PSD cone. Math. Programming 171(1):1–54.Google Scholar
• Permenter F, Parrilo PA (2020) Dimension reduction for semidefinite programs via Jordan algebras. Math. Programming 181(1):51–84.Google Scholar
• Permenter F, Friberg HA, Andersen ED (2017) Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach. SIAM J. Optim. 27(3):1257–1282.Google Scholar
• Pilanci M, Wainwright MJ, El Ghaoui L (2015) Sparse learning via Boolean relaxations. Math. Programming Ser. B 151(1):62–87.Google Scholar
• Pong TK, Wolkowicz H (2014) The generalized trust region subproblem. Comput. Optim. Appl. 58:273–322.Google Scholar
• Puranik Y, Sahinidis NV (2017) Domain reduction techniques for global NLP and MINLP optimization. Constraints 22(3):338–376.Google Scholar
• Qi L, Sun J (1993) A nonsmooth version of Newton’s method. Math. Programming 58(1):353–367.Google Scholar
• Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Sherali HD, Fraticelli BM (2002) Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22:233–261.Google Scholar
• Strabić N (2016) Theory and algorithms for matrix problems with positive semidefinite constraints. PhD thesis, University of Manchester, Manchester, UK.Google Scholar
• Tarski A (1955) A lattice-theoretical fixpoint theorem and its application. Pacific J. Math. 5(2):285–309.Google Scholar
• Vigerske S (2013) Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Dissertation, Humboldt-Universität zu Berlin, Germany.Google Scholar
• Vigerske S, Gleixner A (2018) SCIP: Global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Software 33(3):563–593.Google Scholar
• Witzig J (2021) Infeasibilitity analysis for MIP. Dissertation, Technische Universität Berlin, Germany.Google Scholar
• Witzig J, Berthold T, Heinz S (2017) Experiments with conflict analysis in mixed integer programming. Integration AI OR Techniques Constraint Programming, 211–222.Google Scholar