{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:28:08Z","timestamp":1767983288655,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:00:00Z","timestamp":1641168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:00:00Z","timestamp":1641168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s12532-021-00206-w","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:02:47Z","timestamp":1641168167000},"page":"85-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dantzig\u2013Wolfe reformulations for binary quadratic problems"],"prefix":"10.1007","volume":"14","author":[{"given":"Alberto","family":"Ceselli","sequence":"first","affiliation":[]},{"given":"Lucas","family":"L\u00e9tocart","sequence":"additional","affiliation":[]},{"given":"Emiliano","family":"Traversi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,3]]},"reference":[{"issue":"2","key":"206_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.disopt.2004.03.006","volume":"1","author":"W Adams","year":"2004","unstructured":"Adams, W., Forrester, R., Glover, F.: Comparisons and enhancement strategies for linearizing mixed 0\u20131 quadratic programs. Discret. Optim. 1(2), 99\u2013120 (2004). https:\/\/doi.org\/10.1016\/j.disopt.2004.03.006","journal-title":"Discret. Optim."},{"issue":"1","key":"206_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1109\/59.574929","volume":"12","author":"M Aganagic","year":"1997","unstructured":"Aganagic, M., Mokhtari, S.: Security constrained economic dispatch using nonlinear Dantzig\u2013Wolfe decomposition. IEEE Trans. Power Syst. 12(1), 105\u2013112 (1997)","journal-title":"IEEE Trans. Power Syst."},{"issue":"1","key":"206_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10479-011-0969-1","volume":"199","author":"A Ahlat\u00e7ioglu","year":"2012","unstructured":"Ahlat\u00e7ioglu, A., Bussieck, M., Esen, M., Guignard, M., Jagla, J.H., Meeraus, A.: Combining QCR and CHR for convex quadratic pure 0\u20131 programming problems with linear constraints. Ann. OR 199(1), 33\u201349 (2012)","journal-title":"Ann. OR"},{"key":"206_CR4","doi-asserted-by":"publisher","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","volume":"28","author":"E Balas","year":"1980","unstructured":"Balas, E., Zemel, E.: An algorithm for large zero-one knapsack problems. Oper. Res. 28, 1130\u20131154 (1980)","journal-title":"Oper. Res."},{"issue":"2","key":"206_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s10479-018-3067-9","volume":"284","author":"S Basso","year":"2020","unstructured":"Basso, S., Ceselli, A., Tettamanzi, A.: Random sampling and machine learning to understand good decompositions. Ann. Oper. Res. 284(2), 501\u2013526 (2020). https:\/\/doi.org\/10.1007\/s10479-018-3067-9","journal-title":"Ann. Oper. Res."},{"issue":"1\u20132","key":"206_CR6","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10107-014-0761-5","volume":"149","author":"M Bergner","year":"2015","unstructured":"Bergner, M., Caprara, A., Ceselli, A., Furini, F., L\u00fcbbecke, M., Malaguti, E., Traversi, E.: Automatic Dantzig\u2013Wolfe reformulation of mixed integer programs. Math. Program. 149(1\u20132), 391\u2013424 (2015)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"206_CR7","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-010-0381-7","volume":"131","author":"A Billionnet","year":"2012","unstructured":"Billionnet, A., Elloumi, S., Lambert, A.: Extending the QCR method to general mixed-integer programs. Math. Program. 131(1\u20132), 381\u2013401 (2012)","journal-title":"Math. Program."},{"key":"206_CR8","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1016\/j.dam.2007.12.007","volume":"157","author":"A Billionnet","year":"2009","unstructured":"Billionnet, A., Elloumi, S., Plateau, M.C.: Improving the performance of standard solvers via a tighter convex reformulation of constrained quadratic 0\u20131 programs: the QCR method. Discret. Appl. Math. 157, 1185\u20131197 (2009)","journal-title":"Discret. Appl. Math."},{"key":"206_CR9","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/S0377-2217(03)00244-3","volume":"157","author":"A Billionnet","year":"2004","unstructured":"Billionnet, A., Soutif, E.: An exact method based on Lagrangean decomposition for the 0\u20131 quadratic knapsak problem. Eur. J. Oper. Res. 157, 565\u2013575 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"206_CR10","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-012-0534-y","volume":"141","author":"C Buchheim","year":"2013","unstructured":"Buchheim, C., Wiegele, A.: Semidefinite relaxations for non-convex quadratic mixed-integer programming. Math. Program. 141(1\u20132), 435\u2013452 (2013). https:\/\/doi.org\/10.1007\/s10107-012-0534-y","journal-title":"Math. Program."},{"issue":"2","key":"206_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1287\/ijoc.11.2.125","volume":"11","author":"A Caprara","year":"1999","unstructured":"Caprara, A., Pisinger, D., Toth, P.: Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2), 125\u2013137 (1999)","journal-title":"INFORMS J. Comput."},{"key":"206_CR12","first-page":"1","volume":"5923","author":"A Ceselli","year":"2017","unstructured":"Ceselli, A., L\u00e9tocart, L., Traversi, E.: Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case. Tech. Rep. 5923, 1\u201332 (2017)","journal-title":"Tech. Rep."},{"key":"206_CR13","doi-asserted-by":"publisher","unstructured":"Ceselli, A., L\u00e9tocart, L., Traversi, E.: Binary quadratic problem decomposition methods\u2014kQKP dataset\u2014UNIMI dataverse (2021). https:\/\/doi.org\/10.13130\/RD_UNIMI\/3QA23K","DOI":"10.13130\/RD_UNIMI\/3QA23K"},{"key":"206_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"G Dantzig","year":"1960","unstructured":"Dantzig, G., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8, 101\u2013111 (1960)","journal-title":"Oper. Res."},{"key":"206_CR15","volume-title":"Column Generation","author":"G Desaulniers","year":"2006","unstructured":"Desaulniers, G., Desrosiers, J., Solomon, M.: Column Generation, vol. 5. Springer Science & Business Media, Berlin (2006)"},{"key":"206_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02241754","volume":"28","author":"D Fayard","year":"1982","unstructured":"Fayard, D., Plateau, G.: Algorithm 47: an algorithm for the solution of the 0\u20131 knapsack problem. Computing 28, 269\u2013287 (1982)","journal-title":"Computing"},{"issue":"1","key":"206_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10288-006-0011-7","volume":"5","author":"A Faye","year":"2007","unstructured":"Faye, A., Roupin, F.: Partial Lagrangian relaxation for general quadratic programming. 4OR 5(1), 75\u201388 (2007)","journal-title":"4OR"},{"key":"206_CR18","first-page":"17","volume":"4","author":"R Fortet","year":"1960","unstructured":"Fortet, R.: Applications de lalg\u00e8bre de boole en recherche op\u00e9rationnelle. Revue Fran\u00e7aise de Recherche Op\u00e9rationnelle 4, 17\u201326 (1960)","journal-title":"Revue Fran\u00e7aise de Recherche Op\u00e9rationnelle"},{"key":"206_CR19","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-13193-6_21","volume-title":"Experimental Algorithms","author":"G Gamrath","year":"2010","unstructured":"Gamrath, G., L\u00fcbbecke, M.: Experiments with a generic Dantzig\u2013Wolfe decomposition for integer programs. In: Festa, P. (ed.) Experimental Algorithms, pp. 239\u2013252. Springer, Berlin, Heidelberg (2010)"},{"issue":"4","key":"206_CR20","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/mnsc.22.4.455","volume":"22","author":"F Glover","year":"1975","unstructured":"Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manag. Sci. 22(4), 455\u2013460 (1975)","journal-title":"Manag. Sci."},{"issue":"1","key":"206_CR21","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10479-005-3973-5","volume":"140","author":"S Gueye","year":"2005","unstructured":"Gueye, S., Michelon, P.: Miniaturized linearizations for quadratic 0\/1 problems. Ann. Oper. Res. 140(1), 235\u2013261 (2005). https:\/\/doi.org\/10.1007\/s10479-005-3973-5","journal-title":"Ann. Oper. Res."},{"key":"206_CR22","unstructured":"Gurobi Optimization: Gurobi (2018). http:\/\/www.gurobi.com\/. Version 8.0, http:\/\/www.gurobi.com\/"},{"key":"206_CR23","doi-asserted-by":"crossref","unstructured":"Holmberg, K.: MINLP: generalized cross decomposition. In: Encyclopedia of Optimization, pp. 2148\u20132155. Springer (2009)","DOI":"10.1007\/978-0-387-74759-0_380"},{"key":"206_CR24","unstructured":"IBM: Cplex (2018). Version 12.8.0. https:\/\/www-01.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/"},{"key":"206_CR25","volume-title":"50 Years of Integer Programming 1958\u20132008","year":"2009","unstructured":"J\u00fcnger, M., Liebling, T., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.): 50 Years of Integer Programming 1958\u20132008. Springer, Berlin (2009)"},{"issue":"4","key":"206_CR26","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1145\/3005345","volume":"43","author":"N Krislock","year":"2017","unstructured":"Krislock, N., Malick, J., Roupin, F.: Biqcrunch: a semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. Math. Softw. 43(4), 32:1-32:23 (2017). https:\/\/doi.org\/10.1145\/3005345","journal-title":"ACM Trans. Math. Softw."},{"issue":"1","key":"206_CR27","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0167-6377(99)00059-0","volume":"26","author":"S Lawphongpanich","year":"2000","unstructured":"Lawphongpanich, S.: Simplicial with truncated Dantzig\u2013Wolfe decomposition for nonlinear multicommodity network flow problems with side constraints. Oper. Res. Lett. 26(1), 33\u201341 (2000)","journal-title":"Oper. Res. Lett."},{"key":"206_CR28","unstructured":"Lemar\u00e9chal, C., Oustry, F.: Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Ph.D. thesis, INRIA (1999)"},{"issue":"3","key":"206_CR29","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/PL00011429","volume":"90","author":"C Lemar\u00e9chal","year":"2001","unstructured":"Lemar\u00e9chal, C., Renaud, A.: A geometric study of duality gaps, with applications. Math. Program. 90(3), 399\u2013427 (2001)","journal-title":"Math. Program."},{"issue":"1","key":"206_CR30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1590\/S0101-74382014000100005","volume":"34","author":"L L\u00e9tocart","year":"2014","unstructured":"L\u00e9tocart, L., Plateau, M.C., Plateau, G.: An efficient hybrid heuristic method for the 0\u20131 exact $$k$$-item quadratic knapsack problem. Pesquisa Operacional 34(1), 49\u201372 (2014)","journal-title":"Pesquisa Operacional"},{"key":"206_CR31","doi-asserted-by":"crossref","unstructured":"L\u00e9tocart, L., Wiegele, A.: Exact solution methods for the k-item quadratic knapsack problem. In: Lecture Notes in Computer Science, Combinatorial Optimization, vol. 9849, pp. 166\u2013176. Springer (2016)","DOI":"10.1007\/978-3-319-45587-7_15"},{"issue":"3","key":"206_CR32","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10288-006-0015-3","volume":"5","author":"L Liberti","year":"2007","unstructured":"Liberti, L.: Compact linearization for binary quadratic problems. 4OR 5(3), 231\u2013245 (2007). https:\/\/doi.org\/10.1007\/s10288-006-0015-3","journal-title":"4OR"},{"key":"206_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10898-012-9874-7","volume":"57","author":"R Misener","year":"2013","unstructured":"Misener, R., Floudas, C.: GloMIQO: global mixed-integer quadratic optimizer. J. Global Optim. 57, 3\u201350 (2013)","journal-title":"J. Global Optim."},{"key":"206_CR34","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. Discret. Appl. Math. 155, 623\u2013648 (2007)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"206_CR35","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1287\/ijoc.1050.0172","volume":"19","author":"D Pisinger","year":"2007","unstructured":"Pisinger, D., Rasmussen, A.B., Sandvik, R.: Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput. 19(2), 280\u2013290 (2007)","journal-title":"INFORMS J. Comput."},{"key":"206_CR36","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s10288-007-0044-6","volume":"6","author":"MC Plateau","year":"2008","unstructured":"Plateau, M.C.: Quadratic convex reformulations for quadratic 0\u20131 programming. 4OR 6, 187\u2013190 (2008)","journal-title":"4OR"},{"issue":"2","key":"206_CR37","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2), 307 (2010)","journal-title":"Math. Program."},{"key":"206_CR38","unstructured":"SCIP: Scip (2018). http:\/\/scip.zib.de\/. Version 6.0.0, http:\/\/scip.zib.de\/"},{"issue":"10","key":"206_CR39","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"H Sherali","year":"1986","unstructured":"Sherali, H., Adams, W.: A tight linearization and an algorithm for 0\u20131 quadratic programming problems. Manag. Sci. 32(10), 1274\u20131290 (1986)","journal-title":"Manag. Sci."},{"issue":"3","key":"206_CR40","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.orl.2005.05.009","volume":"34","author":"F Vanderbeck","year":"2006","unstructured":"Vanderbeck, F., Savelsbergh, M.: A generic view of Dantzig\u2013Wolfe decomposition in mixed integer programming. Oper. Res. Lett. 34(3), 296\u2013306 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"206_CR41","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1090\/qam\/135625","volume":"19","author":"P Wolfe","year":"1961","unstructured":"Wolfe, P.: A duality theorem for non-linear programming. Quart. Appl. Math. 19(3), 239\u2013244 (1961)","journal-title":"Quart. Appl. Math."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-021-00206-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-021-00206-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-021-00206-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T18:11:09Z","timestamp":1646676669000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-021-00206-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,3]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["206"],"URL":"https:\/\/doi.org\/10.1007\/s12532-021-00206-w","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,3]]},"assertion":[{"value":"27 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The work has been partially funded by Regione Lombardia - Fondazione Cariplo, grant no. 2015\u20130717, project \u201cREDNEAT\u201d, and partially undertook when A. Ceselli was visiting LIPN - Universit\u00e9 Sorbonne Paris Nord.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"The authors declare that they have no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"All data analyzed during this study are publicly available. URLs are included in this published article.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and materials"}},{"value":"The full code was made available for review. We remark that a set of packages were used in this study, that were either open source or available for academic use. Specific references are included in this published article.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}