{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:41:22Z","timestamp":1780090882166,"version":"3.54.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Grant-in-Aid for JSPS Research Fellowship","award":["JP17J07365"],"award-info":[{"award-number":["JP17J07365"]}]},{"name":"NRF","award":["2017-R1A2B2005119"],"award-info":[{"award-number":["2017-R1A2B2005119"]}]},{"name":"Grant-in-Aid for Scientific Research","award":["26242027"],"award-info":[{"award-number":["26242027"]}]},{"name":"Grant-in-Aid for Scientific Research","award":["15K00031"],"award-info":[{"award-number":["15K00031"]}]},{"name":"the Ministry of Education, Singapore, Academic Research Fund","award":["R-146-000-256-114"],"award-info":[{"award-number":["R-146-000-256-114"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box, and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a doubly nonnegative relaxation of the POP, and then solves the COP by applying the bisection and projection method. The COP is expressed with a linear objective function and constraints described as a single hyperplane and two cones, which are the Cartesian product of positive semidefinite cones and a polyhedral cone induced from the BBC constraints. BBCPOP aims to compute a tight lower bound for the optimal value of a large-scale POP in the class that is beyond the comfort zone of existing software packages. The robustness, reliability, and efficiency of BBCPOP are demonstrated in comparison to the state-of-the-art software SDP package SDPNAL+ on randomly generated sparse POPs of degree 2 and 3 with up to a few thousands variables, and ones of degree from 5 to 8 with up to a few hundred variables. Numerical results on BBC-constrained POPs that arise from quadratic assignment problems are also reported. The software package BBCPOP is available at https:\/\/sites.google.com\/site\/bbcpop1\/.<\/jats:p>","DOI":"10.1145\/3309988","type":"journal-article","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T19:52:26Z","timestamp":1564516346000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Algorithm 996"],"prefix":"10.1145","volume":"45","author":[{"given":"Naoki","family":"Ito","sequence":"first","affiliation":[{"name":"Fast Retailing Co., LTD., Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sunyoung","family":"Kim","sequence":"additional","affiliation":[{"name":"Ewha W. University, Seoul, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masakazu","family":"Kojima","sequence":"additional","affiliation":[{"name":"Chuo University, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akiko","family":"Takeda","sequence":"additional","affiliation":[{"name":"University of Tokyo, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0894-3"},{"key":"e_1_2_2_2_1","volume-title":"International Series in Operations Research and Management Science","volume":"166","author":"Anjos M. F.","unstructured":"M. F. Anjos and J. B. Lasserre . 2012. Handbook on Semidefinite, Conic, and Polynomial Optimization . International Series in Operations Research and Management Science , Vol. 166 . Springer. M. F. Anjos and J. B. Lasserre. 2012. Handbook on Semidefinite, Conic, and Polynomial Optimization. International Series in Operations Research and Management Science, Vol. 166. Springer."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898340299"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-016-9879-0"},{"key":"e_1_2_2_5_1","volume-title":"Research Report B-476. Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-Ku","author":"Arima N.","year":"2014","unstructured":"N. Arima , S. Kim , M. Kojima , and K. C. Toh . 2014 . Lagrangian-conic Relaxations, Part II: Applications to Polynomial Optimization Problems . Research Report B-476. Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-Ku , Tokyo. N. Arima, S. Kim, M. Kojima, and K. C. Toh. 2014. Lagrangian-conic Relaxations, Part II: Applications to Polynomial Optimization Problems. Research Report B-476. Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-Ku, Tokyo."},{"key":"e_1_2_2_6_1","first-page":"161","article-title":"Lagrangian-conic relaxations, part I: A unified framework and its applications to quadratic optimization problems","volume":"14","author":"Arima N.","year":"2018","unstructured":"N. Arima , S. Kim , M. Kojima , and K. C. Toh . 2018 . Lagrangian-conic relaxations, part I: A unified framework and its applications to quadratic optimization problems . Pacific J. of Optim. 14 , 1 (2018), 161 -- 192 . N. Arima, S. Kim, M. Kojima, and K. C. Toh. 2018. Lagrangian-conic relaxations, part I: A unified framework and its applications to quadratic optimization problems. Pacific J. of Optim. 14, 1 (2018), 161--192.","journal-title":"Pacific J. of Optim."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"e_1_2_2_8_1","unstructured":"D. Bertsekas A. Nedic and A. E. Ozdaglar. 2003. Convex Analysis and Optimization. Athena Scientific.  D. Bertsekas A. Nedic and A. E. Ozdaglar. 2003. Convex Analysis and Optimization. Athena Scientific."},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"J. R. S. Blair and B. Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation J. W. H. Liu A. George and J. R. Gilbert (Eds.). Springer-Verlag New York NY 1--29.  J. R. S. Blair and B. Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation J. W. H. Liu A. George and J. R. Gilbert (Eds.). Springer-Verlag New York NY 1--29.","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0663-y"},{"key":"e_1_2_2_11_1","volume-title":"Research Report B-448. Department of Mathematical and Computing Sciences","author":"Fujisawa K.","year":"2008","unstructured":"K. Fujisawa , M. Fukuda , K. Kobayashi , M. Kojima , K. Nakata , M. Nakata , and M. Yamashita . 2008 . SDPA (SemiDefinite Programming Algorithm) User\u2019s Manual \u2014 Version 7.0.5. Research Report B-448. Department of Mathematical and Computing Sciences , Tokyo Institute of Technology, Oh- Okayama , Meguro-Ku, Tokyo . K. Fujisawa, M. Fukuda, K. Kobayashi, M. Kojima, K. Nakata, M. Nakata, and M. Yamashita. 2008. SDPA (SemiDefinite Programming Algorithm) User\u2019s Manual \u2014 Version 7.0.5. Research Report B-448. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-Ku, Tokyo."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936015"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2015.2390037"},{"key":"e_1_2_2_15_1","volume-title":"Gregor Hendel, et al.","author":"Gleixner Ambros","year":"2018","unstructured":"Ambros Gleixner , Michael Bastubbe , Leon Eifler , Tristan Gally , Gerald Gamrath , Robert Lion Gottwald , Gregor Hendel, et al. 2018 . SCIP : Solving Constraint Integer Programs. Retrieved July 9, 2019 from http:\/\/scip.zib.de. Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, et al. 2018. SCIP: Solving Constraint Integer Programs. Retrieved July 9, 2019 from http:\/\/scip.zib.de."},{"key":"e_1_2_2_16_1","unstructured":"P. Hahn and M. Anjos. 2019. QAPLIB\u2014A Quadratic Assignment Problem Library. Retrieved July 9 2019 from http:\/\/www.seas.upenn.edu\/qaplib.  P. Hahn and M. Anjos. 2019. QAPLIB\u2014A Quadratic Assignment Problem Library. Retrieved July 9 2019 from http:\/\/www.seas.upenn.edu\/qaplib."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779363"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-018-0676-4"},{"key":"e_1_2_2_20_1","first-page":"1","article-title":"A unified formulation and fast accelerated proximal gradient method for classification","volume":"18","author":"Ito N.","year":"2017","unstructured":"N. Ito , A. Takeda , and K.-C. Toh . 2017 . A unified formulation and fast accelerated proximal gradient method for classification . J. Mach. Learn. Res. 18 , 16 (2017), 1 -- 49 . N. Ito, A. Takeda, and K.-C. Toh. 2017. A unified formulation and fast accelerated proximal gradient method for classification. J. Mach. Learn. Res. 18, 16 (2017), 1--49.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09)","author":"Iwata S.","unstructured":"S. Iwata and K. Nagano . 2009. Submodular function minimization under covering constraints . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09) . 671--680. S. Iwata and K. Nagano. 2009. Submodular function minimization under covering constraints. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09). 671--680."},{"key":"e_1_2_2_22_1","volume-title":"Research Report B-483. Department of Mathematical and Computing Sciences","author":"Kim S.","year":"2016","unstructured":"S. Kim , M. Kojima , and K. C. Toh . 2016 a. Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints. Research Report B-483. Department of Mathematical and Computing Sciences , Tokyo Institute of Technology, Oh- Okayama , Meguro-Ku, Tokyo . S. Kim, M. Kojima, and K. C. Toh. 2016a. Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints. Research Report B-483. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-Ku, Tokyo."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0874-5"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"e_1_2_2_26_1","volume-title":"Positive Polynomials and Their Applications","author":"Lasserre J. B.","unstructured":"J. B. Lasserre . 2010. Moments , Positive Polynomials and Their Applications . Imperial College Press Optimization Series, Vol . 1. Imperial College Press . J. B. Lasserre. 2010. Moments, Positive Polynomials and Their Applications. Imperial College Press Optimization Series, Vol. 1. Imperial College Press."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13675-015-0050-y"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936019"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9802-0"},{"key":"e_1_2_2_30_1","first-page":"238","article-title":"D\u00e9composition orthogonale d\u2019un espace hilbertien selon deux cones mutuellement polaires","volume":"255","author":"Moreau J. J.","year":"1962","unstructured":"J. J. Moreau . 1962 . D\u00e9composition orthogonale d\u2019un espace hilbertien selon deux cones mutuellement polaires . C. R. Acad. Sci. 255 (1962), 238 -- 240 . J. J. Moreau. 1962. D\u00e9composition orthogonale d\u2019un espace hilbertien selon deux cones mutuellement polaires. C. R. Acad. Sci. 255 (1962), 238--240.","journal-title":"C. R. Acad. Sci."},{"key":"e_1_2_2_31_1","volume-title":"The MOSEK Optimization Software. Retrieved","author":"MOSEK.","year":"2019","unstructured":"MOSEK. 2017. The MOSEK Optimization Software. Retrieved July 9, 2019 from https:\/\/www.mosek.com\/. MOSEK. 2017. The MOSEK Optimization Software. Retrieved July 9, 2019 from https:\/\/www.mosek.com\/."},{"key":"e_1_2_2_32_1","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate O(1\/k<sup>2<\/sup>)","volume":"27","author":"Nesterov Y.","year":"1983","unstructured":"Y. Nesterov . 1983 . A method of solving a convex programming problem with convergence rate O(1\/k<sup>2<\/sup>) . Soviet Mathematics Doklady 27 , 2 (1983), 372 -- 376 . Y. Nesterov. 1983. A method of solving a convex programming problem with convergence rate O(1\/k<sup>2<\/sup>). Soviet Mathematics Doklady 27, 2 (1983), 372--376.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/110825844"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9150-3"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-018-0148-3"},{"key":"e_1_2_2_36_1","unstructured":"A. Papachristodoulou J. Anderson G. Valmorbida S. Prajna P. Seiler and P. Parrilo. 2016. Sums of Squares Optimization Toolbox for Matlab -- User\u2019s Guide. Department of Engineering Science University of Oxford Oxford UK.  A. Papachristodoulou J. Anderson G. Valmorbida S. Prajna P. Seiler and P. Parrilo. 2016. Sums of Squares Optimization Toolbox for Matlab -- User\u2019s Guide. Department of Engineering Science University of Oxford Oxford UK."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/050637467"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2009.01.002"},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC\u201917)","author":"Reid G.","unstructured":"G. Reid , F. Wang , and H. Wolkowicz . 2017. An SDP-based method for the real radical ideal membership test . In Proceedings of the International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC\u201917) . G. Reid, F. Wang, and H. Wolkowicz. 2017. An SDP-based method for the real radical ideal membership test. In Proceedings of the International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC\u201917)."},{"key":"e_1_2_2_41_1","volume-title":"a MATLAB toolbox for optimization over symmetric cones. Optim. Methods and Softw. 11--12","author":"Sturm J. F.","year":"1999","unstructured":"J. F. Sturm . 1999. Se DuMi 1.02 , a MATLAB toolbox for optimization over symmetric cones. Optim. Methods and Softw. 11--12 ( 1999 ), 625--653. J. F. Sturm. 1999. SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods and Softw. 11--12 (1999), 625--653."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2017.1335312"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377612.1377619"},{"key":"e_1_2_2_46_1","unstructured":"H. Waki S. Kim M. Kojima M. Muramatsu H. Sugimoto and M. Yamashita. 2009. User Manual for SparsePOP: A Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems (B-414 Ed.). Tokyo Institute of Technology.  H. Waki S. Kim M. Kojima M. Muramatsu H. Sugimoto and M. Yamashita. 2009. User Manual for SparsePOP: A Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems (B-414 Ed.). Tokyo Institute of Technology."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-009-9269-y"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0121-6"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0082-6"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009795911987"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/080718206"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:36Z","timestamp":1750204416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309988"}},"subtitle":["BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems With Binary, Box, and Complementarity Constraints"],"short-title":[],"issued":{"date-parts":[[2019,7,30]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3309988"],"URL":"https:\/\/doi.org\/10.1145\/3309988","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,30]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}