La valeur optimale des programmes entiers

Lasserre, Jean B.

Comptes Rendus. Mathématique, Tome 335 (2002) no. 11, pp. 863-866

On donne une expression de la valeur optimale f_c(y) du programme entier $\max \{\mathrm{c}\text{'}\mathrm{x}\mid \mathrm{x}\in \Omega \left(\mathrm{y}\right)\cap {\mathbb{N}}^n\}$ où $\Omega \left(\mathrm{y}\right)$ est le polyèdre convexe $\{\mathrm{x}\in {ℝ}^n\mid \mathrm{Ax}=\mathrm{y},\mathrm{x}⩾0\}$. Elle est une conséquence de la formule de Brion et Vergne qui évalue la somme ${\sum }_{\mathrm{x}\in \Omega \left(\mathrm{y}\right)\cap {\mathbb{N}}^n}{\mathrm{e}}^{\mathrm{c}\text{'}\mathrm{x}}$. 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 $\mathrm{t}\in \mathbb{N}$ suffisamment grandes.

We present a formula for the optimal value f_c(y) of the integer program $\max \{\mathrm{c}\text{'}\mathrm{x}\mid \mathrm{x}\in \Omega \left(\mathrm{y}\right)\cap {\mathbb{N}}^n\}$ where $\Omega \left(\mathrm{y}\right)$ is the convex polyhedron $\{\mathrm{x}\in {ℝ}^n\mid \mathrm{Ax}=\mathrm{y},\mathrm{x}⩾0\}$. It is a consequence of Brion and Vergne's formula which evaluates the sum ${\sum }_{\mathrm{x}\in \Omega \left(\mathrm{y}\right)\cap {\mathbb{N}}^n}{\mathrm{e}}^{\mathrm{c}\text{'}\mathrm{x}}$. 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 $\mathrm{t}\in \mathbb{N}$.

[1] Alekseevskaya, T.V.; Gel'fand, I.M.; Zelevinskij, A.V. An arrangement of real hyperplanes and the partition function connected with it, Soviet Math. Dokl., Volume 36 (1988), pp. 589-593

[2] Barvinok, A.I.; Pommersheim, J.E. An algorithmic theory of lattice points in polyhedra, New Perspectives in Algebraic Combinatorics, MSRI Publications, 38, 1999, pp. 91-147

[3] Brion, M.; Vergne, M. Residue formulae, vector partition functions and lattice points in rational polytopes, J. Amer. Math. Soc., Volume 10 (1997), pp. 797-833

[4] Pukhlikov, A.V.; Khovanskii, A.G. A Riemann–Roch theorem for integrals and sums of quasipolynomials over virtual polytopes, St. Petersburg Math. J., Volume 4 (1993), pp. 789-812

[5] A. Szenes, M. Vergne, Residue formulae for vector partitions and Euler–Maclaurin sums, Adv. Appl. Math., à paraître

[6] Thomas, R. Algebraic methods in integer programming (Floudas, C.; Pardalos, P., eds.), Encyclopedia of Optimization, Kluwer Academic, Dordrecht, 2001