Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

In this talk we deal with an algorithmic solution to the following problem: Does the system of linear inequalities Az<=b have an integer solution? If yes, produce one. Without integrality constraints, the elimination step due to Fourier-Motzkin reduces the above question to the solution of a system A'z'<=b' in one variable less. Our problem is clearly solved if we do this elimination step recursively. Whereas Fourier-Motzkin elimination is a fairly well-known procedure, its integral counter-part is not. Herein, the original system is reduced not only to one, but to several smaller systems in one variable less. Moreover, congruences enter the scene.