On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems

References

• Amaral , A. R.S. 2009 . A new lower bound for the single row facility layout problem . Discrete Appl. Math. , 157 ( 1 ) : 183 – 190 .
   Web of Science ®Google Scholar
• Anjos , M. F. and Burer , S. 2007 . On handling free variables in interior-point methods for conic linear optimization . SIAM J. Optim. , 18 ( 4 ) : 1310 – 1325 .
   Web of Science ®Google Scholar
• Anjos , M. F. , Kennings , A. and Vannelli , A. 2005 . A semidefinite optimization approach for the single-row layout problem with unequal dimensions . Discrete Optim. , 2 ( 2 ) : 113 – 122 .
   Google Scholar
• Anjos , M. F. and Vannelli , A. 2008 . Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes . INFORMS J. Comput. , 20 ( 4 ) : 611 – 617 .
   Web of Science ®Google Scholar
• Anjos , M. F. and Wolkowicz , H. 2002 . Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem . Discrete Appl. Math. , 119 ( 1–2 ) : 79 – 106 .
   Web of Science ®Google Scholar
• Anjos , M. F. and Yen , G. 2009 . Provably near-optimal solutions for very large single-row facility layout problems . Optim. Methods Softw. , 24 ( 4–5 ) : 805 – 817 .
   Web of Science ®Google Scholar
• Bampis , E. , Jansen , K. and Kenyon , C. 2006 . Efficient Approximation and Online Algorithms , Berlin : Springer-Verlag . Lecture Notes in Computer Science, Vol. 3484
   Google Scholar
• Benson , H. Y. and Shanno , D. F. 2007 . An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming . Comput. Optim. Appl. , 38 ( 3 ) : 371 – 399 .
   Web of Science ®Google Scholar
• Borchers , B. and Vanderbei , R. J. Private communications, 2008–2009 .
   Google Scholar
• Klerk , E. De , Pasechnik , D. V. and Sotirov , R. 2008 . On semidefinite programming relaxations of the traveling salesman problem . SIAM J. Optim. , 19 ( 4 ) : 1559 – 1573 .
   Web of Science ®Google Scholar
• Deza , M. M. and Laurent , M. 1997 . Geometry of Cuts and Metrics, Algorithms and Combinatorics , Vol. 15 , Berlin : Springer-Verlag .
   Google Scholar
• El-Bakry , A. S. , Tapia , R. A. and Zhang , Y. 1994 . A study of indicators for identifying zero variables in interior-point methods . SIAM Rev. , 36 ( 1 ) : 45 – 72 .
   Web of Science ®Google Scholar
• A. Engau, Recent progress in interior-point methods: Cutting-plane algorithms and warm starts, in Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, Vol. 166, Chapter 17, M.F. Anjos and J.B. Lasserre, eds., Springer, New York, 2012
   Google Scholar
• A. Engau, M.F. Anjos, and A. Vannelli, A primal-dual slack approach to warmstarting interior-point methods for linear programming, in Operations Research and Cyber-Infrastructure, J.W. Chinneck, B. Kristjansson, and M.J. Saltzman, eds., Springer, New York, 2009, pp. 195–217
   Google Scholar
• Engau , A. , Anjos , M. F. and Vannelli , A. 2010 . An improved interior-point cutting-plane method for binary quadratic optimization . Electron. Notes Discrete Math. , 36 : 743 – 750 .
   Google Scholar
• Engau , A. , Anjos , M. F. and Vannelli , A. 2010 . On interior-point warmstarts for linear and combinatorial optimization . SIAM J. Optim. , 10 ( 4 ) : 1828 – 1861 .
   Google Scholar
• Facchinei , F. , Fischer , A. and Kanzow , C. 2000 . On the identification of zero variables in an interior-point framework . SIAM J. Optim. , 10 ( 4 ) : 1058 – 1078 .
   Web of Science ®Google Scholar
• Fischer , I. , Gruber , G. , Rendl , F. and Sotirov , R. 2006 . Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition . Math. Program. , 105 : 451 – 469 . (2–3, Ser. B)
   Web of Science ®Google Scholar
• Freund , R. M. 1991 . A potential-function reduction algorithm for solving a linear program directly from an infeasible ‘warm start’ . Math. Program. , 52 ( 3, Ser. B ) : 441 – 466 .
   Web of Science ®Google Scholar
• Goemans , M. X. and Williamson , D. P. 1995 . Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming . J. Assoc. Comput. Mach. , 42 ( 6 ) : 1115 – 1145 .
   Web of Science ®Google Scholar
• Gondzio , J. 1998 . Warm start of the primal-dual method applied in the cutting-plane scheme . Math. Program. , 83 ( 1, Ser. A ) : 125 – 143 .
   Web of Science ®Google Scholar
• Gondzio , J. and Grothey , A. 2003 . Reoptimization with the primal-dual interior point method . SIAM J. Optim. , 13 ( 3 ) : 842 – 864 .
   Web of Science ®Google Scholar
