Présentation
RÉSUMÉ
De nos jours, les problèmes d'optimisation continue linéaires ou convexes sont résolus assez facilement. Cependant, il n’en est pas de même d’applications industrielles imposant des contraintes d'intégrité sur tout ou partie des variables. Cet article introduit les principaux concepts et les principales méthodes algorithmiques pour la résolution de problèmes en nombres entiers en mettant l'accent sur les méthodes exactes. Tout d’abord, le sujet est illustré à travers un exemple en productique, faisant apparaître des caractéristiques distinctes des problèmes en nombres entiers par rapport à l'optimisation continue. Ensuite, l’ensemble des principaux outils théoriques et algorithmiques permettant d'aborder la résolution exacte de tels problèmes est présenté.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l'articleAUTEUR(S)
-
Michel MINOUX : Professeur à l'Université Pierre-et-Marie-Curie, Paris 6
INTRODUCTION
Les problèmes d'optimisation continue linéaires ou convexes sont résolus très efficacement. Par exemple, on résout couramment aujourd'hui des programmes linéaires continus ayant des dizaines, voire des centaines, de milliers de variables et de contraintes. Cependant, les applications industrielles imposent très fréquemment des contraintes d'intégrité sur tout ou partie des variables ; les problèmes qui en résultent sont généralement beaucoup plus difficiles que leurs versions continues. Les progrès réalisés depuis une vingtaine d'années permettent de résoudre efficacement beaucoup de ces problèmes, souvent de taille importante, mais on peut encore rencontrer aujourd'hui des problèmes comportant seulement quelques centaines de variables entières et de contraintes qui ne peuvent être résolus exactement en un temps raisonnable, disons en moins de quelques heures de calcul. Le présent dossier propose une vue d'ensemble des principaux outils théoriques et algorithmiques permettant d'aborder la résolution exacte de tels problèmes en mentionnant quelques-unes des applications les plus importantes.
Cet article est réservé aux abonnés. Il vous reste 92 % à découvrir.
Déjà abonné ? Se connecter
DOI (DIGITAL OBJECT IDENTIFIER)
Optimisation en nombres entiers
Contexte
Bibliographie
Références bibliographiques
Cet article est réservé aux abonnés. Il vous reste 92 % à découvrir.
Déjà abonné ? Se connecter
Article inclus dans l'offre
"Mathématiques"
(
228 articles
)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
