Cutting planes and infeasibility certificates from lattice-point-free polyhedra

English

Louveaux, Quentin[Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]

Jul-2007

No

Yes

International

Workshop on Mixed-Integer Programming

July 2007

Montreal

Canada

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