• C. Helmberg, A cutting plane algorithm for large scale semidefinite relaxations, in The Sharpest Cut, MPS/SIAM Series Optimization, SIAM, Philadelphia, PA, 2004, pp. 233–256
   Google Scholar
• Helmberg , C. and Rendl , F. 1998 . Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes . Math. Program. , 82 ( 3, Ser. A ) : 291 – 315 .
   Web of Science ®Google Scholar
• Helmberg , C. and Rendl , F. 2000 . A spectral bundle method for semidefinite programming, . SIAM J. Optim. , 10 ( 3 ) : 673 – 696 .
   Web of Science ®Google Scholar
• Heragu , S. S. and Kusiak , A. 1988 . Machine layout problem in flexible manufacturing systems . Oper. Res. , 36 ( 2 ) : 258 – 268 .
   Web of Science ®Google Scholar
• Kong , C. and Anjos , M. F. Facility layout problem (FLP) database library . Available at: http://flplib.uwaterloo.ca/
   Google Scholar
• Krishnan , K. and Mitchell , J. E. 2006 . A unifying framework for several cutting plane methods for semidefinite programming . Optim. Methods Softw. , 21 ( 1 ) : 57 – 74 .
   Web of Science ®Google Scholar
• F. Liers, M. Jünger, G. Reinelt, and G. Rinaldi, 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, Wiley-VCH Verlag, Weinheim, FRG 2004, pp. 47–68
   Google Scholar
• Lustig , I. J. , Marsten , R. E. and Shanno , D. F. 1994 . Interior point methods for linear programming: Computational state of the art . ORSA J. Comput. , 6 ( 1 ) : 1 – 14 .
   Google Scholar
• Mitchell , J. E. 1994 . An interior point column generation method for linear programming using shifted barriers . SIAM J. Optim. , 4 ( 2 ) : 423 – 440 .
   Web of Science ®Google Scholar
• Mitchell , J. E. 2000 . Computational experience with an interior point cutting plane algorithm . SIAM J. Optim. , 10 ( 4 ) : 1212 – 1227 .
   Web of Science ®Google Scholar
• Mitchell , J. E. and Borchers , B. 1996 . Solving real-world linear ordering problems using a primal-dual interior point cutting plane method . Ann. Oper. Res. , 62 : 253 – 276 .
   Web of Science ®Google Scholar
• Mizuno , S. 1994 . Polynomiality of infeasible-interior-point algorithms for linear programming . Math. Program. , 67 ( 1, Ser. A ) : 109 – 119 .
   Web of Science ®Google Scholar
• Monteiro , R. D.C. 2003 . First- and second-order methods for semidefinite programming . Math. Program. , 97 ( 1–2, Ser. B ) : 209 – 244 . ISMP
   Web of Science ®Google Scholar
• Oberlin , C. and Wright , S. J. 2006 . Active set identification in nonlinear programming . SIAM J. Optim. , 17 ( 2 ) : 577 – 605 .
   Web of Science ®Google Scholar
• Polyak , R. A. 1992 . Modified barrier functions (theory and methods) . Math. Program. , 54 ( 2, Ser. A ) : 177 – 222 .
   Web of Science ®Google Scholar
• Rendl , F. , Rinaldi , G. and Wiegele , A. 2010 . Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations . Math. Program. , 121 ( 2, Ser. A ) : 307 – 335 .
   Web of Science ®Google Scholar
• Rinaldi , G. Rudy: A rudimental graph generator . Available at: http://www-user.tu-chemnitz.de/~helmberg/rudy.tar.gz, 1998
   Google Scholar
• Simmons , D. M. 1969 . One-dimensional space allocation: An ordering algorithm . Oper. Res. , 17 : 812 – 826 .
   Web of Science ®Google Scholar
• Suryanarayanan , J. K. , Golden , B. L. and Wang , Q. 1991 . A new heuristic for the linear placement problem . Comput. Oper. Res. , 18 ( 3 ) : 255 – 262 .
   Web of Science ®Google Scholar
• Todd , M. J. 1999 . A study of search directions in primal-dual interior-point methods for semidefinite programming . Optim. Methods Softw. , 11/12 ( 1–4 ) : 1 – 46 .
   Web of Science ®Google Scholar
• Tütüncü , R. H. , Toh , K.-C. and Todd , M. J. 2003 . Solving semidefinite-quadratic-linear programs using SDPT3 . Math. Program. , 95 ( 2, Ser. B ) : 189 – 217 .
   Web of Science ®Google Scholar
• H.Wolkowicz, R. Saigal, and L.Vandenberghe (eds.), Handbook of Semidefinite Programming, International Series in Operations Research & Management Science, Vol. 27, Kluwer Academic Publishers, Boston, MA, 2000
   Google Scholar
• Wolsey , L. A. Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1998 .
   Google Scholar
• Yildirim , E. A. and Wright , S. J. 2002 . Warm-start strategies in interior-point methods for linear programming . SIAM J. Optim. , 12 ( 3 ) : 782 – 810 .
   Web of Science ®Google Scholar