Reference : Cutting planes and infeasibility certificates from lattice-point-free polyhedra
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
Cutting planes and infeasibility certificates from lattice-point-free polyhedra
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Workshop on Mixed-Integer Programming
July 2007
[en] Mixed-integer programming ; Certificates of infeasibility
[en] A central result in the theory of integer optimization states that a system of linear diophantine equations Ax = b has no integral solution if and only if there exists a vector in the dual lattice, yT A integral such that yT b is fractional. We extend this result to systems that both have equations and inequalities {Ax = b, C x ≤ d}. We show that a certificate of integral infeasibility is a linear system with rank(C) variables containing no integral point. The result also extends to the mixed integer setting.

File(s) associated to this reference

Fulltext file(s):

Open access
montrealql.pdfAuthor preprint912.96 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.