La valeur optimale des programmes entiers

We present a formula for the optimal value f_c(y) of the integer program $\text{max}\text{{c′x∣x∈}\text{Ω}\text{(y)∩}\text{N}{}^{\mathrm{n}}\text{}}$ where $\text{Ω}\text{(y)}$ is the convex polyhedron $\text{{x∈}\text{R}{}^{\mathrm{n}}\text{∣Ax=y,}\text{x?0}}$. It is a consequence of Brion and Vergne's formula which evaluates the sum . As in linear programming, f_c(y) can be obtained by inspection of the reduced-costs at the vertices of the polyhedron. We also provide an explicit result that relates f_c(ty) and the optimal value of the associated continous linear program, for large values of $\text{t∈}\text{N}$. To cite this article: J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863–866.