{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:09:08Z","timestamp":1761898148533,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T00:00:00Z","timestamp":1679529600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T00:00:00Z","timestamp":1679529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computational utility of inductive linearizations for binary quadratic programs when combined with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances.<\/jats:p>","DOI":"10.1007\/s10288-023-00537-5","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T11:04:46Z","timestamp":1679569486000},"page":"47-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Inductive linearization for binary quadratic programs with linear constraints: a computational study"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5335-0678","authenticated-orcid":false,"given":"Sven","family":"Mallach","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,23]]},"reference":[{"key":"537_CR1","series-title":"DIMACS Series on Discrete Mathematics and Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","volume-title":"Quadratic assignment and related problems","author":"WP Adams","year":"1994","unstructured":"Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems, vol 16. DIMACS Series on Discrete Mathematics and Computer Science. AMS, Providence, pp 43\u201375"},{"issue":"10","key":"537_CR2","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"WP Adams","year":"1986","unstructured":"Adams WP, Sherali HD (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Manag Sci 32(10):1274\u20131290. https:\/\/doi.org\/10.1287\/mnsc.32.10.1274","journal-title":"Manag Sci"},{"key":"537_CR3","doi-asserted-by":"publisher","unstructured":"Adams WP, Sherali HD (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. In: Nonconvex optimization and its applications, vol 31. Springer. https:\/\/doi.org\/10.1007\/978-1-4757-4388-3","DOI":"10.1007\/978-1-4757-4388-3"},{"issue":"2","key":"537_CR4","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0377-2217(94)00229-0","volume":"92","author":"A Billionnet","year":"1996","unstructured":"Billionnet A, Calmels F (1996) Linear programming for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 92(2):310\u2013325. https:\/\/doi.org\/10.1016\/0377-2217(94)00229-0","journal-title":"Eur J Oper Res"},{"issue":"3","key":"537_CR5","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(00)00257-2","volume":"109","author":"A Billionnet","year":"2001","unstructured":"Billionnet A, Elloumi S (2001) Best reduction of the quadratic semi-assignment problem. Discrete Appl Math 109(3):197\u2013213. https:\/\/doi.org\/10.1016\/S0166-218X(00)00257-2","journal-title":"Discrete Appl Math"},{"issue":"3","key":"537_CR6","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 (2004) An exact method based on Lagrangian decomposition for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 157(3):565\u2013575. https:\/\/doi.org\/10.1016\/S0377-2217(03)00244-3","journal-title":"Eur J Oper Res"},{"issue":"4","key":"537_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard RE, Karisch SE, Rendl F (1997) QAPLIB\u2014a quadratic assignment problem library. J Glob Optim 10(4):391\u2013403. https:\/\/doi.org\/10.1023\/A:1008293323270","journal-title":"J Glob Optim"},{"issue":"4","key":"537_CR8","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1287\/ijoc.1040.0128","volume":"18","author":"JF Cordeau","year":"2006","unstructured":"Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J Comput 18(4):433\u2013443. https:\/\/doi.org\/10.1287\/ijoc.1040.0128","journal-title":"INFORMS J Comput"},{"key":"537_CR9","unstructured":"Davidovi\u0107 T, Liberti L, Maculan N, Mladenovi\u0107 N (2007) Towards the optimal solution of the multiprocessor scheduling problem with communication delays. In: Baptiste P, Kendall G, Munier-Kordon A, Sourd F (eds) Proceedings of the 3rd multidisciplinary international conference on scheduling: theory and applications, \u00c9cole Polytechnique, Paris, pp 128\u2013135"},{"issue":"1","key":"537_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0166-218X(83)90018-5","volume":"5","author":"AM Frieze","year":"1983","unstructured":"Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl Math 5(1):89\u201398. https:\/\/doi.org\/10.1016\/0166-218X(83)90018-5","journal-title":"Discrete Appl Math"},{"key":"537_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, Lodi A, Misener R, Mittelmann H, Sahinidis N, Vigerske S, Wiegele A (2019) QPLIB: a library of quadratic programming instances. Math Program Comput 11:237\u2013265. https:\/\/doi.org\/10.1007\/s12532-018-0147-4","journal-title":"Math Program Comput"},{"issue":"1","key":"537_CR12","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/opre.22.1.180","volume":"22","author":"F Glover","year":"1974","unstructured":"Glover F, Woolsey E (1974) Converting the 0\u20131 polynomial programming problem to a 0\u20131 linear program. Oper Res 22(1):180\u2013182. https:\/\/doi.org\/10.1287\/opre.22.1.180","journal-title":"Oper Res"},{"issue":"2","key":"537_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"PL Hammer","year":"1984","unstructured":"Hammer PL, Hansen P, Simeone B (1984) Roof duality, complementation and persistency in quadratic 0\u20131 optimization. Math Program 28(2):121\u2013155. https:\/\/doi.org\/10.1007\/BF02612354","journal-title":"Math Program"},{"issue":"2","key":"537_CR14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1009898604624","volume":"4","author":"C Helmberg","year":"2000","unstructured":"Helmberg C, Rendl F, Weismantel R (2000) A semidefinite programming approach to the quadratic knapsack problem. J Comb Optim 4(2):197\u2013215. https:\/\/doi.org\/10.1023\/A:1009898604624","journal-title":"J Comb Optim"},{"key":"537_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.disopt.2015.10.002","volume":"18","author":"L Hupp","year":"2015","unstructured":"Hupp L, Klein L, Liers F (2015) An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations. Discrete Optim 18:193\u2013216. https:\/\/doi.org\/10.1016\/j.disopt.2015.10.002","journal-title":"Discrete Optim"},{"issue":"1","key":"537_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"TC Koopmans","year":"1957","unstructured":"Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53\u201376","journal-title":"Econometrica"},{"issue":"3","key":"537_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10288-006-0015-3","volume":"5","author":"L Liberti","year":"2007","unstructured":"Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231\u2013245. https:\/\/doi.org\/10.1007\/s10288-006-0015-3","journal-title":"4OR"},{"key":"537_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-017-0199-9","author":"S Mallach","year":"2017","unstructured":"Mallach S (2017) Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-017-0199-9","journal-title":"J Comb Optim"},{"key":"537_CR19","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10288-017-0364-0","volume":"16","author":"S Mallach","year":"2018","unstructured":"Mallach S (2018) Compact linearization for binary quadratic problems subject to assignment constraints. 4OR 16:295\u2013309. https:\/\/doi.org\/10.1007\/s10288-017-0364-0","journal-title":"4OR"},{"key":"537_CR20","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/978-3-030-35802-0_40","volume-title":"Graph drawing and network visualization","author":"S Mallach","year":"2019","unstructured":"Mallach S (2019) A natural quadratic approach to the generalized graph layering problem. In: Archambault D, T\u00f3th CD (eds) Graph drawing and network visualization. Springer, Cham, pp 532\u2013544. https:\/\/doi.org\/10.1007\/978-3-030-35802-0_40"},{"issue":"4","key":"537_CR21","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s10288-020-00460-z","volume":"19","author":"S Mallach","year":"2021","unstructured":"Mallach S (2021) Inductive linearization for binary quadratic programs with linear constraints. 4OR 19(4):549\u2013570. https:\/\/doi.org\/10.1007\/s10288-020-00460-z","journal-title":"4OR"},{"issue":"1","key":"537_CR22","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ejor.2010.02.006","volume":"206","author":"AA Pessoa","year":"2010","unstructured":"Pessoa AA, Hahn PM, Guignard M, Zhu YR (2010) Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique. Eur J Oper Res 206(1):54\u201363. https:\/\/doi.org\/10.1016\/j.ejor.2010.02.006","journal-title":"Eur J Oper Res"},{"issue":"2","key":"537_CR23","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.ejor.2018.01.054","volume":"268","author":"B Rostami","year":"2018","unstructured":"Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2018) The quadratic shortest path problem: complexity, approximability, and solution methods. Eur J Oper Res 268(2):473\u2013485. https:\/\/doi.org\/10.1016\/j.ejor.2018.01.054","journal-title":"Eur J Oper Res"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-023-00537-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-023-00537-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-023-00537-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T12:06:05Z","timestamp":1712059565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-023-00537-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,23]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["537"],"URL":"https:\/\/doi.org\/10.1007\/s10288-023-00537-5","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2023,3,23]]},"assertion":[{"value":"18 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}