Scanning integer points with lex-cuts: A finite cutting plane algorithm for integer programming with linear objective
Conforti, Michele ; De Santis, Marianna ; Di Summa, Marco ; Rinaldi, Francesco
arXiv, 1811.02345 / Harvested from arXiv
Text on arXiv
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-cuts) that defines the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-cuts contains the Chvatal-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{cx : x \in S \cap Z^n }, where S \subset R^n is a compact set and c \in Z^n . We analyze the number of iterations of our algorithm.
Publié le : 2018-11-06
Classification:  Mathematics - Optimization and Control,  90C10, 90C57 
@article{1811.02345,
     author = {Conforti, Michele and De Santis, Marianna and Di Summa, Marco and Rinaldi, Francesco},
     title = {Scanning integer points with lex-cuts: A finite cutting plane algorithm
  for integer programming with linear objective},
     journal = {arXiv},
     volume = {2018},
     number = {0},
     year = {2018},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1811.02345}
}

Conforti, Michele; De Santis, Marianna; Di Summa, Marco; Rinaldi, Francesco. Scanning integer points with lex-cuts: A finite cutting plane algorithm
  for integer programming with linear objective. arXiv, Tome 2018 (2018) no. 0, . http://gdmltest.u-ga.fr/item/1811.02345/