Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs

References

• Adhya , N. , Tawarmalani , M. and Sahinidis , N. V. 1999 . A Lagrangian approach to the pooling problem . Ind. Eng. Chem. , 38 : 1956 – 1972 .
   Google Scholar
• Al-Khayyal , F. A. 1992 . Generalized bilinear programming: Part I, models, applications and linear programming relaxation . Eur. J. Oper. Res. , 60 : 306 – 314 .
   Web of Science ®Google Scholar
• Al-Khayyal , F. A. and Falk , J. E. 1983 . Jointly constrained biconvex programming . Math. Oper. Res. , 8 : 273 – 286 .
   Web of Science ®Google Scholar
• Al-Khayyal , F. A. , Larsen , C. and Van Voorhis , T. 1995 . A relaxation method for nonconvex quadratically constrained quadratic programs . J. Global Optim. , 6 : 215 – 230 .
   Web of Science ®Google Scholar
• Anstreicher , K. M. 2007 . Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming . Optimization Online Digest , Available at http://www.optimization-online.org/DB_HTML/05/1655.html
   Google Scholar
• Barahona , F. , Jünger , M. and Reinelt , G. 1989 . Experiments in quadratic 0-1 programming . Math. Program. , 44 : 127 – 137 .
   Google Scholar
• Barber , C. B. , Dobkin , D. P. and Huhdanpaa , H. T. 1996 . Lectures on modern convex optimization . ACM Trans. Math. Softw. , 22 : 469 – 483 . Available at http://www.qhull.org
   Web of Science ®Google Scholar
• Benson , H. P. 2007 . On the construction of convex and concave envelope formulas for bilinear and fractional functions on quadrilaterals . Comput. Optim. Appl. , 27 : 5 – 22 .
   Google Scholar
• Bertsimas , D. and Tsitsiklis , J. N. 1997 . Introduction to Linear Optimization , Nashua, NH : Athena Scientific .
   Google Scholar
• Billionnet , A. and Elloumi , S. 2007 . Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem . Math. Program. , 109 : 55 – 68 .
   Web of Science ®Google Scholar
• Boros , E. , Hammer , P. L. and Tavares , G. 2007 . Local search heuristics for quadratic unconstrained binary optimization (QUBO) . J. Heuristics , 13 : 99 – 132 .
   Google Scholar
• Brooke , A. , Kendrick , D. and Meeraus , A. 1988 . GAMS–A User's Guide , Redwood City, CA : The Scientific Press .
   Google Scholar
• Dorneich , M. C. and Sahinidis , N. V. 1995 . Global optimization algorithms for chip layout and compaction . Eng. Optim. , 25 : 131 – 154 .
   Web of Science ®Google Scholar
• Fang , S. C. , Gao , D. Y. , Sheu , R. L. and Wu , S. Y. 2008 . Canonical dual approach to solving 0–1 quadratic programming problems . J. Ind. Manag. Optim. , 4 : 124 – 142 .
   Google Scholar
• Floudas , C. A. and Visweswaran , V. 1995 . “ Quadratic optimization ” . In Handbook of Global Optimization, Nonconvex Optimization and its Applications , Vol. 2 , 217 – 269 . Dordrecht : Kluwer Academic Publishers . Chapter 5
   Google Scholar
• Goemans , M. X. and Williamson , D. P. 1995 . Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming . J. ACM , 42 : 1115 – 1145 .
   Web of Science ®Google Scholar
• Hao , E. P. 1982 . Quadratically constrained quadratic programming: Some applications and a method for solution . Math. Methods Oper. Res. , 26 : 105 – 119 .
   Google Scholar
• 2003 . ILOG, CPLEX 9.0 User's Manual , Incline Village, NV : ILOG CPLEX Division .
   Google Scholar
• Kim , S. and Kojima , M. 2001 . Second order cone programming relaxation of nonconvex quadratic optimization problems . Optim. Methods Softw. , 15 : 201 – 224 .
   Web of Science ®Google Scholar
• Kim , S. and Kojima , M. 2003 . Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations . Comput. Optim. Appl. , 26 : 143 – 154 .
   Web of Science ®Google Scholar
• Kojima , M. and Tunçel , L. 2002 . Some fundamental properties of successive convex relaxation methods on LCP and related problems . J. Global Optim. , 24 : 333 – 348 .
   Google Scholar
• Lin , Y. and Schrage , L. 2009 . The global solver in the LINDO API . Optim. Methods Softw. , 24 : 657 – 668 .
   Web of Science ®Google Scholar
• Linderoth , J. 2005 . A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs . Math. Program. , 103 : 251 – 282 .
   Web of Science ®Google Scholar
• Liu , M. L. and Sahinidis , N. V. 1997 . Process planning in a fuzzy environment . Eur. J. Oper. Res. , 100 : 142 – 169 .
   Web of Science ®Google Scholar
• Locatelli , M. and Raber , U. 2002 . Packing equal circles in a square: A deterministic global optimization approach . Discrete Appl. Math. , 122 : 139 – 166 .
   Web of Science ®Google Scholar
• McBride , R. D. and Yormark , J. S. 1980 . An implicit enumeration algorithm for quadratic integer programming . Manag. Sci. , 26 : 282 – 296 .
   Google Scholar
• Meyer , C. A. and Floudas , C. A. 2003 . “ Convex hull of trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes ” . In Frontiers in Global Optimization , Edited by: Floudas , C.A. and Pardalos , P.M. 327 – 352 . Boston : Kluwer .
   Google Scholar
• Meyer , C. A. and Floudas , C. A. 2004 . Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes . J. Glob. Optim. , 29 : 125 – 155 .
   Google Scholar
• Meyer , C. A. and Floudas , C. A. 2005 . Convex envelopes for edge-concave functions . Math. Program. , 103 : 207 – 224 .
   Google Scholar
• Nemhauser , G. L. and Wolsey , L. A. 1988 . Integer and Combinatorial Optimization , Series in Discrete Mathematics and Optimization New York, NY : Wiley Interscience .
   Google Scholar
• Nowak , I. 1999 . A new semidefinite programming bound for indefinite quadratic forms over a simplex . J. Global Optim. , 14 : 357 – 364 .
   Google Scholar
• Nowak , I. 2000 . Dual bounds and optimality cuts for all-quadratic programs with convex constraints . J. Global Optim. , 18 : 337 – 356 .
   Google Scholar
• Palubeckis , G. 2004 . Multistart tabu search strategies for the unconstrained binary quadratic optimization problem . Ann. Oper. Res. , 131 : 259 – 282 .
   Web of Science ®Google Scholar
• Pardalos , P. M. and Vavasis , S. A. 1991 . Quadratic programming with one negative eigenvalue is NP-hard . J. Global Optim. , 1 : 15 – 22 .
   Google Scholar
• Parija , G. , Gadidov , R. and Wilhelm , W. 1999 . A facet generation procedure for solving 0/1 integer programs . Oper. Res. , 47 : 789 – 791 .
   Google Scholar
• Picard , J. C. and Ratliff , H. D. 1974 . Minimum cuts and related problems . Networks , 5 : 357 – 370 .
   Google Scholar
• Qu , S. , Yin , H. and Zhang , K. 2006 . A global optimization algorithm using linear relaxation . Appl. Math. Comput. , 178 : 510 – 518 .
   Google Scholar
• Raber , U. 1999 . “ Nonconvex all-quadratic global optimization problems: Solution method, application and related topics ” . Germany : Universitär Trier . Ph.D. thesis
   Google Scholar
• Rikun , A. D. 1997 . A convex envelope formula for multilinear functions . J. Global Optim. , 10 : 425 – 437 .
   Google Scholar
• Rote , G. 1992 . The convergence rate of the sandwich algorithm for approximating convex functions . Computing , 48 : 337 – 361 .
   Web of Science ®Google Scholar
• Sahinidis , N. V. and Tawarmalani , M. 2005 . Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints . J. Global Optim. , 32 : 259 – 280 .
   Google Scholar
• Sahinidis , N. V. and Tawarmalani , M. 2008 . BARON 8.1.1: Global Optimization of Mixed-Integer Nonlinear Programs , User's Manual . Available at http://www.gams.com/dd/docs/solvers/baron.pdf
   Google Scholar
• Saxena , A. , Bonami , P. and Lee , J. 2008 . “ Convex relaxations of non-convex mixed integer quadratically constrained problems: Extended formulations ” . IBM Research Report RC24621
   Google Scholar
• Sherali , H. D. 1987 . A constructive proof of the representation theorem for polyhedral sets based on fundamental definitions . Am. J. Math. Manage. Sci. , 7 : 253 – 270 .
   Google Scholar
