{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:40:36Z","timestamp":1725586836934},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_17","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"207-222","source":"Crossref","is-referenced-by-count":3,"title":["An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming"],"prefix":"10.1007","author":[{"given":"Bissan","family":"Ghaddar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan C.","family":"Vera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"17_CR1","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1287\/ijoc.1080.0270","volume":"20","author":"M.F. Anjos","year":"2008","unstructured":"Anjos, M.F., Vannelli, A.: Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J. Comp.\u00a020(4), 611\u2013617 (2008)","journal-title":"INFORMS J. Comp."},{"issue":"3","key":"17_CR2","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s11081-008-9050-6","volume":"10","author":"Y. Bai","year":"2009","unstructured":"Bai, Y., de Klerk, E., Pasechnik, D., Sotirov, R.: Exploiting group symmetry in truss topology optimization. Optimization and Engineering\u00a010(3), 331\u2013349 (2009)","journal-title":"Optimization and Engineering"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming\u00a058, 295\u2013324 (1993)","journal-title":"Mathematical Programming"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.01.025","volume":"201","author":"E. Klerk de","year":"2010","unstructured":"de Klerk, E.: Exploiting special structure in semidefinite programming: A survey of theory and applications. European Journal of Operational Research\u00a0201(1), 1\u201310 (2010)","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"17_CR5","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E. de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.: Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization\u00a012(4), 875\u2013892 (2002)","journal-title":"SIAM Journal on Optimization"},{"issue":"2-3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10107-006-0039-7","volume":"109","author":"E. Klerk de","year":"2007","unstructured":"de Klerk, E., Pasechnik, D., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular*-representation. Mathematical Programming\u00a0109(2-3), 613\u2013624 (2007)","journal-title":"Mathematical Programming"},{"issue":"2","key":"17_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-008-0246-5","volume":"122","author":"E. Klerk de","year":"2010","unstructured":"de Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Mathematical Programming\u00a0122(2), 225\u2013246 (2010)","journal-title":"Mathematical Programming"},{"issue":"1-3","key":"17_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K. Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.: Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra\u00a0192(1-3), 95\u2013128 (2004)","journal-title":"Journal of Pure and Applied Algebra"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Ghaddar, B., Anjos, M.F., Liers, F.: A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Annals of Operations Research (to appear)","DOI":"10.1007\/s10479-008-0481-4"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Ghaddar, B., Vera, J., Anjos, M.F.: Second-order cone relaxations for binary quadratic polynomial programs. SIAM Journal on Optimization (to appear)","DOI":"10.1137\/100802190"},{"key":"17_CR11","unstructured":"Hungerl\u00e4nder, P., Rendl, F.: Semidefinite relaxations of ordering problems. Technical report, Alpen-Adria-Universit\u00e4t Klagenfurt (August. 2010)"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. To appear in Mathematical Programming (2009)","DOI":"10.1007\/s10107-010-0402-6"},{"issue":"2","key":"17_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s10107-008-0210-4","volume":"9","author":"S. Kim","year":"2009","unstructured":"Kim, S., Kojima, M., Toint, P.: Recognizing underlying sparsity in optimization. Mathematical Programming\u00a09(2), 273\u2013303 (2009)","journal-title":"Mathematical Programming"},{"issue":"1","key":"17_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00245-007-9030-9","volume":"58","author":"K. Kobayashi","year":"2008","unstructured":"Kobayashi, K., Kim, S., Kojima, M.: Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP. Applied Mathematics and Optimization\u00a058(1), 69\u201388 (2008)","journal-title":"Applied Mathematics and Optimization"},{"issue":"1","key":"17_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-004-0554-3","volume":"103","author":"M. Kojima","year":"2003","unstructured":"Kojima, M., Kim, S., Waki, H.: Sparsity in sums of squares of polynomials. Mathematical Programming\u00a0103(1), 45\u201362 (2003)","journal-title":"Mathematical Programming"},{"issue":"1","key":"17_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10589-007-9112-2","volume":"42","author":"M. Kojima","year":"2009","unstructured":"Kojima, M., Muramatsu, M.: A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Computational Optimization and Applications\u00a042(1), 31\u201341 (2009)","journal-title":"Computational Optimization and Applications"},{"issue":"3","key":"17_CR17","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"J. Lasserre","year":"2001","unstructured":"Lasserre, J.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM Journal on Optimization\u00a012(3), 756\u2013769 (2001)","journal-title":"SIAM Journal on Optimization"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J. Lasserre","year":"2001","unstructured":"Lasserre, J.: Global optimization problems with polynomials and the problem of moments. SIAM Journal on Optimization\u00a011, 796\u2013817 (2001)","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"17_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1287\/moor.27.2.347.322","volume":"27","author":"J. Lasserre","year":"2002","unstructured":"Lasserre, J.: Semidefinite programming vs. LP relaxations for polynomial programming. Mathematics of Operations Research\u00a027(2), 347\u2013360 (2002)","journal-title":"Mathematics of Operations Research"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2001","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research\u00a028, 470\u2013496 (2001)","journal-title":"Mathematics of Operations Research"},{"issue":"Ser. A","key":"17_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-004-0561-4","volume":"109","author":"M. Laurent","year":"2007","unstructured":"Laurent, M.: Semidefinite representations for finite varieties. Mathematical Programming\u00a0109(Ser. A), 1\u201326 (2007)","journal-title":"Mathematical Programming"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S0927-0507(05)12008-8","volume-title":"Handbook on Discrete Optimization","author":"M. Laurent","year":"2005","unstructured":"Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Handbook on Discrete Optimization, vol.\u00a012, pp. 393\u2013514. Elsevier, Amsterdam (2005)"},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"17_CR24","unstructured":"Nesterov, Y.: Structure of non-negative polynomials and optimization problems. Technical report, Technical Report 9749, CORE (1997)"},{"issue":"4","key":"17_CR25","doi-asserted-by":"publisher","first-page":"1534","DOI":"10.1137\/060668791","volume":"19","author":"J. Nie","year":"2008","unstructured":"Nie, J., Demmel, J.: Sparse SOS relaxations for minimizing functions that are summation of small polynomials. SIAM Journal on Optimization\u00a019(4), 1534\u20131558 (2008)","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"17_CR26","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s10107-005-0672-6","volume":"106","author":"J. Nie","year":"2006","unstructured":"Nie, J., Demmel, J., Sturmfels, B.: Minimizing polynomials via sum of squares over the gradient ideal. Mathematical Programming: Series A and B\u00a0106(3), 587\u2013606 (2006)","journal-title":"Mathematical Programming: Series A and B"},{"key":"17_CR27","unstructured":"Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, Department of Control and Dynamical Systems, California Institute of Technology, Pasadena, California (2000)"},{"key":"17_CR28","unstructured":"Parrilo, P.: An explicit construction of distinguished representations of polynomials nonnegative over finite sets. Technical report, IFA Technical Report AUT02-02, Zurich - Switzerland (2002)"},{"issue":"2","key":"17_CR29","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"P. Parrilo","year":"2003","unstructured":"Parrilo, P.: Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming\u00a096(2), 293\u2013320 (2003)","journal-title":"Mathematical Programming"},{"key":"17_CR30","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1090\/dimacs\/060\/08","volume":"60","author":"P. Parrilo","year":"2003","unstructured":"Parrilo, P., Sturmfels, B.: Minimizing polynomial functions, algorithmic and quantitative real algebraic geometry. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a060, 83\u201389 (2003)","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Pe\u00f1a, J.F., Vera, J.C., Zuluaga, L.F.: Exploiting equalities in polynomial programming. Operations Research Letters\u00a036(2) (2008)","DOI":"10.1016\/j.orl.2007.05.011"},{"issue":"5","key":"17_CR32","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.dam.2006.08.007","volume":"155","author":"D. Pisinger","year":"2007","unstructured":"Pisinger, D.: The quadratic knapsack problem-a survey. Discrete Applied Mathematics\u00a0155(5), 623\u2013648 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"17_CR33","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S003614450444614X","volume":"49","author":"I. P\u00f3lik","year":"2007","unstructured":"P\u00f3lik, I., Terlaky, T.: A survey of the $\\mathcal{S}$ -lemma. SIAM Review\u00a049, 371\u2013418 (2007)","journal-title":"SIAM Review"},{"key":"17_CR34","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M. Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal\u00a042, 969\u2013984 (1993)","journal-title":"Indiana University Mathematics Journal"},{"key":"17_CR35","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-540-72792-7_23","volume":"4513","author":"F. Rendl","year":"2007","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for max-cut based on combining semidefinite and polyhedral relaxations. Integer programming and combinatorial optimization\u00a04513, 295\u2013309 (2007)","journal-title":"Integer programming and combinatorial optimization"},{"key":"17_CR36","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s10107-006-0038-8","volume":"109","author":"F. Rendl","year":"2007","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using bundle method. Mathematical Programming, Series B\u00a0109, 505\u2013524 (2007)","journal-title":"Mathematical Programming, Series B"},{"issue":"3","key":"17_CR37","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics\u00a03(3), 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"17_CR38","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1023\/A:1008237515535","volume":"10","author":"H.D. Sherali","year":"1997","unstructured":"Sherali, H.D., Tuncbilek, C.H.: Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems. Journal of Global Optimization\u00a010(4), 381\u2013390 (1997)","journal-title":"Journal of Global Optimization"},{"issue":"6","key":"17_CR39","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BF01070233","volume":"23","author":"N. Shor","year":"1987","unstructured":"Shor, N.: A class of global minimum bounds of polynomial functions. Cybernetics\u00a023(6), 731\u2013734 (1987)","journal-title":"Cybernetics"},{"key":"17_CR40","doi-asserted-by":"crossref","unstructured":"Sturm, J.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11\u201312 (1999)","DOI":"10.1080\/10556789908805766"},{"issue":"1","key":"17_CR41","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/050623802","volume":"17","author":"H. Waki","year":"2006","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization\u00a017(1), 218\u2013242 (2006)","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"17_CR42","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1377612.1377619","volume":"35","author":"H. Waki","year":"2008","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Transactions on Mathematical Software\u00a035(2), 15 (2008)","journal-title":"ACM Transactions on Mathematical Software"},{"key":"17_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4381-7","volume-title":"Handbook of Semidefinite programming -Theory, Algorithms, and Applications","author":"H. Wolkowicz","year":"2000","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite programming -Theory, Algorithms, and Applications. Kluwer, Dordrecht (2000)"},{"key":"17_CR44","unstructured":"Zuluaga, L.: A conic programming approach to polynomial optimization problems: Theory and applications. PhD thesis, The Tepper School of Business, Carnegie Mellon University, Pittsburgh (2004)"},{"key":"17_CR45","doi-asserted-by":"crossref","unstructured":"Zuluaga, L., Vera, J.C., Pe\u00f1a, J.: LMI approximations for cones of positive semidefinite forms. SIAM Journal on Optimization\u00a016(4) (2006)","DOI":"10.1137\/03060151X"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:16:04Z","timestamp":1560284164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}