Integral Farkas type lemmas for systems with equalities and inequalities

Kent Andersen, Quentin Louveaux and Robert Weismantel

No 2007051, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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, y T A integral such that y T b is fractional. We extend this result to systems that both have equations and inequalities {Ax = b, Cx d}. We show that a certificate of integral infeasibility is a linear system with rank(C) variables containing no integral point.

Date: 2007-07-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2007.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2007051

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().