{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:49Z","timestamp":1740145189159,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"crossref","award":["S\/25-MCF\/OL J.0026.17"],"award-info":[{"award-number":["S\/25-MCF\/OL J.0026.17"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007370","name":"Universit\u00e9 Catholique de Louvain","doi-asserted-by":"publisher","award":["Fonds Speciaeux de Recherche"],"award-info":[{"award-number":["Fonds Speciaeux de Recherche"]}],"id":[{"id":"10.13039\/100007370","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007355","name":"Fondation Louvain","doi-asserted-by":"publisher","award":["COALESCENS"],"award-info":[{"award-number":["COALESCENS"]}],"id":[{"id":"10.13039\/100007355","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the problem of separating cover inequalities of maximum-depth exactly. We propose a pseudopolynomial-time dynamic-programming algorithm for its solution, thanks to which we show that this problem is weakly <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {N}}{\\mathcal {P}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>N<\/mml:mi>\n                    <mml:mi>P<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard (similarly to the problem of separating cover inequalities of maximum violation). We carry out extensive computational experiments on instances of the knapsack and the multi-dimensional knapsack problems with and without conflict constraints. The results show that, with a cutting-plane generation method based on the maximum-depth criterion, we can optimize over the cover-inequality closure by generating a number of cuts smaller than when adopting the standard maximum-violation criterion. We also introduce the Point-to-Hyperplane Distance Knapsack Problem (PHD-KP), a problem closely related to the separation problem for maximum-depth cover inequalities, and show how the proposed dynamic programming algorithm can be adapted for effectively solving the PHD-KP as well.<\/jats:p>","DOI":"10.1007\/s11590-021-01741-0","type":"journal-article","created":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T15:00:42Z","timestamp":1620054042000},"page":"449-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the exact separation of cover inequalities of maximum-depth"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9427-1562","authenticated-orcid":false,"given":"Daniele","family":"Catanzaro","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9568-4385","authenticated-orcid":false,"given":"Stefano","family":"Coniglio","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1839-5827","authenticated-orcid":false,"given":"Fabio","family":"Furini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,1]]},"reference":[{"issue":"1","key":"1741_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"1741_CR2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.ejor.2012.09.026","volume":"227","author":"E Amaldi","year":"2013","unstructured":"Amaldi, E., Coniglio, S.: A distance-based point-reassignment heuristic for the $$k$$-hyperplane clustering problem. Eur. J. Oper. Res. 227(1), 22\u201329 (2013)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"1741_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10107-012-0596-x","volume":"143","author":"E Amaldi","year":"2014","unstructured":"Amaldi, E., Coniglio, S., Gualandi, S.: Coordinated cutting plane generation via multi-objective separation. Math. Program. 143(1\u20132), 87\u2013110 (2014)","journal-title":"Math. Program."},{"issue":"2","key":"1741_CR4","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1287\/ijoc.1050.0162","volume":"19","author":"G Andreello","year":"2007","unstructured":"Andreello, G., Caprara, A., Fischetti, M.: Embedding $$\\{$$0, $$1\/2$$$$\\}$$-cuts in a branch-and-cut framework: a computational study. INFORMS J. Comput. 19(2), 229\u2013238 (2007)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"1741_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s10589-008-9183-8","volume":"45","author":"P Avella","year":"2010","unstructured":"Avella, P., Boccia, M., Vasilyev, I.: A computational study of exact knapsack separation for the generalized assignment problem. Comput. Optim. Appl. 45(3), 543\u2013555 (2010)","journal-title":"Comput. Optim. Appl."},{"issue":"1\u20133","key":"1741_CR6","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math. Program. 58(1\u20133), 295\u2013324 (1993)","journal-title":"Math. Program."},{"issue":"9","key":"1741_CR7","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1287\/mnsc.42.9.1229","volume":"42","author":"E Balas","year":"1996","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: Mixed 0\u20131 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42(9), 1229\u20131246 (1996)","journal-title":"Manag. Sci."},{"issue":"11","key":"1741_CR8","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"issue":"3","key":"1741_CR9","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1287\/ijoc.2016.0742","volume":"29","author":"A Bettinelli","year":"2017","unstructured":"Bettinelli, A., Cacchiani, V., Malaguti, E.: A branch-and-bound algorithm for the knapsack problem with conflict graph. INFORMS J. Comput. 29(3), 457\u2013473 (2017)","journal-title":"INFORMS J. Comput."},{"key":"1741_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1023\/A:1008324625522","volume":"16","author":"P Bradely","year":"2000","unstructured":"Bradely, P., Mangasarian, O.: $$k$$-plane clustering. J. Glob. Optim. 16, 23\u201332 (2000)","journal-title":"J. Glob. Optim."},{"issue":"1\u20133","key":"1741_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01582574","volume":"64","author":"S Chopra","year":"1994","unstructured":"Chopra, S., Rao, M.R.: The Steiner tree problem II: properties and classes of facets. Math. Program. 64(1\u20133), 231\u2013246 (1994)","journal-title":"Math. Program."},{"issue":"1","key":"1741_CR12","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1023\/A:1009642405419","volume":"4","author":"PC Chu","year":"1998","unstructured":"Chu, P.C., Beasley, J.E.: A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4(1), 63\u201386 (1998)","journal-title":"J. Heuristics"},{"key":"1741_CR13","unstructured":"Coniglio, S.: The impact of the norm on the $$k$$-hyperplane clustering problem: relaxations, restrictions, approximation factors, and exact formulations. In: Proceedings of the 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW), Frascati, Italy, pp. 118\u2013121 (2011)"},{"key":"1741_CR14","doi-asserted-by":"crossref","unstructured":"Coniglio, S., Tieves, M.: On the generation of cutting planes which maximize the bound improvement. In: International Symposium on Experimental Algorithms, pp. 97\u2013109. Springer (2015)","DOI":"10.1007\/978-3-319-20086-6_8"},{"key":"1741_CR15","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/j.orl.2019.10.011","volume":"47","author":"S Coniglio","year":"2019","unstructured":"Coniglio, S., D\u2019Andreagiovanni, F., Furini, F.: A lexicographic pricer for the fractional bin packing problem. Oper. Res. Lett. 47, 622\u2013628 (2019)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1741_CR16","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.ejor.2020.07.023","volume":"289","author":"S Coniglio","year":"2020","unstructured":"Coniglio, S., Furini, F., San Segundo, P.: A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. Eur. J. Oper. Res. 289(2), 435\u2013455 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"1741_CR17","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H Crowder","year":"1983","unstructured":"Crowder, H., Johnson, E.L., Padberg, M.: Solving large-scale zero-one linear programming problems. Oper. Res. 31(5), 803\u2013834 (1983)","journal-title":"Oper. Res."},{"issue":"4","key":"1741_CR18","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s11590-017-1227-5","volume":"12","author":"C D\u2019Ambrosio","year":"2018","unstructured":"D\u2019Ambrosio, C., Furini, F., Monaci, M., Traversi, E.: On the product knapsack problem. Optim. Lett. 12(4), 691\u2013712 (2018)","journal-title":"Optim. Lett."},{"issue":"1","key":"1741_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"M Delorme","year":"2016","unstructured":"Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1), 1\u201320 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1741_CR20","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1287\/ijoc.2014.0632","volume":"27","author":"F Furini","year":"2015","unstructured":"Furini, F., Iori, M., Martello, S., Yagiura, M.: Heuristic and exact algorithms for the interval min\u2013max regret knapsack problem. INFORMS J. Comput. 27(2), 392\u2013405 (2015)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"1741_CR21","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/j.ejor.2017.03.061","volume":"262","author":"F Furini","year":"2017","unstructured":"Furini, F., Ljubi\u0107, I., Sinnl, M.: An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem. Eur. J. Oper. Res. 262(2), 438\u2013448 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"1741_CR22","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.cor.2017.09.019","volume":"90","author":"F Furini","year":"2018","unstructured":"Furini, F., Monaci, M., Traversi, E.: Exact approaches for the knapsack problem with setups. Comput. Oper. Res. 90, 208\u2013220 (2018)","journal-title":"Comput. Oper. Res."},{"key":"1741_CR23","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s10479-019-03380-2","volume":"292","author":"C Hojny","year":"2019","unstructured":"Hojny, C., Gally, T., Habeck, O., L\u00fcthen, H., Matter, F., Pfetsch, M.E., Schmitt, A.: Knapsack polytopes: a survey. Ann. Oper. Res. 292, 469\u2013517 (2019)","journal-title":"Ann. Oper. Res."},{"issue":"1\u20132","key":"1741_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-010-0359-5","volume":"124","author":"K Kaparis","year":"2010","unstructured":"Kaparis, K., Letchford, A.N.: Separation algorithms for 0\u20131 knapsack polytopes. Math. Program. 124(1\u20132), 69\u201391 (2010)","journal-title":"Math. Program."},{"key":"1741_CR25","doi-asserted-by":"publisher","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)"},{"issue":"1\u20132","key":"1741_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0167-6377(98)00025-X","volume":"23","author":"D Klabjan","year":"1998","unstructured":"Klabjan, D., Tovey, C.A., Nemhauser, G.L.: The complexity of cover inequality separation. Oper. Res. Lett. 23(1\u20132), 35\u201340 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1741_CR27","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00453-008-9218-7","volume":"55","author":"AMCA Koster","year":"2009","unstructured":"Koster, A.M.C.A., Zymolka, A., Kutschka, M.: Algorithms to separate $$\\{0, \\frac{1}{2}\\}$$-chv\u00e1tal-gomory cuts. Algorithmica 55(2), 375\u2013391 (2009)","journal-title":"Algorithmica"},{"key":"1741_CR28","unstructured":"L\u00fcbbecke, M.: Engine Scheduling by Column Generation. PhD thesis, Technische Universit\u00e4t Braunschweig (2001)"},{"issue":"1\u20132","key":"1741_CR29","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0167-6377(98)00049-2","volume":"24","author":"OL Mangasarian","year":"1999","unstructured":"Mangasarian, O.L.: Arbitrary-norm separating plane. Oper. Res. Lett. 24(1\u20132), 15\u201323 (1999)","journal-title":"Oper. Res. Lett."},{"key":"1741_CR30","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)"},{"issue":"3","key":"1741_CR31","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Manag. Sci. 45(3), 414\u2013424 (1999)","journal-title":"Manag. Sci."},{"issue":"1","key":"1741_CR32","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1112\/plms\/s1-28.1.486","volume":"s1\u201328","author":"GB Mathews","year":"1896","unstructured":"Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. s1\u201328(1), 486\u2013490 (1896)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1741_CR33","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1999)"},{"issue":"1","key":"1741_CR34","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.cor.2007.08.002","volume":"36","author":"N Papadakos","year":"2009","unstructured":"Papadakos, N.: Integrated airline scheduling. Comput. Oper. Res. 36(1), 176\u2013195 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"1741_CR35","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Algorithms Appl. 13(2), 233\u2013249 (2009)","journal-title":"J. Algorithms Appl."},{"issue":"2","key":"1741_CR36","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/ijoc.1090.0344","volume":"22","author":"J Puchinger","year":"2010","unstructured":"Puchinger, J., Raidl, G.R., Pferschy, U.: The multidimensional knapsack problem: structure and algorithms. INFORMS J. Comput. 22(2), 250\u2013265 (2010)","journal-title":"INFORMS J. Comput."},{"key":"1741_CR37","unstructured":"Vanderbeck, F.: Decomposition and column generation for integer program. PhD thesis, Faculty of Applied Sciences, Universit\u00e9 Catholique de Louvain (1994)"},{"issue":"1","key":"1741_CR38","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s10107-009-0335-0","volume":"130","author":"A Zanette","year":"2011","unstructured":"Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: can a pure cutting plane algorithm work? Math. Program. 130(1), 153\u2013176 (2011)","journal-title":"Math. Program."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01741-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01741-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01741-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T00:04:09Z","timestamp":1645056249000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01741-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1741"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01741-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,5,1]]},"assertion":[{"value":"14 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}