Reference : Cutting planes and infeasibility certificates from lattice-point-free polyhedra
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/122930
Cutting planes and infeasibility certificates from lattice-point-free polyhedra
English
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 >]
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.
http://hdl.handle.net/2268/122930
http://www.crm.umontreal.ca/MIP2007/index_e.shtml

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
montrealql.pdfAuthor preprint912.96 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.