{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:43:34Z","timestamp":1769298214082,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,5,23]],"date-time":"2015-05-23T00:00:00Z","timestamp":1432339200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["307026\/2013-2"],"award-info":[{"award-number":["307026\/2013-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["141118\/2009-1"],"award-info":[{"award-number":["141118\/2009-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["304793\/2011-6"],"award-info":[{"award-number":["304793\/2011-6"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s10589-015-9763-3","type":"journal-article","created":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T23:55:17Z","timestamp":1432252517000},"page":"97-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Lagrangian heuristics for the Quadratic Knapsack Problem"],"prefix":"10.1007","volume":"63","author":[{"given":"Jesus Ossian","family":"Cunha","sequence":"first","affiliation":[]},{"given":"Luidi","family":"Simonetti","sequence":"additional","affiliation":[]},{"given":"Abilio","family":"Lucena","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,23]]},"reference":[{"key":"9763_CR1","first-page":"243","volume-title":"Modern Heuristic Techniques for Combinatorial Problems","author":"J Beasley","year":"1993","unstructured":"Beasley, J.: Lagrangian relaxation. In: Reeves, C. (ed.) Modern Heuristic Techniques for Combinatorial Problems, pp. 243\u2013303. Wiley, New York (1993)"},{"key":"9763_CR2","doi-asserted-by":"crossref","unstructured":"Belloni, A., Lucena, A.: Lagrangian heuristic for the linear ordering problem. In: Resende, M.G.C., de Sousa, J.P. (eds.) Metaheuristics: Computer Decision-Making. Kluwer Academic Publishers (2004)","DOI":"10.1007\/978-1-4757-4137-7_3"},{"key":"9763_CR3","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0377-2217(94)00229-0","volume":"92","author":"A Billionnet","year":"1996","unstructured":"Billionnet, A., Calmels, F.: Linear programming for the 0\u20131 quadratic knapsack problem. Eur. J. Oper. Res. 92, 310\u2013325 (1996)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"9763_CR4","doi-asserted-by":"crossref","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 lagrangian decomposition for the 0\u20131 quadratic knapsack problem. Eur. J. Oper. Res. 157(3), 565\u2013575 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"9763_CR5","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1016\/S0377-2217(97)00414-1","volume":"112","author":"A Billionnet","year":"1999","unstructured":"Billionnet, A., Faye, A., Soutif, E.: A new upper bound for the 0\u20131 quadratic knapsack problem. Eur. J. Oper. Res. 112(3), 664\u2013672 (1999)","journal-title":"Eur. J. Oper. Res."},{"key":"9763_CR6","doi-asserted-by":"crossref","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, 125\u2013137 (1999)","journal-title":"INFORMS J. Comput."},{"key":"9763_CR7","doi-asserted-by":"crossref","first-page":"1963","DOI":"10.1016\/j.cor.2006.10.009","volume":"35","author":"V Cavalcante","year":"2008","unstructured":"Cavalcante, V., Souza, C.C., Lucena, A.: A relax-and-cut algorithm to the set partitioning problem. Comput. Oper. Res. 35, 1963\u20131981 (2008)","journal-title":"Comput. Oper. Res."},{"key":"9763_CR8","doi-asserted-by":"crossref","unstructured":"Chaillou, P., Hansen, P., Mahieu, Y.: Best network flow bound for the quadratic knapsack problem. Combinatorial Optimization, Lecture Notes in Mathematics, vol. 1403, pp. 225\u2013235 (1989)","DOI":"10.1007\/BFb0083467"},{"key":"9763_CR9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.20166","volume":"50","author":"AS Cunha","year":"2007","unstructured":"Cunha, A.S., Lucena, A.: Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks 50, 55\u201366 (2007)","journal-title":"Networks"},{"key":"9763_CR10","doi-asserted-by":"crossref","first-page":"1198","DOI":"10.1016\/j.dam.2008.02.014","volume":"157","author":"AS Cunha","year":"2009","unstructured":"Cunha, A.S., Lucena, A., Maculan, N., Resende, M.G.C.: A relax-and-cut algorithm for the prize-collecting steiner problem in graphs. Discret. Appl. Math. 157, 1198\u20131217 (2009)","journal-title":"Discret. Appl. Math."},{"key":"9763_CR11","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.endm.2010.05.079","volume":"36","author":"AS Cunha da","year":"2010","unstructured":"da Cunha, A.S., Bahiense, L., Lucena, A., de Souza, C.C.: A new lagrangian based branch and bound algorithm for the 0\u20131 knapsack problem. Electron. Notes Discret. Math. 36, 623\u2013630 (2010)","journal-title":"Electron. Notes Discret. Math."},{"key":"9763_CR12","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"G Dantzig","year":"1957","unstructured":"Dantzig, G.: Discrete variables extremum problems. Oper. Res. 5, 266\u2013277 (1957)","journal-title":"Oper. Res."},{"key":"9763_CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02085641","volume":"50","author":"L Escudero","year":"1994","unstructured":"Escudero, L., Guignard, M., Malik, K.: A lagrangean relax and cut approach for the sequential ordering with precedence constraints. Ann. Oper. Res. 50, 219\u2013237 (1994)","journal-title":"Ann. Oper. Res."},{"key":"9763_CR14","first-page":"247","volume":"74","author":"C Ferreira","year":"1996","unstructured":"Ferreira, C., Martin, A., Souza, C., Weismantel, R., Wolsey, L.: Formulations and valid inequalities for node capacitated graph partitioning. Math. Program. 74, 247\u2013266 (1996)","journal-title":"Math. Program."},{"key":"9763_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1287\/ijoc.2013.0555","volume":"26","author":"F Fomeni","year":"2013","unstructured":"Fomeni, F., Letchford, A.: A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26, 173\u2013182 (2013)","journal-title":"INFORMS J. Comput."},{"key":"9763_CR16","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0120892","volume":"12","author":"G Gallo","year":"1980","unstructured":"Gallo, G., Hammer, P.L., Simeone, B.: Quadratic knapsack problems. Math. Program. 12, 132\u2013149 (1980)","journal-title":"Math. Program."},{"key":"9763_CR17","doi-asserted-by":"crossref","unstructured":"Gendreau, M., Potvin, J.: Handbook of Metaheuristics, International Series in Operations Research & Management, vol. 146. Science (2010)","DOI":"10.1007\/978-1-4419-1665-5"},{"issue":"1","key":"9763_CR18","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The travelling salesman problem and minimum spanning trees: part II. Math. Program. 1(1), 6\u201325 (1971)","journal-title":"Math. Program."},{"issue":"1","key":"9763_CR19","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M Held","year":"1974","unstructured":"Held, M., Wolfe, P., Crowder, H.P.: Validation of subgradient optimization. Math. Program. 6(1), 62\u201388 (1974)","journal-title":"Math. Program."},{"key":"9763_CR20","doi-asserted-by":"crossref","unstructured":"Helmberg, C., Rendl, F., Weismantel, R.: Quadratic knapsack relaxations using cutting planes and semidefinite programming. In: Proceedings of the Fifth IPCO Conference, Lecture Notes in Computer Science, vol. 1084, pp. 175\u2013189 (1996)","DOI":"10.1007\/3-540-61310-2_14"},{"key":"9763_CR21","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1023\/A:1009898604624","volume":"4","author":"C Helmberg","year":"1996","unstructured":"Helmberg, C., Rendl, F., Weismantel, R.: A semidefinite programming approach to the quadratic knapsack problem. J. Combin. Optim. 4, 197\u2013215 (1996)","journal-title":"J. Combin. Optim."},{"key":"9763_CR22","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"E Johnson","year":"1993","unstructured":"Johnson, E., Mehrotra, A., Nemhauser, G.: Min-cut clustering. Math. Program. 62, 133\u2013151 (1993)","journal-title":"Math. Program."},{"key":"9763_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"9763_CR24","unstructured":"Lucena, A.: Steiner problem in graphs: Lagrangean relaxation and cutting-planes. COAL Bulletin, Mathematical Programming Society, vol. 21 (1992)"},{"key":"9763_CR25","unstructured":"Lucena, A.: Tight bounds for the steiner problem in graphs. In: Proceedings of NET-FLOW93, pp. 147\u2013154 (1993)"},{"issue":"1","key":"9763_CR26","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10479-005-3977-1","volume":"140","author":"A Lucena","year":"2005","unstructured":"Lucena, A.: Non delayed relax-and-cut algorithms. Ann. Oper. Res. 140(1), 375\u2013410 (2005)","journal-title":"Ann. Oper. Res."},{"key":"9763_CR27","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-0-387-30165-5_5","volume-title":"Handbook of Optimization in Telecommunications","author":"A Lucena","year":"2006","unstructured":"Lucena, A.: Lagrangian relax-and-cut algorithms. In: Resende, M., Pardalos, P. (eds.) Handbook of Optimization in Telecommunications, pp. 129\u2013145. Springer, New York (2006)"},{"key":"9763_CR28","doi-asserted-by":"crossref","unstructured":"Maniezzo, V., St\u00fctzle, T., Vo\u00df, S. (eds.): Matheuristics\u2014Hybridizing Metaheuristics and Mathematical Programming, Annals of Information Systems, vol. 10. Springer (2010)","DOI":"10.1007\/978-1-4419-1306-7"},{"key":"9763_CR29","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)"},{"key":"9763_CR30","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/0377-2217(94)00286-X","volume":"92","author":"P Michelon","year":"1996","unstructured":"Michelon, P., Veilleux, L.: Lagrangean methods for the 0\u20131 quadratic knapsack problem. Eur. J. Oper. Res 92, 326\u2013341 (1996)","journal-title":"Eur. J. Oper. Res"},{"key":"9763_CR31","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"9763_CR32","unstructured":"Palmeira, M.: Um algoritmo relax-and-cut para o problema quadrtico da mochila binria. Master\u2019s thesis, PUC, Rio de Janeiro, RJ, Brasil (1999)"},{"key":"9763_CR33","doi-asserted-by":"crossref","unstructured":"Pisinger, D.: The quadratic knapsack problem\u2014a survey. Discret. Appl. Math. 623\u2013648 (2007)","DOI":"10.1016\/j.dam.2006.08.007"},{"key":"9763_CR34","doi-asserted-by":"crossref","unstructured":"Pisinger, D., Toth, P.: Knapsack problems. In: Du, D., Pardalos, P. (eds.) Handbook of Combinatorial Optimization. Kluwer Academic Publishers (1998)","DOI":"10.1007\/978-1-4613-0303-9_5"},{"key":"9763_CR35","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1287\/mnsc.17.3.200","volume":"17","author":"J Rhys","year":"1970","unstructured":"Rhys, J.: A selection problem of shared fixed costs and network flows. Manag. Sci. 17, 200\u2013207 (1970)","journal-title":"Manag. Sci."},{"key":"9763_CR36","doi-asserted-by":"crossref","first-page":"14491468","DOI":"10.1137\/110820762","volume":"22","author":"CD Rodrigues","year":"2012","unstructured":"Rodrigues, C.D., Quadri, Q., Michelon, P., Gueye, S.: 0\u20131 quadratic knapsack problems: an exact approach based on t-linearization. SIAM J. Optim. 22, 14491468 (2012)","journal-title":"SIAM J. Optim."},{"key":"9763_CR37","doi-asserted-by":"crossref","unstructured":"Witzgall, C.: Mathematical methods of site selection for electronic message system (ems). Technical Report, NBS Internal Report (1975)","DOI":"10.6028\/NBS.IR.75-737"},{"key":"9763_CR38","volume-title":"Integer Programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Wiley, New York (1998)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-015-9763-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-015-9763-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-015-9763-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,25]],"date-time":"2019-08-25T07:44:00Z","timestamp":1566719040000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-015-9763-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,23]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9763"],"URL":"https:\/\/doi.org\/10.1007\/s10589-015-9763-3","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,23]]}}}