Comptes Rendus
no. 11
La valeur optimale des programmes entiers
Jean B. Lasserre1
1 LAAS-CNRS, 7, avenue du Colonel Roche, 31077 Toulouse cedex 4, France
Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 863-866.

On donne une expression de la valeur optimale fc(y) du programme entier max {c'x∣x∈Ω(y)∩ℕ n } où Ω(y) est le polyèdre convexe {x∈ℝ n ∣ Ax =y,x⩾0}. Elle est une conséquence de la formule de Brion et Vergne qui évalue la somme ∑ x∈Ω(y)∩ℕ n e c'x . On montre que comme en programmation linéaire, fc(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 fc(ty) à la valeur optimale du programme linéaire associé, pour des valeurs de t∈ℕ suffisamment grandes.

We present a formula for the optimal value fc(y) of the integer program max {c'x∣x∈Ω(y)∩ℕ n } where Ω(y) is the convex polyhedron {x∈ℝ n ∣ Ax =y,x⩾0}. It is a consequence of Brion and Vergne's formula which evaluates the sum ∑ x∈Ω(y)∩ℕ n e c'x . As in linear programming, fc(y) can be obtained by inspection of the reduced-costs at the vertices of the polyhedron. We also provide an explicit result that relates fc(ty) and the optimal value of the associated continous linear program, for large values of t∈ℕ.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(02)02591-8
Jean B. Lasserre 1

1 LAAS-CNRS, 7, avenue du Colonel Roche, 31077 Toulouse cedex 4, France 
@article{CRMATH_2002__335_11_863_0,
     author = {Jean B. Lasserre},
     title = {La valeur optimale des programmes entiers},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {863--866},
     publisher = {Elsevier},
     volume = {335},
     number = {11},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02591-8},
     language = {fr},
}
TY  - JOUR
AU  - Jean B. Lasserre
TI  - La valeur optimale des programmes entiers
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 863
EP  - 866
VL  - 335
IS  - 11
PB  - Elsevier
DO  - 10.1016/S1631-073X(02)02591-8
LA  - fr
ID  - CRMATH_2002__335_11_863_0
ER  - 
%0 Journal Article
%A Jean B. Lasserre
%T La valeur optimale des programmes entiers
%J Comptes Rendus. Mathématique
%D 2002
%P 863-866
%V 335
%N 11
%I Elsevier
%R 10.1016/S1631-073X(02)02591-8
%G fr
%F CRMATH_2002__335_11_863_0
Jean B. Lasserre. La valeur optimale des programmes entiers. Comptes Rendus. Mathématique, Volume 335 (2002) no. 11, pp. 863-866. doi : 10.1016/S1631-073X(02)02591-8. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02591-8/

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

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

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

[4] A.V. Pukhlikov; A.G. Khovanskii 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] R. Thomas Algebraic methods in integer programming (C. Floudas; P. Pardalos, eds.), Encyclopedia of Optimization, Kluwer Academic, Dordrecht, 2001

Cité par Sources :

Commentaires - Politique