{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:48:25Z","timestamp":1780674505539,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T00:00:00Z","timestamp":1564790400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T00:00:00Z","timestamp":1564790400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s11590-019-01460-7","type":"journal-article","created":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T10:02:37Z","timestamp":1564826557000},"page":"1557-1569","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions"],"prefix":"10.1007","volume":"14","author":[{"given":"Amit","family":"Verma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Lewis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,8,3]]},"reference":[{"key":"1460_CR1","unstructured":"Datasets. https:\/\/github.com\/amitverma1509\/QUBO . Accessed: 12 Nov 2018"},{"key":"1460_CR2","unstructured":"Qbsolv, a decomposing solver. https:\/\/github.com\/dwavesystems\/qbsolv . Accessed 09 Nov 2018"},{"key":"1460_CR3","unstructured":"Quantum computing | d-wave systems. https:\/\/www.dwavesys.com\/quantum-computing . Accessed 09 Nov 2018"},{"key":"1460_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2016.01.001","volume":"203","author":"M Anthony","year":"2016","unstructured":"Anthony, M., Boros, E., Crama, Y., Gruber, A.: Quadratization of symmetric pseudo-boolean functions. Discrete Appl. Math. 203, 1\u201312 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"1460_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10107-016-1032-4","volume":"162","author":"M Anthony","year":"2017","unstructured":"Anthony, M., Boros, E., Crama, Y., Gruber, A.: Quadratic reformulations of nonlinear binary optimization problems. Math. Program. 162(1\u20132), 115\u2013144 (2017)","journal-title":"Math. Program."},{"key":"1460_CR6","doi-asserted-by":"crossref","unstructured":"Boros, E., Crama, Y., Rodriguez\u00a0Heck, E.: Compact quadratizations for pseudo-boolean functions (2018)","DOI":"10.1007\/s10878-019-00511-0"},{"key":"1460_CR7","unstructured":"Boros, E., Gruber, A.: On quadratization of pseudo-boolean functions. (2014). arXiv:1404.6538"},{"issue":"1\u20133","key":"1460_CR8","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Appl. Math. 123(1\u20133), 155\u2013225 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1460_CR9","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/050646500","volume":"18","author":"C Buchheim","year":"2007","unstructured":"Buchheim, C., Rinaldi, G.: Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM J. Optim. 18(4), 1398\u20131413 (2007)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1460_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.ejor.2011.06.041","volume":"215","author":"CT Chang","year":"2011","unstructured":"Chang, C.T.: Multi-choice goal programming with utility functions. Eur. J. Oper. Res. 215(2), 439\u2013445 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"1460_CR11","unstructured":"Coffrin, C., Nagarajan, H., Bent, R.: Ising processing units: potential and challenges for discrete optimization. (2017). arXiv:1707.00355"},{"key":"1460_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511852008","volume-title":"Boolean Functions: Theory, Algorithms, and Applications","author":"Y Crama","year":"2011","unstructured":"Crama, Y., Hammer, P.L.: Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, Cambridge (2011)"},{"issue":"7","key":"1460_CR13","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1109\/TPAMI.2014.2382109","volume":"37","author":"A Fix","year":"2015","unstructured":"Fix, A., Gruber, A., Boros, E., Zabih, R.: A hypergraph-based reduction for higher-order binary markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. 37(7), 1387\u20131395 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"1460_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF03006558","volume":"11","author":"R Fortet","year":"1960","unstructured":"Fortet, R.: L\u2019algebre de boole et ses applications en recherche op\u00e9rationnelle. Trabajos de Estadistica y de Investigaci\u00f3n Operativa 11(2), 111\u2013118 (1960)","journal-title":"Trabajos de Estadistica y de Investigaci\u00f3n Operativa"},{"key":"1460_CR15","unstructured":"Freedman, D., Drineas, P.: Energy minimization via graph cuts: Settling what is possible. In: 2005 IEEE computer society conference on computer vision and pattern recognition, CVPR 2005 , vol. 2, pp. 939\u2013946. IEEE (2005)"},{"issue":"4","key":"1460_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1504\/IJMHEUR.2011.044356","volume":"1","author":"F Glover","year":"2011","unstructured":"Glover, F., Hao, J.K., Kochenberger, G.A.: Polynomial unconstrained binary optimisation-part 2. IJMHeur 1(4), 317\u2013354 (2011)","journal-title":"IJMHeur"},{"issue":"3","key":"1460_CR17","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/j.ejor.2017.08.025","volume":"265","author":"F Glover","year":"2018","unstructured":"Glover, F., Lewis, M., Kochenberger, G.: Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems. Eur. J. Oper. Res. 265(3), 829\u2013842 (2018)","journal-title":"Eur. J. Oper. Res."},{"key":"1460_CR18","volume-title":"Boolean Methods in Operations Research and Related Areas","author":"PL Hammer","year":"2012","unstructured":"Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas, vol. 7. Springer Science & Business Media, Berlin (2012)"},{"issue":"6","key":"1460_CR19","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","volume":"33","author":"H Ishikawa","year":"2011","unstructured":"Ishikawa, H.: Transformation of general binary mrf minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33(6), 1234\u20131249 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"1460_CR20","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., Hao, J.K., Glover, F., Lewis, M., L\u00fc, Z., Wang, H., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58\u201381 (2014)","journal-title":"J. Comb. Optim."},{"issue":"05","key":"1460_CR21","doi-asserted-by":"publisher","first-page":"L05003","DOI":"10.1088\/1742-5468\/2010\/05\/L05003","volume":"2010","author":"F Liers","year":"2010","unstructured":"Liers, F., Marinari, E., Pagacz, U., Ricci-Tersenghi, F., Schmitz, V.: A non-disordered glassy model with a tunable interaction range. J. Stat. Mech. Theory Exp. 2010(05), L05003 (2010)","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"1460_CR22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"key":"1460_CR23","doi-asserted-by":"crossref","unstructured":"Rodriguez\u00a0Heck, E.: Linear and quadratic reformulations of nonlinear optimization problems in binary variables. Ph.D. thesis, Universite de Liege, Liege, Belgium (2018)","DOI":"10.1007\/s10288-018-0392-4"},{"key":"1460_CR24","first-page":"71","volume":"17","author":"IG Rosenberg","year":"1975","unstructured":"Rosenberg, I.G.: Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d\u2019etudes de Recherche Operationnelle 17, 71\u201374 (1975)","journal-title":"Cahiers du Centre d\u2019etudes de Recherche Operationnelle"},{"key":"1460_CR25","doi-asserted-by":"crossref","unstructured":"Vert, D., Sirdey, R., Louise, S.: On the limitations of the chimera graph topology in using analog quantum computers. In: Proceedings of the 16th ACM international conference on computing frontiers, pp. 226\u2013229. ACM (2019)","DOI":"10.1145\/3310273.3322830"},{"issue":"4","key":"1460_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.3390\/a12040077","volume":"12","author":"T Vyskocil","year":"2019","unstructured":"Vyskocil, T., Djidjev, H.: Embedding equality constraints of optimization problems into a quantum annealer. Algorithms 12(4), 77 (2019)","journal-title":"Algorithms"},{"key":"1460_CR27","doi-asserted-by":"crossref","unstructured":"Vysko\u010dil, T., Pakin, S., Djidjev, H.N.: Embedding inequality constraints for quantum annealing optimization. In: International workshop on quantum technology and optimization problems, pp. 11\u201322. Springer (2019)","DOI":"10.1007\/978-3-030-14082-3_2"},{"issue":"3","key":"1460_CR28","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.ejor.2012.07.012","volume":"223","author":"Y Wang","year":"2012","unstructured":"Wang, Y., L\u00fc, Z., Glover, F., Hao, J.K.: Path relinking for unconstrained binary quadratic programming. Eur. J. Oper. Res. 223(3), 595\u2013604 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"6","key":"1460_CR29","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1287\/opre.15.6.1171","volume":"15","author":"LJ Watters","year":"1967","unstructured":"Watters, L.J.: Letter to the editor-reduction of integer polynomial programming problems to zero-one linear programming problems. Operations Research 15(6), 1171\u20131174 (1967)","journal-title":"Operations Research"},{"key":"1460_CR30","doi-asserted-by":"publisher","unstructured":"Zangwill, W.I.: Media Selection by Decision Programming. In: Mathematical Models in Marketing. Lecture Notes in Economics and Mathematical Systems (Operations Research), vol. 132, Springer, Berlin, Heidelberg, (1976). https:\/\/doi.org\/10.1007\/978-3-642-51565-1_44","DOI":"10.1007\/978-3-642-51565-1_44"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-019-01460-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-019-01460-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-019-01460-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,25]],"date-time":"2022-09-25T03:54:58Z","timestamp":1664078098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-019-01460-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,3]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1460"],"URL":"https:\/\/doi.org\/10.1007\/s11590-019-01460-7","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,3]]},"assertion":[{"value":"18 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}