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

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 defines the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-inequalities 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 is a compact set of R^n and c belongs to Z^n. We analyze the number of iterations of our algorithm.

Article

Download

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