Integral Farkas type lemmas for systems with equalities and inequalities

Andersen, Kent;Louveaux, Quentin;Weismantel, Robert
(2007)

Files

ifl-dp2.pdf
  • Open Access
  • Adobe PDF
  • 196.42 KB
Download

Details

Authors
  • Andersen, Kent
    Author
  • Louveaux, QuentinUCLouvain
    Author
  • Weismantel, Robert
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Andersen, K., Louveaux, Q., & Weismantel, R. (2007). Integral Farkas type lemmas for systems with equalities and inequalities (CORE Discussion Papers 2007/51). https://hdl.handle.net/2078.5/129300