• Sherali , H. D. 1997 . Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets . Acta Math. Vietnam. , 22 : 245 – 270 .
   Google Scholar
• Sherali , H. D. and Alameddine , A. 1992 . A new reformulation-linearization technique for bilinear programming problems . J. Global Optim. , 2 : 379 – 410 .
   Google Scholar
• Sherali , H. D. and Fraticelli , B. M.P. 2002 . Enhancing RLT relaxation via a new class of semidefinite cuts . J. Global Optim. , 22 : 233 – 261 .
   Google Scholar
• Sherali , H. D. and Tuncbilek , C. H. 1992 . A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique . J. Global Optim. , 2 : 101 – 112 .
   Google Scholar
• Sherali , H. D. and Tuncbilek , C. H. 1995 . A reformulation-convexification approach for solving nonconvex quadratic programming problems . J. Global Optim. , 7 : 1 – 31 .
   Web of Science ®Google Scholar
• Shor , N. Z. 1987 . Quadratic optimization problems . Sov. J. Comput. and Syst. Sci. , 25 : 1 – 11 .
   Web of Science ®Google Scholar
• Shor , N. Z. 1992 . Dual estimates in multiextremal problems . J. Global Optim. , 2 : 411 – 418 .
   Google Scholar
• Sutou , A. and Dai , Y. 2002 . Global optimization approach to unequal sphere packing problems in 3D . J. Optim. Theory Appl. , 114 : 671 – 694 .
   Web of Science ®Google Scholar
• Tardella , F. 2003 . “ On the existence of polyhedral convex envelopes ” . In Frontiers in Global Optimization , Edited by: Floudas , C.A. and Pardalos , P.M. 149 – 188 . Boston : Kluwer .
   Google Scholar
• Tardella , F. 2008 . Existence and sum decomposition of vertex polyhedral convex envelopes . Optim. Lett. , 2 : 363 – 375 .
   Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2002 . Convex extensions and convex envelopes of l.s.c. functions . Math. Program. , 93 : 247 – 263 .
   Web of Science ®Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2002 . Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications , Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2004 . Global optimization of mixed-integer nonlinear programs: A theoretical and computational study . Math. Program. , 99 : 563 – 591 .
   Web of Science ®Google Scholar
• Thoai , N. V. 2000 . Duality bound method for the general quadratic programming problem with quadratic constraints . J. Optim. Theory Appl. , 107 : 331 – 354 .
   Google Scholar
• Tuy , H. 2005 . On solving nonconvex optimization problems by reducing the duality gap . J. Global Optim. , 32 : 349 – 365 .
   Google Scholar
• Tuy , H. and Hoai-Phuong , N. T. 2007 . A robust algorithm for quadratic optimization under quadratic constraints . J. Global Optim. , 4 : 557 – 569 .
   Google Scholar
• Vandenberghe , L. and Boyd , S. 1996 . Semidefinite programming . SIAM Rev. , 38 : 49 – 95 .
   Web of Science ®Google Scholar
• Van Voorhis , T. 2002 . A global optimization algorithm using lagrangian underestimates and the interval Newton method . J. Global Optim. , 24 : 349 – 370 .
   Google Scholar
• Van Voorhis , T. and Al-Khayyal , F. A. 2003 . Difference of convex solution of quadratically constrained optimization problems . Eur. J. Oper. Res. , 148 : 349 – 362 .
   Google Scholar
• Vavasis , S. A. 1990 . Quadratic programming is in NP . Inf. Process. Lett. , 36 : 73 – 77 .
   Google Scholar
• Vavasis , S. A. 1991 . Nonlinear Optimization: Complexity Issues , Oxford University Press .
   Google Scholar
• Weintraub , A. and Vera , J. 1991 . A cutting plane approach for chance constrained linear programs . Oper. Res. , 39 : 776 – 785 .
   Web of Science ®Google Scholar
• Xie , W. and Sahinidis , N. V. 2008 . A branch-and-bound algorithm for the continuous facility layout problem . Comput. Chem. Eng. , 32 : 1016 – 1028 .
   Web of Science ®Google Scholar
• Yamashita , M. , Fujisawa , K. and Kojima , M. 2002 . Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0) . Optim. Methods Softw. , 18 : 491 – 505 .
   Google Scholar