Présentation

Article

1 - CONTEXTE

2 - EXEMPLE D'APPLICATION EN PRODUCTIQUE

  • 2.1 - Premier modèle : problème d'optimisation continue (convexe)
  • 2.2 - Second modèle (en nombres entiers) : cas de ressources discrètes
  • 2.3 - Particularités et difficulté de l'optimisation en nombres entiers
  • 2.4 - Importance particulière des problèmes linéaires en nombres entiers

3 - MÉTHODES DE PROGRAMMATION LINÉAIRE CONTINUE

  • 3.1 - Algorithme du simplexe
  • 3.2 - Méthodes de points intérieurs

4 - RÉSOLUTION EXACTE DES PROGRAMMES LINÉAIRES EN NOMBRES ENTIERS

Article de référence | Réf : AF1251 v1

Résolution exacte des programmes linéaires en nombres entiers
Optimisation en nombres entiers

Auteur(s) : Michel MINOUX

Date de publication : 10 avr. 2008

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

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’article

ABSTRACT

At this time, issues of convex or linear continuous optimization are quite easy to solve. The same does not apply to industrial applications imposing integrity constraints on all or a part of the variables. This article introduces the main concepts and algorithmic methods for the resolution of problems in integers by focusing on exact methods. The subject matter is illustrated through an industrial automation example highlighting characteristics distinct from problems in integers regarding continuous optimization. The principal theoretical and algorithmic tools allowing for the exact resolution of such problems is then presented.

Auteur(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.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1251


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

4. Résolution exacte des programmes linéaires en nombres entiers

Nous présentons dans ce paragraphe les idées qui fondent les principales méthodes connues de résolution exacte des programmes linéaires en nombres entiers. L'ordre de notre présentation suit pratiquement la chronologie selon laquelle ont été successivement développées les différentes méthodes. R. Gomory a été, dès la fin des années 1950, le pionnier du premier courant de recherche consistant à généraliser l'algorithme du simplexe pour prendre en compte les conditions d'intégrité sur les variables. Cette approche est décrite et illustrée dans le paragraphe . La deuxième approche, qui suit historiquement de peu la première, est connue sous le nom de « recherche arborescente par séparation et évaluation » (Branch & Bound) et est décrite au paragraphe . La troisième approche, connue depuis le début des années 1980 sous le nom de « combinatoire polyédrique » peut être considérée comme une combinaison des deux précédentes. Le paragraphe 4.3 lui est consacré.

4.1 Méthode des « coupes de Gomory »

L'idée de base de la méthode des coupes exploite l'efficacité bien connue de l'algorithme du simplexe, en particulier dans la fonction de réoptimisation. Lorsque l'on a obtenu la solution optimale d'un programme linéaire, il est souvent facile de déterminer la solution optimale d'un autre programme linéaire très peu différent du précédent (ajout ou retrait d'une colonne ou d'une contrainte, changement de quelques coefficients de la matrice des contraintes ou des seconds membres). Quelques pivots supplémentaires peuvent suffire, si l'on prend comme base de départ la base optimale du problème précédent.

La méthode proposée par Gomory Optimisation en nombres entiers[22] Optimisation en nombres entiers[23] consiste en un mécanisme d'adjonctions successives de contraintes supplémentaires (appelées « Coupes de Gomory »). Ces contraintes supplémentaires, choisies de façon...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Résolution exacte des programmes linéaires en nombres entiers
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - BALAS (E.) -   An Additive Algorithm for Solving Linear Programs with Zero-one Variables.  -  Operations Research, 13, 4, p. 517-546 (1965).

  • (2) - BALAS (E.) -   Disjunctive Programming.  -  Annals of Discrete Mathematics, 5, p. 3-51 (1979).

  • (3) - BALAS (E.), CERIA (S.), CORNUEJOLS (G.) -   Mixed 0-1 Programming by Lift & Project in a Branch-and-Cut Framework.  -  Management, 42, p. 1229-1246 (1996).

  • (4) - BALAS (E.), CERIA (S.), CORNUEJOLS (G.), NATRAJ (N.R.) -   Gomory Cuts revisited.  -  Operations Research Letters, 19, p. 1-9 (1996).

  • (5) - BERTIER (P.), ROY (B.) -   Une Procédure de résolution pour une classe de problèmes pouvant avoir un caractère combinatoire.  -  Cahiers du Centre d'Études de recherche Opérationnelle, 6, p. 202-208 (1964).

  • (6) - BLAND (R.G.) -   A Combinatorial Abstraction...

1 Outils

HAUT DE PAGE

1.1 Logiciels de résolution de programmes linéaires continus et en nombres entiers

COIN (en libre accès) http://www.coin-or.org

CPLEX http://www.ilog.com/produits/cplex

XPRESS-MP http://www.dashoptimization.com/home/products

HAUT DE PAGE

2 Événements

HAUT DE PAGE

2.1 Congrès

Congrès annuel de la ROADEF (recherche opérationnelle et d'aide à la décision), France.

Congrès annuel INFORMS (Institute For Operations Research and The Management Sciences), USA.

Congrès annuel européen de recherche opérationnelle EURO.

Congrès SMAI (tous les 4 ans).

...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS