{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:25:02Z","timestamp":1787329502875,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we present three relaxations for binary quadratic polynomial programs. The first two relaxations, based on second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of nonconvex binary quadratic polynomial problems. From a practical point of view, due to the computational cost, semidefinite-based relaxations for binary quadratic polynomial problems can be used only to solve small to midsize instances. To improve the computational efficiency for solving such problems, we propose a third relaxation based purely on second-order cone programming. Computational tests on different classes of nonconvex binary quadratic polynomial problems, including quadratic knapsack problems, show that the second-order-cone-based relaxation outperforms the semidefinite-based relaxations that are proposed in the literature in terms of computational efficiency, and it is comparable in terms of bounds.<\/jats:p>","DOI":"10.1137\/100802190","type":"journal-article","created":{"date-parts":[[2011,3,31]],"date-time":"2011-03-31T21:26:54Z","timestamp":1301606814000},"page":"391-414","source":"Crossref","is-referenced-by-count":17,"title":["Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs"],"prefix":"10.1137","volume":"21","author":[{"given":"Bissan","family":"Ghaddar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan C.","family":"Vera","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,3,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1080\/00207729408928968"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2005.03.001"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587084"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00341-9"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02022095"},{"key":"R6","unstructured":"S. Burer,\n                      private communication\n                      , 2009."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400382467"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401383248"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614319"},{"key":"R10","first-page":"132","volume":"12","author":"Gallo G.","year":"1980","journal-title":"European J. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-2217","issn-type":"print"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.3.493"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009898604624"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585164"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1080\/10556780108805819"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025794313696"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1080\/1055678031000148696"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.46.125"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400380079"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.3.454"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0561-4"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.586"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"R24","unstructured":"T. S. Motzkin,\n                      The arithmetic-geometric inequality\n                      , in Inequalities (Proceedings of Symposium Wright Patterson Air Force Base, Ohio, 1965), Academic Press, New York, 1967, pp. 205\u2013224."},{"key":"R25","first-page":"1","volume":"12","author":"Nesterov Y.","year":"1997","journal-title":"Optim. Methods Softw.","ISSN":"https:\/\/id.crossref.org\/issn\/1055-6788","issn-type":"print"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02247879"},{"key":"R27","unstructured":"P. Parrilo,\n                      Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization\n                      , Ph.D. thesis, Department of Control and Dynamical Systems, California Institute of Technology, Pasadena, CA, 2000."},{"key":"R28","unstructured":"P. Parrilo,\n                      An Explicit Construction of Distinguished Representations of Polynomials Nonnegative over Finite Sets\n                      , Technical report, IfA Technical Report AUT02-02, Zurich, Switzerland, 2002."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/060\/08"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. F. Pe\u00f1a, J. C. Vera, and L. F. Zuluaga,\n                      Exploiting equalities in polynomial programming\n                      , Oper. Res. Lett., 36, 2008.","DOI":"10.1016\/j.orl.2007.05.011"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01096724"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.08.007"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450444614X"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"J. Sturm,\n                      Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones\n                      , Optim. Methods Softw., 1999, pp. 11-12.","DOI":"10.1080\/10556789908805766"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0672-6"},{"key":"R39","unstructured":"J. C. Vera, L. Zuluaga, and J. Pe\u00f1a,\n                      Positive polynomials on equality constrained domains\n                      , working paper."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe,\n                      Handbook of Semidefinite Programming\u2014Theory, Algorithms, and Applications\n                      , Springer, New York, 2000.","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/03060151X"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100802190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:20:16Z","timestamp":1787325616000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100802190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100802190"],"URL":"https:\/\/doi.org\/10.1137\/100802190","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}