Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation

References

• Anstreicher KM (2009) Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43(2):471–484.Crossref, Google Scholar
• Asahiro Y, Iwama K, Tamaki H, Tokuyama T (1996) Greedily finding a dense subgraph. Proc. 5th Scandinavian Workshop on Algorithm Theory. Lectures Notes Comput. Sci., Vol. 1097 (Springer-Verlag, Berlin), 136–148.Crossref, Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (2000) A branch and cut algorithm for non-convex quadratically constrained quadratic programming. Math. Programming 87(1):131–152.Crossref, Google Scholar
• Belloni A, Sagastizábal C (2009) Dynamic bundle methods. Math. Programming 120(2, Ser. A):289–311.Crossref, Google Scholar
• Belotti P (2013) Couenne, a user’s manual. Accessed October 31, 2009, http://www.coin-or.org/Couenne/.Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Waechter A (2009) Branching and bounds tightening techniques for non-convex MINLPs. Optim. Methods Software 24(4–5):597–634.Crossref, Google Scholar
• Billionnet A (2005) Different formulations for solving the heaviest k-subgraph problem. Inform. Systems Oper. Res. 43(3):171–186.Crossref, Google Scholar
• Billionnet A, Elloumi S, Lambert A (2012) Extending the QCR method to the case of general mixed integer program. Math. Programming 131(1):381–401.Crossref, Google Scholar
• Billionnet A, Elloumi S, Lambert A (2016) Exact quadratic convex reformulations of mixed-integer quadratically constrained problems. Math. Programming 158(1):235–266.Crossref, Google Scholar
• Billionnet A, Elloumi S, Plateau M-C (2005) Convex quadratic programming for exact solution of 0–1 quadratic programs. Technical Report CEDRIC-05-856, CEDRIC, Paris.Google Scholar
• Billionnet A, Elloumi S, Plateau M-C (2009) Improving the performance of standard solvers for quadratic 0–1 programs by a tight convex reformulation: The QCR method. Discrete Appl. Math. 157(6):1185–1197.Crossref, Google Scholar
• Bliek C, Bonami P (2013) Non-convex quadratic programming in CPLEX. Presentation, INFORMS 2013 Annual Meeting, Minneapolis.Google Scholar
• Bonami P, Biegler L, Conn A, Cornuéjols G, Grossmann I, Laird C, Lee Jet al. (2005) An algorithmic framework for convex mixed integer nonlinear programming. Discrete Optim. 5(2):186–204.Crossref, Google Scholar
• Borchers B (1999) CSDP, a C library for semidefinite programming. Optim. Methods Software 11(1):613–623.Crossref, Google Scholar
• Burer S, Monteiro RDC (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2, Ser. B):329–357.Crossref, Google Scholar
• Burer S, Monteiro RDC (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3, Ser. A):427–444.Crossref, Google Scholar
• Corneil DC, Perl YA (1984) Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1):27–39.Crossref, Google Scholar
• Erkut E (1990) The discrete p-dispersion problem. Eur. J. Oper. Res. 46(1):46–80.Crossref, Google Scholar
• Fischer I, Gruber G, Rendl F, Sotirov R (2006) Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition. Math. Programming 105(2–3, Ser. B):451–469.Crossref, Google Scholar
• Floudas CA (2000) Deterministic Global Optimization (Kluwer Academic Publishing, Dordrecht, Netherlands).Crossref, Google Scholar
• Fujisawa K, Kojima M (1995) SDPA (semidefinite programming algorithm) users manual. Technical Report B-308, Tokyo Institute of Technology.Google Scholar
• Hager WW, Krylyuk Y (1999) Graph partitioning and continuous quadratic programming. SIAM J. Discrete Math. 12(4):500–523.Crossref, Google Scholar
• Han Q, Ye Y, Zhang J (2002) An improved rounded method and semidefinite programming relaxation for graph partition. Math. Programming 92(3):509–535.Crossref, Google Scholar
• Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21(3):133–137.Crossref, Google Scholar
• Helmberg C (2000) A C++ Implementation of the Spectral Bundle Method. Manual Version 1.1.1. Accessed February 10, 2017, https://www-user.tu-chemnitz.de/~helmberg/SBmethod/.Google Scholar
• Helmberg C (2011) Conic Bundle v 0.3.10. Accessed February 10, 2017, https://www-user.tu-chemnitz.de/~helmberg/ConicBundle/.Google Scholar
• Helmberg C, Rendl F (2000) A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3):673–696.Crossref, Google Scholar
• Helmberg C, Rendl F, Vanderbei RJ, Wolkowicz H (1996) An interior-point method for semidefinite programming. SIAM J. Optim. 6(2):342–361.Crossref, Google Scholar
• IBM-ILOG (2013) IBM ILOG Cplex 12.5 reference manual. Accessed February 10, 2017, http://www.ibm.com/support/knowledgecenter/SSSA5P_12.5.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html.Google Scholar
• IBM-ILOG (2015) IBM ILOG Cplex 12.6 reference manual. Accessed February 10, 2017, http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html.Google Scholar
• Jäger G, Srivastav A (2005) Improved approximation algorithms for maximum graph partitioning problems. J. Combinatorial Optim. 10(2):133–167.Crossref, Google Scholar
• Jarre F, Rendl F (2008) An augmented primal-dual method for linear conic programs. SIAM J. Optim. 19(2):808–823.Crossref, Google Scholar
• Kortsarz G, Peleg D (1993) On choosing a dense subgraph. Proc. 1993 IEEE 34th Annual Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 692–701.Crossref, Google Scholar
• Krarup J, Pisinger D, Plastria F (2002) Discrete location problems with push-pull objectives. Discrete Appl. Math. 123(4):363–378.Crossref, Google Scholar
• Krislock N, Malick J, Roupin F (2013) Library of k-cluster instances. http://lipn.univ-paris13.fr/BiqCrunch/download.Google Scholar
• Krislock N, Malick J, Roupin F (2016) Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Comput. Oper. Res. 66:153–159.Crossref, Google Scholar
• Lambert A (2009) Résolution de programmes quadratiques en nombres entiers. Unpublished doctoral dissertation, Conservatoire National des Arts et Métiers, Paris, http://cedric.cnam.fr/fichiers/art_1838.pdf.Google Scholar
• Lambert A (2012) EIQP/IIQP: Library of integer quadratic programs. Accessed October 31, 2015, http://cedric.cnam.fr/~lamberta/Library/eiqp_iiqp.html.Google Scholar
• Le Cun B, Roucairol C, The PNN Team (1995) BOB: A unified platform for implementing branch-and-bound like algorithms. Report, Laboratoire PRiSM, Université de Versailles, Versailles Cedex, France. Accessed February 10, 2017, http://perso.prism.uvsq.fr/users/blec/Download/BobReport.pdf.Google Scholar
• Liberti L, Maculan N (2006) Global Optimization: From Theory to Implementation (Springer, New York).Crossref, Google Scholar
• Malick J (2007) Spherical constraint in Boolean quadratic programming. J. Global Optim. 39(4):609–622.Crossref, Google Scholar
• Malick J, Roupin F (2012) Solving k-cluster problems to optimality with semidefinite programming. Math. Programming 136(2(B)):279–300.Crossref, Google Scholar
• Malick J, Povh J, Rendl F, Wiegele A (2009) Regularization methods for semidefinite programming. SIAM J. Optim. 20(1):336–356.Crossref, Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable non-convex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Pisinger D (2006) Upper bounds and exact algorithms for p-dispersion problems. Comput. Oper. Res. 33(5):1380–1398.Crossref, Google Scholar
• Plateau M-C (2006) Reformulations quadratiques convexes pour la programmation quadratique en variables 0–1. Unpublished doctoral dissertation, Conservatoire National des Arts et Métiers, Paris, http://cedric.cnam.fr/fichiers/RC1115.pdf.Google Scholar
• Roupin F (2004) From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems. J. Combinatorial Optim. 8(4):469–493.Crossref, Google Scholar
• Sahinidis NV, Tawarmalani M (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225–249.Crossref, Google Scholar
• Smith EMB (1996) On the optimal design of continuous processes. Unpublished doctoral dissertation, Imperial College of Science, Technology and Medicine, University of London.Google Scholar
• Smith EMB, Pantelides CC (1997) Global optimisation of nonconvex minlps. Comput. Chem. Engrg. 21(Suppl.):S791–S796.Crossref, Google Scholar
• Smith EMB, Pantelides CC (1999) A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex minlps. Comput. Chem. Engrg. 23(4):457–478.Crossref, Google Scholar
• Srivastav A, Wolf K (1998) Finding dense subgraph with semidefinite programming. Jansen K, Rolim J, eds. Approximation Algorithms for Combinatorial Optimization, Lecture Notes Comput. Sci., Vol. 1444 (Springer, Berlin), 181–191.Crossref, Google Scholar
• Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11(1–4):625–653.Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming (Kluwer Academic Publishing, Dordrecht, Netherlands).Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Programming 99(3):563–591.Crossref, Google Scholar
• Zhao X-Y, Sun D, Toh K-C (2010) A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4):1737–1765.Crossref, Google Scholar