{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:44:57Z","timestamp":1740141897649,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T00:00:00Z","timestamp":1608681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T00:00:00Z","timestamp":1608681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2015B5F27W"],"award-info":[{"award-number":["2015B5F27W"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Universit\u00e0 di Padova","award":["SID 2016"],"award-info":[{"award-number":["SID 2016"]}]},{"DOI":"10.13039\/501100004271","name":"Sapienza Universit\u00e0 di Roma","doi-asserted-by":"publisher","award":["RP11715C7D8537BA"],"award-info":[{"award-number":["RP11715C7D8537BA"]}],"id":[{"id":"10.13039\/501100004271","id-type":"DOI","asserted-by":"publisher"}]}],"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>We consider the integer points in a unimodular cone<jats:italic>K<\/jats:italic>ordered by a lexicographic rule defined by a lattice basis. To each integer point<jats:italic>x<\/jats:italic>in<jats:italic>K<\/jats:italic>we associate a family of inequalities (lex-inequalities) that define the convex hull of the integer points in<jats:italic>K<\/jats:italic>that are not lexicographically smaller than<jats:italic>x<\/jats:italic>. The family of lex-inequalities contains the Chv\u00e1tal\u2013Gomory cuts, but does not contain and is not contained in the family of split cuts. This provides a finite cutting plane method to solve the integer program<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\min \\{cx: x\\in S\\cap \\mathbb {Z}^n\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>min<\/mml:mo><mml:mo>{<\/mml:mo><mml:mi>c<\/mml:mi><mml:mi>x<\/mml:mi><mml:mo>:<\/mml:mo><mml:mi>x<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>S<\/mml:mi><mml:mo>\u2229<\/mml:mo><mml:msup><mml:mrow><mml:mi>Z<\/mml:mi><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msup><mml:mo>}<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where<jats:inline-formula><jats:alternatives><jats:tex-math>$$S\\subset \\mathbb {R}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>S<\/mml:mi><mml:mo>\u2282<\/mml:mo><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is a compact set and<jats:inline-formula><jats:alternatives><jats:tex-math>$$c\\in \\mathbb {Z}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>c<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:msup><mml:mrow><mml:mi>Z<\/mml:mi><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We analyze the number of iterations of our algorithm.<\/jats:p>","DOI":"10.1007\/s10288-020-00459-6","type":"journal-article","created":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T14:03:32Z","timestamp":1608732212000},"page":"531-548","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective"],"prefix":"10.1007","volume":"19","author":[{"given":"Michele","family":"Conforti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-5917","authenticated-orcid":false,"given":"Marianna","family":"De Santis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Di Summa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,12,23]]},"reference":[{"key":"459_CR1","doi-asserted-by":"crossref","unstructured":"Andersen K, Jensen AN (2013) Intersection cuts for mixed integer conic quadratic sets. In: International conference on integer programming and combinatorial optimization, pp 37\u201348","DOI":"10.1007\/978-3-642-36694-9_4"},{"issue":"1\u20132","key":"459_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(79)90011-8","volume":"1","author":"R Armstrong","year":"1979","unstructured":"Armstrong R, Charnes A, Phillips F (1979) Page cuts for integer interval linear programming. Discrete Appl Math 1(1\u20132):1\u201314","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"459_CR3","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 (1993) A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math Program 58(1\u20133):295\u2013324","journal-title":"Math Program"},{"key":"459_CR4","unstructured":"Bell DE (1973) A cutting plane algorithm for integer programs with an easy proof of convergence. Working paper 73-15, International Institute for Applied Systems Analysis, Laxenburg"},{"issue":"16\u201317","key":"459_CR5","doi-asserted-by":"publisher","first-page":"2778","DOI":"10.1016\/j.dam.2013.05.017","volume":"161","author":"P Belotti","year":"2013","unstructured":"Belotti P, G\u00f3ez JC, P\u00f3lik I, Ralphs TK, Terlaky T (2013) On families of quadratic surfaces having fixed intersections with two hyperplanes. Discrete Appl Math 161(16\u201317):2778\u20132793","journal-title":"Discrete Appl Math"},{"key":"459_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492913000032","volume":"22","author":"P Belotti","year":"2013","unstructured":"Belotti P, Kirches C, Leyffer S, Linderoth J, Luedtke J, Mahajan A (2013) Mixed-integer nonlinear optimization. Acta Numer 22:1\u2013131","journal-title":"Acta Numer"},{"key":"459_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.disopt.2016.10.001","volume":"24","author":"P Belotti","year":"2017","unstructured":"Belotti P, G\u00f3ez JC, P\u00f3lik I, Ralphs TK, Terlaky T (2017) A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization. Discrete Optim 24:3\u201331","journal-title":"Discrete Optim"},{"issue":"3","key":"459_CR8","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/nav.3800170307","volume":"17","author":"VJ Bowman","year":"1970","unstructured":"Bowman VJ, Nemhauser GL (1970) A finiteness proof for modified Dantzig cuts in integer programming. Naval Res Logist Q 17(3):309\u2013313","journal-title":"Naval Res Logist Q"},{"key":"459_CR9","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s10107-016-1045-z","volume":"162","author":"S Burer","year":"2017","unstructured":"Burer S, K\u0131l\u0131n\u00e7-Karzan F (2017) How to convexify the intersection of a second order cone and a nonconvex quadratic. Math Program 162:393\u2013429","journal-title":"Math Program"},{"key":"459_CR10","first-page":"97","volume":"17","author":"S Burer","year":"2012","unstructured":"Burer S, Letchford A (2012) Non-convex mixed-integer nonlinear programming: a survey. Surv Oper Res Manag Sci 17:97\u2013106","journal-title":"Surv Oper Res Manag Sci"},{"issue":"3","key":"459_CR11","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s101070050106","volume":"86","author":"S Ceria","year":"1999","unstructured":"Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math Program 86(3):595\u2013614","journal-title":"Math Program"},{"key":"459_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti M, Cornu\u00e9jols G, Zambelli G (2014) Integer programming, vol 271. Springer, Berlin"},{"key":"459_CR13","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10107-013-0649-9","volume":"145","author":"D Dadush","year":"2014","unstructured":"Dadush D, Dey SS, Vielma JP (2014) On the Chv\u00e1tal\u2013Gomory closure of a compact convex set. Math Program 145:327\u2013348","journal-title":"Math Program"},{"issue":"2","key":"459_CR14","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-005-0594-3","volume":"106","author":"A Frangioni","year":"2006","unstructured":"Frangioni A, Gentile C (2006) Perspective cuts for a class of convex 0\u20131 mixed integer programs. Math Program 106(2):225\u2013236","journal-title":"Math Program"},{"issue":"5","key":"459_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"R Gomory","year":"1958","unstructured":"Gomory R (1958) Outline of an algorithm for integer solutions to linear programs. Bull Am Math Soc 64(5):275\u2013278","journal-title":"Bull Am Math Soc"},{"key":"459_CR16","volume-title":"Recent advances in mathematical programming","author":"R Gomory","year":"1963","unstructured":"Gomory R (1963) An algorithm for integer solutions to linear programs. In: Wolfe P, Graves RL (eds) Recent advances in mathematical programming. McGraw-Hill, New York"},{"key":"459_CR17","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.dam.2015.08.010","volume":"201","author":"A Gupte","year":"2016","unstructured":"Gupte A (2016) Convex hulls of superincreasing knapsacks and lexicographic orderings. Discrete Appl Math 201:150\u2013163","journal-title":"Discrete Appl Math"},{"issue":"1","key":"459_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1051\/ro\/2016013","volume":"51","author":"Q He","year":"2017","unstructured":"He Q, Lee J (2017) Another pedagogy for pure-integer Gomory. RAIRO Oper Res 51(1):189\u2013197","journal-title":"RAIRO Oper Res"},{"issue":"4","key":"459_CR19","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s13675-017-0085-3","volume":"5","author":"J Lee","year":"2017","unstructured":"Lee J, Wiegele A (2017) Another pedagogy for mixed-integer Gomory. EURO J Comput Optim 5(4):455\u2013466","journal-title":"EURO J Comput Optim"},{"issue":"1\u20132","key":"459_CR20","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0866-5","volume":"155","author":"S Modaresi","year":"2016","unstructured":"Modaresi S, K\u0131l\u0131n\u00e7 MR, Vielma JP (2016) Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math Program 155(1\u20132):575\u2013611","journal-title":"Math Program"},{"issue":"6","key":"459_CR21","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.orl.2012.10.003","volume":"40","author":"J Neto","year":"2012","unstructured":"Neto J (2012) A simple finite cutting plane algorithm for integer programs. Oper Res Lett 40(6):578\u2013580","journal-title":"Oper Res Lett"},{"issue":"1","key":"459_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6377(85)90041-0","volume":"4","author":"JB Orlin","year":"1985","unstructured":"Orlin JB (1985) A finitely converging cutting plane technique. Oper Res Lett 4(1):1\u20133","journal-title":"Oper Res Lett"},{"key":"459_CR23","volume-title":"Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics","author":"A Schrijver","year":"1986","unstructured":"Schrijver A (1986) Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester"},{"issue":"3","key":"459_CR24","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s101070050103","volume":"86","author":"RA Stubbs","year":"1999","unstructured":"Stubbs RA, Mehrotra S (1999) A branch-and-cut method for 0\u20131 mixed convex programming. Math Program 86(3):515\u2013532","journal-title":"Math Program"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00459-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-020-00459-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00459-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T03:15:23Z","timestamp":1697426123000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-020-00459-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,23]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["459"],"URL":"https:\/\/doi.org\/10.1007\/s10288-020-00459-6","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2020,12,23]]},"assertion":[{"value":"5 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}