{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:24:12Z","timestamp":1774369452080,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2009,6,6]],"date-time":"2009-06-06T00:00:00Z","timestamp":1244246400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s10107-009-0284-7","type":"journal-article","created":{"date-parts":[[2009,6,6]],"date-time":"2009-06-06T00:59:55Z","timestamp":1244249995000},"page":"19-41","source":"Crossref","is-referenced-by-count":26,"title":["On the exact separation of mixed integer knapsack cuts"],"prefix":"10.1007","volume":"128","author":[{"given":"Ricardo","family":"Fukasawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcos","family":"Goycoolea","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,6,6]]},"reference":[{"key":"284_CR1","unstructured":"Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1\u201312 (2006). doi: 10.1016\/j.orl.2005.07.009 . http:\/\/www.zib.de\/Publications\/abstracts\/ZR-05-28\/ . See http:\/\/miplib.zib.de"},{"key":"284_CR2","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/S0377-2217(99)00265-9","volume":"123","author":"R. Andonov","year":"2000","unstructured":"Andonov R., Poirriez V., Rajopadhye S.: Unbounded knapsack problem: dynamic programming revisited. Eur. J. Oper. Res. 123, 394\u2013407 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"284_CR3","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-45586-8_7","volume-title":"Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School]","author":"D. Applegate","year":"2001","unstructured":"Applegate D., Bixby R.E., Chv\u00e1tal V., Cook W.: TSP cuts which do not conform to the template paradigm. In: (eds) Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], pp. 261\u2013304. Springer-Verlag GmbH, London (2001)"},{"key":"284_CR4","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1016\/j.orl.2006.12.010","volume":"35","author":"D. Applegate","year":"2007","unstructured":"Applegate D., Cook W., Dash S., Espinoza D.: Exact solutions to linear programming problems. Oper. Res. Lett. 35, 693\u2013699 (2007)","journal-title":"Oper. Res. Lett."},{"key":"284_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10107-003-0400-z","volume":"98","author":"A. Atamt\u00fcrk","year":"2003","unstructured":"Atamt\u00fcrk A.: On the facets of the mixed\u2013integer knapsack polyhedron. Math. Program. 98, 145\u2013175 (2003)","journal-title":"Math. Program."},{"key":"284_CR6","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1287\/opre.1030.0099","volume":"52","author":"A. Atamt\u00fcrk","year":"2004","unstructured":"Atamt\u00fcrk A.: Sequence independent lifting for mixed\u2013integer programming. Oper. Res. 52, 487\u2013490 (2004)","journal-title":"Oper. Res."},{"key":"284_CR7","unstructured":"Avella, P., Boccia, M., Vasilyev, I.: A computational study of exact knapsack separation for the generalized assignment problem. Technical report available at Optimization Online (2006)"},{"key":"284_CR8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10107-002-0317-y","volume":"94","author":"E. Balas","year":"2003","unstructured":"Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjuntive cuts, and mixed integer Gomory cuts for 0\u20131 programming. Math. Program. 94, 221\u2013245 (2003)","journal-title":"Math. Program."},{"issue":"2","key":"284_CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10107-006-0049-5","volume":"113","author":"E. Balas","year":"2008","unstructured":"Balas E., Saxena A.: Optimizing over the split closure. Math. Program. 113(2), 219\u2013240 (2008)","journal-title":"Math. Program."},{"issue":"1","key":"284_CR10","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/0134010","volume":"34","author":"E. Balas","year":"1978","unstructured":"Balas E., Zemel E.: Facets of knapsack polytope from minimal covers. SIAM J. Appl. Math. 34(1), 119\u2013148 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"284_CR11","volume-title":"Dynamic Programming","author":"R.E. Bellman","year":"1957","unstructured":"Bellman R.E.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"284_CR12","doi-asserted-by":"crossref","unstructured":"Bixby, R., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: a progress report. In: The sharpest cut: the impact of Manfred Padberg and his work. MPS\/SIAM Series on Optimization, pp. 309\u2013326","DOI":"10.1137\/1.9780898718805.ch18"},{"key":"284_CR13","first-page":"12","volume":"58","author":"R.E. Bixby","year":"1998","unstructured":"Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12\u201315 (1998)","journal-title":"Optima"},{"issue":"2","key":"284_CR14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10107-006-0051-y","volume":"113","author":"P. Bonami","year":"2008","unstructured":"Bonami P., Cornu\u00e9jols G., Dash S., Fischetti M., Lodi A.: Projected Chv\u00e1tal Gomory cuts for mixed integer linear programs. Math. Program. 113(2), 241\u2013257 (2008)","journal-title":"Math. Program."},{"key":"284_CR15","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1287\/opre.42.1.53","volume":"42","author":"A.E. Boyd","year":"1992","unstructured":"Boyd A.E.: Fenchel cutting planes for integer programs. Oper. Res. 42, 53\u201364 (1992)","journal-title":"Oper. Res."},{"key":"284_CR16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01580858","volume":"47","author":"W. Cook","year":"1990","unstructured":"Cook W., Kannan R., Schrijver A.: Chv\u00e1tal closures for mixed integer programming problems. Math. Program. 47, 155\u2013174 (1990)","journal-title":"Math. Program."},{"issue":"4","key":"284_CR17","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1287\/ijoc.15.4.385.24893","volume":"15","author":"G. Cornu\u00e9jols","year":"2003","unstructured":"Cornu\u00e9jols G., Li Y., Vanderbussche D.: K-cuts: a variation of Gomory mixed integer cuts from the LP tableau. INFORMS J. Comput. 15(4), 385\u2013396 (2003)","journal-title":"INFORMS J. Comput."},{"key":"284_CR18","unstructured":"CPLEX: http:\/\/www.ilog.com\/products\/cplex"},{"issue":"5","key":"284_CR19","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H. Crowder","year":"1983","unstructured":"Crowder H., Johnson E., Padberg M.: Solving large-scale zero-one linear-programming problems. Oper. Res. 31(5), 803\u2013834 (1983)","journal-title":"Oper. Res."},{"issue":"2","key":"284_CR20","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"G.B. Dantzig","year":"1957","unstructured":"Dantzig G.B.: Discrete variable extremum problems. Oper. Res. 5(2), 266\u2013277 (1957)","journal-title":"Oper. Res."},{"key":"284_CR21","doi-asserted-by":"crossref","unstructured":"Dash, S., G\u00fcnl\u00fck, O.: On the strength of gomory mixed-integer cuts as group cuts. IBM research report RC23967 (2006)","DOI":"10.1007\/s10107-007-0179-4"},{"key":"284_CR22","doi-asserted-by":"crossref","unstructured":"Dash, S., G\u00fcnl\u00fck, O., Lodi, A.: On the MIR closure of polyhedra. In: Fischetti, M., Williamson, D. (eds.). IPCO, Lecture notes in computer science, vol. 4513, pp. 337\u2013351 (2007)","DOI":"10.1007\/978-3-540-72792-7_26"},{"issue":"2","key":"284_CR23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"E. Dolan","year":"2001","unstructured":"Dolan E., Mor\u00e9 J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2001)","journal-title":"Math. Program."},{"issue":"2","key":"284_CR24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s10107-004-0520-0","volume":"102","author":"F. Eisenbrand","year":"2005","unstructured":"Eisenbrand F., Laue S.: A linear algorithm for integer programming in the plane. Math. Program. 102(2), 249\u2013259 (2005)","journal-title":"Math. Program."},{"key":"284_CR25","unstructured":"Fischetti, M., Lodi, A.: On the knapsack closure of 0\u20131 integer linear problems. In: Presentation at 10th International Workshop on Combinatorial Optimization, Aussois (2006). Available at http:\/\/www-id.imag.fr\/IWCO2006\/slides\/Fischetti.pdf"},{"issue":"1","key":"284_CR26","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-006-0054-8","volume":"110","author":"M. Fischetti","year":"2007","unstructured":"Fischetti M., Lodi A.: Optimizing over the first Chv\u00e1tal closure. Math. Programm. B 110(1), 3\u201320 (2007)","journal-title":"Math. Programm. B"},{"key":"284_CR27","unstructured":"Fischetti, M., Salvagnin, D.: A local dominance procedure for mixed-integer linear programming. http:\/\/www.dei.unipd.it\/~fisch\/papers\/MIPdominance.pdf"},{"key":"284_CR28","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0167-6377(88)90025-9","volume":"7","author":"M. Fischetti","year":"1988","unstructured":"Fischetti M., Toth P.: A new dominance procedure for combinatorial optimization problems. Oper. Res. Lett. 7, 181\u2013187 (1988)","journal-title":"Oper. Res. Lett."},{"key":"284_CR29","unstructured":"Fukasawa, R.: Single-row mixed-integer programs: Theory and computations. Ph.D. thesis, Georgia Institute of Technology (2008)"},{"issue":"1","key":"284_CR30","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1287\/opre.50.1.78.17793","volume":"50","author":"R.E. Gomory","year":"2002","unstructured":"Gomory R.E.: Early integer programming (reprinted). Oper. Res. 50(1), 78\u201381 (2002)","journal-title":"Oper. Res."},{"key":"284_CR31","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01584976","volume":"3","author":"R.E. Gomory","year":"1972","unstructured":"Gomory R.E., Johnson E.: Some continuous functions related to corner polyhedra I. Math. Program. 3, 23\u201385 (1972)","journal-title":"Math. Program."},{"key":"284_CR32","unstructured":"Goycoolea, M.: Cutting planes for large mixed integer programming models. Ph.D. thesis, Georgia Institute of Technology (2006)"},{"key":"284_CR33","unstructured":"Granlund, T.: The GNU multiple precision arithmetic library. Available on-line at http:\/\/www.swox.com\/gmp\/"},{"key":"284_CR34","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1287\/ijoc.10.4.427","volume":"10","author":"Z. Gu","year":"1998","unstructured":"Gu Z., Nemhauser G.L., Savelsbergh M.W.P.: Lifted cover inequalities for 0\u20131 integer programs: computation. INFORMS J. Comput. 10, 427\u2013437 (1998)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"284_CR35","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1023\/A:1009841107478","volume":"4","author":"Z. Gu","year":"2000","unstructured":"Gu Z., Nemhauser G.L., Savelsbergh M.W.P.: Sequence independent lifting in mixed integer programming. J. Combin Optimiz. 4(1), 109\u2013129 (2000)","journal-title":"J. Combin Optimiz."},{"key":"284_CR36","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz E., Sahni S.: Computing partitions with applications to the knapsack problem. J. ACM 21, 277\u2013292 (1974)","journal-title":"J. ACM"},{"key":"284_CR37","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/322003.322010","volume":"24","author":"T. Ibaraki","year":"1977","unstructured":"Ibaraki T.: The power of dominance relations in branch-and-bound algorithms. J. ACM 24, 264\u2013279 (1977)","journal-title":"J. ACM"},{"key":"284_CR38","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/322169.322179","volume":"27","author":"R. Kannan","year":"1980","unstructured":"Kannan R.: A polynomial algorithm for the two-variable integer programming problem. J. ACM 27, 118\u2013122 (1980)","journal-title":"J. ACM"},{"key":"284_CR39","unstructured":"Kaparis, K., Letchford, A.: Separation algorithms for 0\u20131 knapsack polytopes. Technical report available at Optimization Online (2007)"},{"key":"284_CR40","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":"284_CR41","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/opre.49.3.363.11211","volume":"49","author":"H. Marchand","year":"2001","unstructured":"Marchand H., Wolsey L.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363\u2013371 (2001)","journal-title":"Oper. Res."},{"key":"284_CR42","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":"284_CR43","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01585752","volume":"46","author":"G.L. Nemhauser","year":"1990","unstructured":"Nemhauser G.L., Wolsey L.A.: A recursive procedure for generating all cuts for 0-1 mixed integer programs. Math. Program. 46, 379\u2013390 (1990)","journal-title":"Math. Program."},{"key":"284_CR44","volume-title":"Integer and Combinatorial Optimization. Discrete Mathematics and Optimization","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Discrete Mathematics and Optimization. Wiley, New York (1999)"},{"key":"284_CR45","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"M. Savelsbergh","year":"1994","unstructured":"Savelsbergh M.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445\u2013454 (1994)","journal-title":"ORSA J. Comput."},{"key":"284_CR46","doi-asserted-by":"crossref","first-page":"395","DOI":"10.2307\/1913318","volume":"49","author":"H.E. Scarf","year":"1981","unstructured":"Scarf H.E.: Production sets with indivisibilities\u2014part II: the case of two activities. Econometrica 49, 395\u2013423 (1981)","journal-title":"Econometrica"},{"issue":"2","key":"284_CR47","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1287\/opre.24.2.367","volume":"24","author":"L. Wolsey","year":"1976","unstructured":"Wolsey L.: Facets and strong valid inequalities for integer programs. Oper. Res. 24(2), 367\u2013372 (1976)","journal-title":"Oper. Res."},{"issue":"2","key":"284_CR48","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01581108","volume":"81","author":"X.Q. Yan","year":"1998","unstructured":"Yan X.Q., Boyd E.A.: Cutting planes for mixed-integer knapsack polyhedra. Math. Program. 81(2), 257\u2013262 (1998)","journal-title":"Math. Program."},{"issue":"1","key":"284_CR49","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/BF01609032","volume":"15","author":"E. Zemel","year":"1978","unstructured":"Zemel E.: Lifting the facets of zero-one polytopes. Math. Program. 15(1), 268\u2013277 (1978)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-009-0284-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-009-0284-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-009-0284-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T15:05:51Z","timestamp":1685027151000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-009-0284-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,6]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["284"],"URL":"https:\/\/doi.org\/10.1007\/s10107-009-0284-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,6]]}}}