La valeur optimale des programmes entiers

Lasserre, Jean B.¹

¹LAAS-CNRS, 7, avenue du Colonel Roche, 31077 Toulouse cedex 4, France

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

Résumé (VO)

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.

Abstract

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}$.

Détail

Reçu le : 2002-09-22
Accepté le : 2002-10-15
Publié le : 2002-11-12

DOI : 10.1016/S1631-073X(02)02591-8