On donne une expression de la valeur optimale fc(y) du programme entier où est le polyèdre convexe . Elle est une conséquence de la formule de Brion et Vergne qui évalue la somme . 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 suffisamment grandes.
We present a formula for the optimal value fc(y) of the integer program where is the convex polyhedron . It is a consequence of Brion and Vergne's formula which evaluates the sum . 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 .
Accepté le :
Publié le :
Jean B. Lasserre 1
@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}, }
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] An arrangement of real hyperplanes and the partition function connected with it, Soviet Math. Dokl., Volume 36 (1988), pp. 589-593
[2] An algorithmic theory of lattice points in polyhedra, New Perspectives in Algebraic Combinatorics, MSRI Publications, 38, 1999, pp. 91-147
[3] Residue formulae, vector partition functions and lattice points in rational polytopes, J. Amer. Math. Soc., Volume 10 (1997), pp. 797-833
[4] 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] Algebraic methods in integer programming (C. Floudas; P. Pardalos, eds.), Encyclopedia of Optimization, Kluwer Academic, Dordrecht, 2001
Cité par Sources :
Commentaires - Politique