{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:46:07Z","timestamp":1773798367971,"version":"3.50.1"},"reference-count":21,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2021,11,1]]},"DOI":"10.1587\/transfun.2020kep0007","type":"journal-article","created":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T22:07:26Z","timestamp":1625695646000},"page":"1526-1535","source":"Crossref","is-referenced-by-count":16,"title":["Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine"],"prefix":"10.1587","volume":"E104.A","author":[{"given":"Matthieu","family":"PARIZY","sequence":"first","affiliation":[{"name":"FUJITSU LABORATORIES LTD."}]},{"given":"Nozomu","family":"TOGAWA","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communications Engineering, Waseda University"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] A. Caprara, D. Pisinger, and P. Toth, \u201cExact solution of the quadratic knapsack problem,\u201d INFORMS J. Comput., vol.11, no.2, pp.125-137, 1999. 10.1287\/ijoc.11.2.125","DOI":"10.1287\/ijoc.11.2.125"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] D. Pisinger, \u201cThe quadratic knapsack problem \u2014 A survey,\u201d Discrete Appl. Math., vol.155, no.5, pp.623-648, 2007. 10.1016\/j.dam.2006.08.007","DOI":"10.1016\/j.dam.2006.08.007"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] C.E. Ferreira, A. Martin, C.C. de Souza, R. Weismantel, and L.A. Wolsey, \u201cFormulations and valid inequalities for the node capacitated graph partitioning problem,\u201d Math. Program., vol.74, no.3, pp.247-266, 1996. 10.1007\/bf02592198","DOI":"10.1007\/BF02592198"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] E.L. Johnson, A. Mehrotra, and G.L. Nemhauser, \u201cMin-cut clustering,\u201d Math. Program., vol.62, no.1-3, pp.133-151, 1993. 10.1007\/bf01585164","DOI":"10.1007\/BF01585164"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] D. Laughhunn, \u201cQuadratic binary programming with application to capital-budgeting problems,\u201d Oper. Res., vol.18, no.3, pp.454-461, 1970. 10.1287\/opre.18.3.454","DOI":"10.1287\/opre.18.3.454"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] J.M. Rhys, \u201cA selection problem of shared fixed costs and network flows,\u201d Manage. Sci., vol.17, no.3, pp.200-207, 1970. 10.1287\/mnsc.17.3.200","DOI":"10.1287\/mnsc.17.3.200"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] G. Gallo, P.L. Hammer, and B. Simeone, \u201cQuadratic knapsack problems,\u201d Combinatorial Optimization, pp.132-149, Springer Berlin Heidelberg, Berlin, Heidelberg, 1980. 10.1007\/bfb0120892","DOI":"10.1007\/BFb0120892"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] C. Patvardhan, S. Bansal, and A. Srivastav, \u201cSolving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm,\u201d J. Comput. Appl. Math., vol.285, pp.86-99, 2015. 10.1016\/j.cam.2015.02.016","DOI":"10.1016\/j.cam.2015.02.016"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] F. Glover, G. Kochenberger, and B. Alidaee, \u201cSolving quadratic knapsack problems by reformulation and tabu search: Single constraint case,\u201d Combinatorial and Global Optimization, vol.14, April 2002. 10.1142\/9789812778215_0008","DOI":"10.1142\/9789812778215_0008"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] M.W. Johnson, M.H.S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A.J. Berkley, J. Johansson, P. Bunyk, E.M. Chapple, C. Enderud, J.P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M.C. Thom, E. Tolkacheva, C.J.S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, \u201cQuantum annealing with manufactured spins,\u201d Nature, vol.473, no.7346, pp.194-198, May 2011. 10.1038\/nature10012","DOI":"10.1038\/nature10012"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] M. Babaeian, D.T. Nguyen, V. Demir, M. Akbulut, P.A. Blanche, Y. Kaneda, S. Guha, M.A. Neifeld, and N. Peyghambarian, \u201cA single shot coherent ising machine based on a network of injection-locked multicore fiber lasers,\u201d Nature Communications, vol.10, no.1, p.3516, Aug. 2019. 10.1038\/s41467-019-11548-4","DOI":"10.1038\/s41467-019-11548-4"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] R. Hamerly, T. Inagaki, P.L. McMahon, D. Venturelli, A. Marandi,T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K.i.Kawarabayashi, R.L. Byer, M.M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y. Yamamoto, \u201cExperimental investigation of performance differences between coherent ising machines and a quantum annealer,\u201d Sci. Adv., vol.5, no.5, 2019. 10.1126\/sciadv.aau0823","DOI":"10.1126\/sciadv.aau0823"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] A. Billionnet and F. Calmels, \u201cLinear programming for the 0-1 quadratic knapsack problem,\u201d Eur. J. Oper. Res., vol.92, no.2, pp.310-325, 1996. 10.1016\/0377-2217(94)00229-0","DOI":"10.1016\/0377-2217(94)00229-0"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H.G. Katzgraber, \u201cPhysics-inspired optimization for quadratic unconstrained problems using a digital annealer,\u201d Front. Phys., vol.7, p.48, 2019. 10.3389\/fphy.2019.00048","DOI":"10.3389\/fphy.2019.00048"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] S. Matsubara, M. Takatsu, T. Miyazawa, T. Shibasaki, Y. Watanabe, K. Takemoto, and H. Tamura, \u201cDigital annealer for high-speed solving of combinatorial optimization problems and its applications,\u201d 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), pp.667-672, 2020. 10.1109\/asp-dac47756.2020.9045100","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"16","unstructured":"[16] \u201cD-wave simulated annealing sampler.\u201d https:\/\/docs.ocean.dwavesys.com\/projects\/neal. Accessed: 2021-03-10."},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] K. Hukushima and K. Nemoto, \u201cExchange monte carlo method and application to spin glass simulations,\u201d J. Phy. Soc. Jpn., vol.65, no.6, pp.1604-1608, Jun 1996. 10.1143\/jpsj.65.1604","DOI":"10.1143\/JPSJ.65.1604"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] J. Bergstra, D. Yamins, and D.D. Cox, \u201cMaking a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures,\u201d Proc. 30th International Conference on International Conference on Machine Learning-Volume 28, ICML'13, p.I-115-I-123, JMLR.org, 2013.","DOI":"10.25080\/Majora-8b375195-003"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Y. Chen and J.K. Hao, \u201cIterated responsive threshold search for the quadratic multiple knapsack problem,\u201d Ann. Oper. Res., vol.226, no.1, pp.101-131, March 2015. 10.1007\/s10479-014-1720-5","DOI":"10.1007\/s10479-014-1720-5"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] Y. Chen and J. Hao, \u201cMemetic search for the generalized quadratic multiple knapsack problem,\u201d IEEE Trans. Evol. Comput., vol.20, no.6, pp.908-923, 2016. 10.1109\/tevc.2016.2546340","DOI":"10.1109\/TEVC.2016.2546340"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] C.R. Harris, K.J. Millman, S.J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N.J. Smith, R. Kern, M. Picus, S. Hoyer, M.H. van Kerkwijk, M. Brett, A. Haldane, J.F. del R'\u0131o, M. Wiebe, P. Peterson, P. G'erard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T.E. Oliphant, \u201cArray programming with NumPy,\u201d Nature, vol.585, no.7825, pp.357-362, Sept. 2020. 10.1038\/s41586-020-2649-2","DOI":"10.1038\/s41586-020-2649-2"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/11\/E104.A_2020KEP0007\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T16:52:13Z","timestamp":1725382333000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/11\/E104.A_2020KEP0007\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,1]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2020kep0007","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,1]]},"article-number":"2020KEP0007"}}