La valeur optimale des programmes entiers

Jean B. Lasserre

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

La valeur optimale des programmes entiers

Jean B. Lasserre ¹

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

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

Résumé
Abstract

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

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

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

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

Affiliations des auteurs :

Jean B. Lasserre ¹

¹ 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/

Bibliographie
Cité par

[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

Jean B. Lasserre Duality and a Farkas lemma for integer programs, Optimization, Volume 32 (2009), p. 15 | DOI:10.1007/978-0-387-98096-6_2
Jean B. Lasserre Generating functions and duality for integer programs, Discrete Optimization, Volume 1 (2004) no. 2, pp. 167-187 | DOI:10.1016/j.disopt.2003.12.002 | Zbl:1154.90549
Jesús A. De Loera; Raymond Hemmecke; Jeremiah Tauzer; Ruriko Yoshida Effective lattice point counting in rational convex polytopes, Journal of Symbolic Computation, Volume 38 (2004) no. 4, p. 1273 | DOI:10.1016/j.jsc.2003.04.003

Cité par 3 documents. Sources : Crossref, zbMATH

Commentaires - Politique