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

	Document type :	Scientific congresses and symposiums : Unpublished conference
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/2268/122930

Title :	Cutting planes and infeasibility certificates from lattice-point-free polyhedra
Language :	English
Author, co-author :	Louveaux, Quentin [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
Publication date :	Jul-2007
On invitation :	Yes
Audience :	International
Event name :	Workshop on Mixed-Integer Programming
Event date :	July 2007
Event place (city) :	Montreal
Event country :	Canada
Keywords :	[en] Mixed-integer programming ; Certificates of infeasibility
Abstract :	[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.
Permalink :	http://hdl.handle.net/2268/122930
Other URL :	http://www.crm.umontreal.ca/MIP2007/index_e.shtml

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access montrealql.pdf Author preprint 912.96 kB View/Open

All documents in ORBi are protected by a user license.

 

© ULg Library Network |  Feedback |  ORBi legal notices

Dspace v1.5