Home » Publication » 22812

Dettaglio pubblicazione

2020, 4OR, Pages -

Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective (01a Articolo in rivista)

Conforti Michele, De Santis Marianna, Di Summa Marco, Rinaldi Francesco

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.
Gruppo di ricerca: Continuous Optimization
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma