{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T19:35:15Z","timestamp":1773344115262,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,10,9]],"date-time":"2021-10-09T00:00:00Z","timestamp":1633737600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,9]],"date-time":"2021-10-09T00:00:00Z","timestamp":1633737600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide several applications of the linearization problem of a binary quadratic problem. We propose a new lower bounding strategy, called the linearization-based scheme, that is based on a simple certificate for a quadratic function to be non-negative on the feasible set. Each linearization-based bound requires a set of linearizable matrices as an input. We prove that the Generalized Gilmore\u2013Lawler bounding scheme for binary quadratic problems provides linearization-based bounds. Moreover, we show that the bound obtained from the first level reformulation linearization technique is also a type of linearization-based bound, which enables us to provide a comparison among mentioned bounds. However, the strongest linearization-based bound is the one that uses the full characterization of the set of linearizable matrices. We also present a polynomial-time algorithm for the linearization problem of the quadratic shortest path problem on directed acyclic graphs. Our algorithm gives a complete characterization of the set of linearizable matrices for the quadratic shortest path problem.<\/jats:p>","DOI":"10.1007\/s10479-021-04310-x","type":"journal-article","created":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T15:58:27Z","timestamp":1633881507000},"page":"229-249","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["The linearization problem of a binary quadratic problem and its applications"],"prefix":"10.1007","volume":"307","author":[{"given":"Hao","family":"Hu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3298-7255","authenticated-orcid":false,"given":"Renata","family":"Sotirov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,9]]},"reference":[{"key":"4310_CR1","doi-asserted-by":"crossref","unstructured":"Adams, W. P., & Johnson, T. A. (1994). Improved linear programming-based lower bounds for the quadratic assignment problem. In Proceedings of the DIMACS workshop on quadratic assignment problems, DIMACS series in discrete mathematics and theoretical computes sciences (pp. 43\u201375). AMS.","DOI":"10.1090\/dimacs\/016\/02"},{"issue":"10","key":"4310_CR2","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"WP Adams","year":"1986","unstructured":"Adams, W. P., & Sherali, H. D. (1986). A tight linearization and an algorithm for zero-one quadratic programming problems. Management Science, 32(10), 1274\u20131290.","journal-title":"Management Science"},{"issue":"2","key":"4310_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1287\/opre.38.2.217","volume":"38","author":"WP Adams","year":"1990","unstructured":"Adams, W. P., & Sherali, H. D. (1990). Linearization strategies for a class of zero-one mixed integer programming problems. Operations Research, 38(2), 217\u2013226.","journal-title":"Operations Research"},{"key":"4310_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.disopt.2014.07.001","volume":"14","author":"WP Adams","year":"2014","unstructured":"Adams, W. P., & Waddell, L. (2014). Linear programming insights into solvable cases of the quadratic assignment problem. Discrete Optimization, 14, 46\u201360.","journal-title":"Discrete Optimization"},{"issue":"4","key":"4310_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0167-6377(85)90025-2","volume":"4","author":"AA Assad","year":"1985","unstructured":"Assad, A. A., & Xu, W. (1985). On lower bounds for a class of quadratic 0,1 programs. Operations Research Letters, 4(4), 175\u2013180.","journal-title":"Operations Research Letters"},{"issue":"6","key":"4310_CR6","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. (2009). Improving the performance of standard solvers for quadratic 0\u20131 programs by a tight convex reformulation: The QCR method. Discrete Applied Mathematics, 157(6), 1185\u20131197.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"4310_CR7","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1287\/ijoc.2017.0789","volume":"30","author":"C Buchheim","year":"2018","unstructured":"Buchheim, C., & Traversi, E. (2018). Quadratic 0\u20131 optimization using separable under estimators. INFORMS Journal on Computing, 30(3), 421\u2013624.","journal-title":"INFORMS Journal on Computing"},{"key":"4310_CR8","doi-asserted-by":"crossref","unstructured":"Burkard, R., & Dell Amico, M., & Martello, S. . (2012). Assignment problems: Revised reprint (Vol. 106). SIAM.","DOI":"10.1137\/1.9781611972238"},{"issue":"1","key":"4310_CR9","doi-asserted-by":"publisher","first-page":"S22","DOI":"10.1287\/opre.40.1.S22","volume":"40","author":"P Carraresi","year":"1992","unstructured":"Carraresi, P., & Malucelli, F. (1992). A new lower bound for the quadratic assignment problem. Operations Research, 40(1), S22\u2013S27.","journal-title":"Operations Research"},{"issue":"3","key":"4310_CR10","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.ejor.2017.12.024","volume":"267","author":"E \u00c7ela","year":"2018","unstructured":"\u00c7ela, E., Deineko, V., & Woeginger, G. J. (2018). New special cases of the quadratic assignment problem with diagonally structured coefficient matrices. European Journal of Operational Research, 267(3), 818\u2013834.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"4310_CR11","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1007\/s10878-014-9821-2","volume":"31","author":"E \u00c7ela","year":"2016","unstructured":"\u00c7ela, E., Deineko, V. G., & Woeginger, G. J. (2016). Linearizable special cases of the QAP. Journal of Combinatorial optimization, 31(3), 1269\u20131279.","journal-title":"Journal of Combinatorial optimization"},{"issue":"2","key":"4310_CR12","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/s10878-017-0184-3","volume":"35","author":"A \u0106usti\u0107","year":"2018","unstructured":"\u0106usti\u0107, A., & Punnen, A. P. (2018). A characterization of linearizable instances of the quadratic minimum spanning tree problem. Journal of Combinatorial Optimization, 35(2), 436\u2013453.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1\u20132","key":"4310_CR13","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10107-017-1111-1","volume":"166","author":"A \u0106usti\u0107","year":"2017","unstructured":"\u0106usti\u0107, A., Sokol, V., Punnen, A. P., & Bhattacharya, B. (2017). The bilinear assignment problem: Complexity and polynomially solvable special cases. Mathematical Programming, 166(1\u20132), 185\u2013205.","journal-title":"Mathematical Programming"},{"key":"4310_CR14","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1007\/s10878-020-00547-7","volume":"39","author":"F de Meijer","year":"2020","unstructured":"de Meijer, F., & Sotirov, R. (2020). The quadratic cycle cover problem: Special cases and efficient bounds. Journal of Combinatorial Optimization, 39, 1096\u20131128.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"4310_CR15","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.disopt.2011.03.002","volume":"8","author":"G Erdo\u011fan","year":"2011","unstructured":"Erdo\u011fan, G., & Tansel, B. \u00c7. (2011). Two classes of quadratic assignment problems that are solvable as linear assignment problems. Discrete Optimization, 8(3), 446\u2013451.","journal-title":"Discrete Optimization"},{"issue":"1","key":"4310_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, A. M., & Yadegar, J. (1983). On the quadratic assignment problem. Discrete Applied Mathematics, 5(1), 89\u201398.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"4310_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"PC Gilmore","year":"1962","unstructured":"Gilmore, P. C. (1962). Optimal and suboptimal algorithms for the quadratic assignment problem. Journal of the Society for Industrial and Applied Mathematics, 10(2), 305\u2013313.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"issue":"6","key":"4310_CR18","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1287\/opre.46.6.912","volume":"46","author":"P Hahn","year":"1998","unstructured":"Hahn, P., & Grant, T. (1998). Lower bounds for the quadratic assignment problem based upon a dual formulation. Operations Research, 46(6), 912\u2013922.","journal-title":"Operations Research"},{"issue":"3","key":"4310_CR19","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/S0377-2217(97)00063-5","volume":"108","author":"P Hahn","year":"1998","unstructured":"Hahn, P., Grant, T., & Hall, N. (1998). A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. European Journal of Operational Research, 108(3), 629\u2013640.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"4310_CR20","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s10878-017-0219-9","volume":"35","author":"H Hu","year":"2018","unstructured":"Hu, H., & Sotirov, R. (2018). Special cases of the quadratic shortest path problem. Journal of Combinatorial Optimization, 35(3), 754\u2013777.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"4310_CR21","first-page":"219","volume":"32","author":"H Hu","year":"2020","unstructured":"Hu, H., & Sotirov, R. (2020). On solving the quadratic shortest path problem. INFORMS Journal on Computing, 32(2), 219\u2013233.","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"4310_CR22","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1287\/moor.1110.0509","volume":"36","author":"SN Kabadi","year":"2011","unstructured":"Kabadi, S. N., & Punnen, A. P. (2011). An O($$n^4$$) algorithm for the QAP linearization problem. Mathematics of Operations Research, 36(4), 754\u2013761.","journal-title":"Mathematics of Operations Research"},{"key":"4310_CR23","doi-asserted-by":"crossref","unstructured":"Koopmans, T. C., & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society, 53\u201376.","DOI":"10.2307\/1907742"},{"issue":"3","key":"4310_CR24","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J. B. (2001). Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3), 796\u2013817.","journal-title":"SIAM Journal on Optimization"},{"key":"4310_CR25","doi-asserted-by":"crossref","unstructured":"Laurent, M. (2009). Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry (pp. 157\u2013270). Springer.","DOI":"10.1007\/978-0-387-09686-5_7"},{"issue":"4","key":"4310_CR26","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler, E. L. (1963). The quadratic assignment problem. Management Science, 9(4), 586\u2013599.","journal-title":"Management Science"},{"key":"4310_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.disopt.2019.03.004","volume":"33","author":"S Lendl","year":"2019","unstructured":"Lendl, S., \u0106usti\u0107, A., & Punnen, A. P. (2019). Combinatorial optimization problems with interaction costs: Complexity and solvable cases. Discrete Optimization, 33, 101\u2013117.","journal-title":"Discrete Optimization"},{"key":"4310_CR28","doi-asserted-by":"crossref","unstructured":"Murakami, K., & Kim, H. S. (1997). Comparative study on restoration schemes of survivable atm networks. In INFOCOM\u201997. Sixteenth annual joint conference of the IEEE computer and communications societies. Driving the information revolution. Proceedings IEEE (Vol.\u00a01, pp. 345\u2013352). IEEE.","DOI":"10.1109\/INFCOM.1997.635156"},{"issue":"1","key":"4310_CR29","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jco.2006.07.002","volume":"23","author":"J Nie","year":"2007","unstructured":"Nie, J., & Schweighofer, M. (2007). On the complexity of Putinar-Positivstellensatz. Journal of Complexity, 23(1), 135\u2013150.","journal-title":"Journal of Complexity"},{"issue":"3","key":"4310_CR30","first-page":"205","volume":"7","author":"AP Punnen","year":"2001","unstructured":"Punnen, A. P. (2001). Combinatorial optimization with multiplicative objective function. International Journal of Operations and Quantitative Management, 7(3), 205\u2013210.","journal-title":"International Journal of Operations and Quantitative Management"},{"issue":"3","key":"4310_CR31","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","volume":"10","author":"AP Punnen","year":"2013","unstructured":"Punnen, A. P., & Kabadi, S. N. (2013). A linear time algorithm for the Koopmans\u2013Beckmann QAP linearization and related problems. Discrete Optimization, 10(3), 200\u2013209.","journal-title":"Discrete Optimization"},{"key":"4310_CR32","doi-asserted-by":"publisher","first-page":"104769","DOI":"10.1016\/j.cor.2019.104769","volume":"112","author":"AP Punnen","year":"2019","unstructured":"Punnen, A. P., Pandey, P., & Friesen, M. (2019). Representations of quadratic combinatorial optimization problems: A case study using the quadratic set covering problem. Computers and Operations Research, 112, 104769.","journal-title":"Computers and Operations Research"},{"key":"4310_CR33","unstructured":"Punnen, A. P., Woods, B. D., & Kabadi, S. N. (2017). A characterization of linearizable instances of the quadratic traveling salesman problem. arXiv:1708.07217"},{"issue":"2","key":"4310_CR34","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. European Journal of Operational Research, 268(2), 473\u2013485.","journal-title":"European Journal of Operational Research"},{"key":"4310_CR35","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.cor.2015.06.005","volume":"64","author":"B Rostami","year":"2015","unstructured":"Rostami, B., & Malucelli, F. (2015). Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation. Computers and Operations Research, 64, 178\u2013188.","journal-title":"Computers and Operations Research"},{"issue":"1","key":"4310_CR36","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1287\/trsc.35.1.37.10141","volume":"35","author":"S Sen","year":"2001","unstructured":"Sen, S., Pillai, R., Joshi, S., & Rathi, A. K. (2001). A mean-variance model for route guidance in advanced traveler information systems. Transportation Science, 35(1), 37\u201349.","journal-title":"Transportation Science"},{"issue":"4","key":"4310_CR37","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1287\/trsc.28.4.309","volume":"28","author":"RA Sivakumar","year":"1994","unstructured":"Sivakumar, R. A., & Batta, R. (1994). The variance-constrained shortest path problem. Transportation Science, 28(4), 309\u2013316.","journal-title":"Transportation Science"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04310-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04310-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04310-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T16:32:02Z","timestamp":1636993922000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04310-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,9]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["4310"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04310-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,9]]},"assertion":[{"value":"12 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}