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.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.