{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T10:36:38Z","timestamp":1770460598406,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"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":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called \u201cinductive linearization\u201d, extends concepts for BQPs with particular equation constraints, that have been referred to as \u201ccompact linearization\u201d before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers.<\/jats:p>","DOI":"10.1007\/s10288-020-00460-z","type":"journal-article","created":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T04:02:25Z","timestamp":1603080145000},"page":"549-570","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Inductive linearization for binary quadratic programs with linear constraints"],"prefix":"10.1007","volume":"19","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":[[2020,10,19]]},"reference":[{"key":"460_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","volume-title":"Quadratic assignment and related problems, DIMACS series on discrete mathematics and computer science","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, DIMACS series on discrete mathematics and computer science, vol 16. AMS, Providence, pp 43\u201375"},{"issue":"10","key":"460_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":"460_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A Reformulation-Linearization technique for solving discrete and continuous nonconvex problems, nonconvex optimization and its applications","author":"WP Adams","year":"1999","unstructured":"Adams WP, Sherali HD (1999) A Reformulation-Linearization technique for solving discrete and continuous nonconvex problems, nonconvex optimization and its applications, vol 31. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-1-4757-4388-3"},{"key":"460_CR4","first-page":"5136","volume":"258","author":"E Balas","year":"1964","unstructured":"Balas E (1964) Extension de l\u2019algorithme additif \u00e0 la programmation en nombres entiers et \u00e0 la programmation non lin\u00e9aire. Comptes rendus de l\u2019Acad\u00e9mie des Sciences Paris 258:5136\u20135139","journal-title":"Comptes rendus de l\u2019Acad\u00e9mie des Sciences Paris"},{"issue":"1","key":"460_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F Barahona","year":"1989","unstructured":"Barahona F, J\u00fcnger M, Reinelt G (1989) Experiments in quadratic 0\u20131 programming. Math Programm 44(1):127\u2013137. https:\/\/doi.org\/10.1007\/BF01587084","journal-title":"Math Programm"},{"issue":"2","key":"460_CR6","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":"460_CR7","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":"6","key":"460_CR8","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/j.orl.2004.03.005","volume":"32","author":"W Chaovalitwongse","year":"2004","unstructured":"Chaovalitwongse W, Pardalos PM, Prokopyev OA (2004) A new linearization technique for multi-quadratic 0\u20131 programming problems. Oper Res Lett 32(6):517\u2013522. https:\/\/doi.org\/10.1016\/j.orl.2004.03.005","journal-title":"Oper Res Lett"},{"issue":"4","key":"460_CR9","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393\u2013410. https:\/\/doi.org\/10.1287\/opre.2.4.393","journal-title":"J Oper Res Soc Am"},{"key":"460_CR10","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) Proc. 3rd Multidisciplinary Int. Conf. on Scheduling: Theory and Application, \u00c9cole Polytechnique, Paris, France, pp 128\u2013135"},{"issue":"1","key":"460_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"C De Simone","year":"1990","unstructured":"De Simone C (1990) The cut polytope and the boolean quadric polytope. Discrete Math 79(1):71\u201375. https:\/\/doi.org\/10.1016\/0012-365X(90)90056-N","journal-title":"Discrete Math"},{"key":"460_CR12","unstructured":"Fischer A (2013) A polyhedral study of quadratic traveling salesman problems. PhD thesis, Chemnitz University of Technology"},{"issue":"1\u20132","key":"460_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s10107-012-0568-1","volume":"142","author":"A Fischer","year":"2013","unstructured":"Fischer A, Helmberg C (2013) The symmetric quadratic traveling salesman problem. Math Program 142(1\u20132):205\u2013254. https:\/\/doi.org\/10.1007\/s10107-012-0568-1","journal-title":"Math Program"},{"key":"460_CR14","first-page":"5","volume":"1","author":"R Fortet","year":"1959","unstructured":"Fortet R (1959) L\u2019alg\u00e8bre de boole et ses applications en recherche op\u00e9rationnelle. Cahiers du Centre d\u2019Etudes de Recherche Op\u00e9rationnelle 1:5\u201336","journal-title":"Cahiers du Centre d\u2019Etudes de Recherche Op\u00e9rationnelle"},{"key":"460_CR15","first-page":"17","volume":"4","author":"R Fortet","year":"1960","unstructured":"Fortet R (1960) Applications de l\u2019alg\u00e8bre de boole en recherche op\u00e9rationnelle. Revue de la Soci\u00e9t\u00e9 Fran\u00e7aise de Recherche Op\u00e9rationnelle 4:17\u201326","journal-title":"Revue de la Soci\u00e9t\u00e9 Fran\u00e7aise de Recherche Op\u00e9rationnelle"},{"issue":"1","key":"460_CR16","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":"460_CR17","unstructured":"Furini F, Traversi E (2013) Extended linear formulation for binary quadratic problems. Optimization Online"},{"issue":"1","key":"460_CR18","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1287\/opre.21.1.156","volume":"21","author":"F Glover","year":"1973","unstructured":"Glover F, Woolsey E (1973) Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper Res 21(1):156\u2013161","journal-title":"Oper Res"},{"issue":"1","key":"460_CR19","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":"6","key":"460_CR20","doi-asserted-by":"publisher","first-page":"1255","DOI":"10.1016\/j.dam.2008.01.028","volume":"157","author":"S Gueye","year":"2009","unstructured":"Gueye S, Michelon P (2009) A linearization framework for unconstrained quadratic (0\u20131) problems. Discrete Appl Math 157(6):1255\u20131266. https:\/\/doi.org\/10.1016\/j.dam.2008.01.028","journal-title":"Discrete Appl Math"},{"issue":"3","key":"460_CR21","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"PL Hammer","year":"1965","unstructured":"Hammer PL (1965) Some network flow problems solved with pseudo-boolean programming. Oper Res 13(3):388\u2013399","journal-title":"Oper Res"},{"key":"460_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean Methods in Operations Research and Related Areas, \u00d6konometrie und Unternehmensforschung\/Econometrics and Operations Research","author":"PL Hammer","year":"1968","unstructured":"Hammer PL, Rudeanu S (1968) Boolean Methods in Operations Research and Related Areas, \u00d6konometrie und Unternehmensforschung\/Econometrics and Operations Research, vol 7. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-642-85823-9"},{"issue":"6","key":"460_CR23","doi-asserted-by":"publisher","first-page":"1267","DOI":"10.1016\/j.dam.2007.12.008","volume":"157","author":"P Hansen","year":"2009","unstructured":"Hansen P, Meyer C (2009) Improved compact linearizations for the unconstrained quadratic 0\u20131 minimization problem. Discrete Appl Math 157(6):1267\u20131290. https:\/\/doi.org\/10.1016\/j.dam.2007.12.008","journal-title":"Discrete Appl Math"},{"issue":"2","key":"460_CR24","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":"460_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"460_CR26","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":"460_CR27","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":"460_CR28","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":"460_CR29","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"},{"issue":"1","key":"460_CR30","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: part I\u2014convex underestimating problems. Math Program 10(1):147\u2013175. https:\/\/doi.org\/10.1007\/BF01580665","journal-title":"Math Program"},{"issue":"1\u2013supplement\u20131","key":"460_CR31","doi-asserted-by":"publisher","first-page":"S109","DOI":"10.1287\/opre.40.1.S109","volume":"40","author":"M Oral","year":"1992","unstructured":"Oral M, Kettani O (1992a) A linearization procedure for quadratic and cubic mixed-integer problems. Oper Res 40(1\u2013supplement\u20131):S109\u2013S116. https:\/\/doi.org\/10.1287\/opre.40.1.S109","journal-title":"Oper Res"},{"issue":"2","key":"460_CR32","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0377-2217(92)90210-Z","volume":"58","author":"M Oral","year":"1992","unstructured":"Oral M, Kettani O (1992b) Reformulating nonlinear combinatorial optimization problems for higher computational efficiency. Eur J Oper Res 58(2):236\u2013249. https:\/\/doi.org\/10.1016\/0377-2217(92)90210-Z","journal-title":"Eur J Oper Res"},{"issue":"1","key":"460_CR33","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg M (1989) The boolean quadric polytope: some characteristics, facets and relatives. Math Program 45(1):139\u2013172. https:\/\/doi.org\/10.1007\/BF01589101","journal-title":"Math Program"},{"issue":"1","key":"460_CR34","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s11590-006-0019-0","volume":"1","author":"HD Sherali","year":"2007","unstructured":"Sherali HD, Smith JC (2007) An improved linearization strategy for zero-one quadratic programming problems. Optim Lett 1(1):33\u201347. https:\/\/doi.org\/10.1007\/s11590-006-0019-0","journal-title":"Optim Lett"},{"key":"460_CR35","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1287\/opre.15.6.1171","volume":"15","author":"LJ Watters","year":"1967","unstructured":"Watters LJ (1967) Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper Res 15:1171\u20131174","journal-title":"Oper Res"},{"key":"460_CR36","first-page":"23","volume":"5","author":"WI Zangwill","year":"1965","unstructured":"Zangwill WI (1965) Media selection by decision programming. J Adv Res 5:23\u201337","journal-title":"J Adv Res"}],"updated-by":[{"DOI":"10.1007\/s10288-021-00494-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T00:00:00Z","timestamp":1633564800000}}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00460-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-020-00460-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00460-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T17:03:51Z","timestamp":1691082231000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-020-00460-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,19]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["460"],"URL":"https:\/\/doi.org\/10.1007\/s10288-020-00460-z","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10288-021-00494-x","asserted-by":"object"}]},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,19]]},"assertion":[{"value":"21 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10288-021-00494-x","URL":"https:\/\/doi.org\/10.1007\/s10288-021-00494-x","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The author declares that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}