La valeur optimale des programmes entiers

Abstract

On donne une expression de la valeur optimale f_c(y) du programme entier $\text{max}\text{{c′x∣x∈}\text{Ω}\text{(y)∩}\text{N}{}^{\mathrm{n}}\text{}}$ où $\text{Ω}\text{(y)}$ est le polyèdre convexe $\text{{x∈}\text{R}{}^{\mathrm{n}}\text{∣Ax=y,}\text{x⩾0}}$. Elle est une conséquence de la formule de Brion et Vergne qui évalue la somme . On montre que comme en programmation linéaire, f_c(y) peut être obtenue par inspection des coûts réduits aux sommets du polyèdre. On donne aussi un résultat explicite qui relie f_c(ty) à la valeur optimale du programme linéaire associé, pour des valeurs de $\text{t∈}\text{N}$ suffisamment grandes. Pour citer cet article : J.B. Lasserre, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 863–866. 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.