La valeur optimale des programmes entiers
Comptes Rendus. Mathématique, Tome 335 (2002) no. 11, pp. 863-866.

On donne une expression de la valeur optimale fc(y) du programme entier max {c'xxΩ(y) n }Ω(y) est le polyèdre convexe {x n Ax =y,x0}. 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'xxΩ(y) n } where Ω(y) is the convex polyhedron {x n Ax =y,x0}. 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
Lasserre, Jean B. 1

1 LAAS-CNRS, 7, avenue du Colonel Roche, 31077 Toulouse cedex 4, France
@article{CRMATH_2002__335_11_863_0,
     author = {Lasserre, Jean B.},
     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},
     url = {http://archive.numdam.org/articles/10.1016/S1631-073X(02)02591-8/}
}
TY  - JOUR
AU  - Lasserre, Jean B.
TI  - La valeur optimale des programmes entiers
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 863
EP  - 866
VL  - 335
IS  - 11
PB  - Elsevier
UR  - http://archive.numdam.org/articles/10.1016/S1631-073X(02)02591-8/
DO  - 10.1016/S1631-073X(02)02591-8
LA  - fr
ID  - CRMATH_2002__335_11_863_0
ER  - 
%0 Journal Article
%A Lasserre, Jean B.
%T La valeur optimale des programmes entiers
%J Comptes Rendus. Mathématique
%D 2002
%P 863-866
%V 335
%N 11
%I Elsevier
%U http://archive.numdam.org/articles/10.1016/S1631-073X(02)02591-8/
%R 10.1016/S1631-073X(02)02591-8
%G fr
%F CRMATH_2002__335_11_863_0
Lasserre, Jean B. La valeur optimale des programmes entiers. Comptes Rendus. Mathématique, Tome 335 (2002) no. 11, pp. 863-866. doi : 10.1016/S1631-073X(02)02591-8. http://archive.numdam.org/articles/10.1016/S1631-073X(02)02591-8/

[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

Cité par Sources :