We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that define the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-inequalities contains the Chvátal–Gomory 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 min{:∈∩ℤ}, where ⊂ℝ is a compact set and ∈ℤ. We analyze the number of iterations of our algorithm.

Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective / Conforti, Michele; De Santis, Marianna; Di Summa, Marco; Rinaldi, Francesco. - In: 4OR. - ISSN 1619-4500. - 19:4(2021), pp. 531-548. [10.1007/s10288-020-00459-6]

Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective

De Santis, Marianna
;
2021

Abstract

We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that define the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-inequalities contains the Chvátal–Gomory 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 min{:∈∩ℤ}, where ⊂ℝ is a compact set and ∈ℤ. We analyze the number of iterations of our algorithm.
2021
Nonlinear integer programming; Valid inequalities; Cutting planemethod;
01 Pubblicazione su rivista::01a Articolo in rivista
Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective / Conforti, Michele; De Santis, Marianna; Di Summa, Marco; Rinaldi, Francesco. - In: 4OR. - ISSN 1619-4500. - 19:4(2021), pp. 531-548. [10.1007/s10288-020-00459-6]
File allegati a questo prodotto
File Dimensione Formato  
Conforti_Scanning-integer_2021.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 385.02 kB
Formato Adobe PDF
385.02 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1481130
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact