Programmation Linéaire en Nombres Entiers — Optimisation exacte sur des décisions continues et entières
- Introduite par
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Année
- 1958–1960
- Type
- Mathematical optimization
- Famille
- Simulation / optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La Programmation Linéaire en Nombres Entiers (PLNE), ou Mixed-Integer Programming (MIP) en anglais, est un cadre d'optimisation mathématique dans lequel certaines variables de décision doivent prendre des valeurs entières tandis que d'autres peuvent être continues.
Elle généralise la programmation linéaire et est largement utilisée en recherche opérationnelle, logistique, ordonnancement, allocation de ressources et conception d'ingénierie, où les contraintes d'indivisibilité — telles que les décisions oui/non ou les quantités en unités entières — apparaissent naturellement.
L’intuition derrière la méthode
De nombreux problèmes d'optimisation réels impliquent des décisions qui ne peuvent pas être fractionnées — on ouvre une installation ou on ne l'ouvre pas, on assigne exactement un employé à un poste, on commande des unités entières. La programmation linéaire continue ignore ces réalités et peut produire des réponses fractionnaires non réalisables. La PLNE impose l'intégralité directement dans le modèle. Le solveur explore l'espace des solutions entières réalisables systématiquement par la méthode de séparation et évaluation (branch-and-bound) : il résout des sous-problèmes continus relaxés pour borner la meilleure solution possible dans chaque région, écarte les régions qui ne peuvent pas améliorer la meilleure solution entière trouvée jusqu'à présent, et ajoute des plans coupants pour resserrer la recherche. Le résultat est un plan prouvé optimal ou quasi-optimal.
Histoire
Les fondations de la programmation en nombres entiers ont été posées par Ralph Gomory, qui a introduit la méthode des plans coupants en 1958, et par Land et Doig, qui ont formalisé la séparation et évaluation en 1960. Les décennies suivantes ont vu le développement de la théorie de la relaxation linéaire, de la combinatoire polyédrique (Edmonds, Padberg, Grötschel), et dans les années 1990, les solveurs commerciaux ont rendu la PLNE à grande échelle pratique. Le domaine est traité de manière exhaustive dans Nemhauser et Wolsey (1988) et Wolsey (1998).
Quand l’utiliser
Utiliser la PLNE lorsque votre problème a un objectif et des contraintes linéaires ou linéarisables et inclut des décisions qui doivent être à valeurs entières (localisation d'installations, planification d'équipes, budgétisation des investissements, conception de réseaux, problèmes de découpe). C'est la méthode de choix lorsque vous avez besoin d'une solution prouvée optimale ou avec un écart borné, et que la taille du problème est traitable (des milliers de variables avec des solveurs modernes). N'UTILISEZ PAS la PLNE lorsque l'objectif ou les contraintes sont fortement non linéaires (utilisez la programmation non linéaire ou la programmation non linéaire en nombres entiers à la place), lorsque le problème est si grand que les méthodes exactes sont prohibitives (envisagez des heuristiques ou des métaheuristiques), ou lorsque des approximations continues sont suffisamment précises (utilisez la programmation linéaire pour la rapidité).
Limites et points d’attention
- La complexité dans le pire des cas est NP-difficile ; le temps de résolution peut croître exponentiellement avec le nombre de variables entières.
- Nécessite une formulation mathématique précise ; des modèles mal formulés peuvent être intraitable même lorsque le problème sous-jacent est gérable.
- Les éléments non convexes ou non linéaires nécessitent une linéarisation supplémentaire ou des solveurs spécialisés, augmentant la complexité du modèle.
- Les coûts de licence des solveurs peuvent être significatifs pour les outils commerciaux, bien que des alternatives open-source de haute qualité existent.
- Les résultats ne sont bons que si le modèle l'est : une spécification incorrecte des contraintes conduit à des optima dénués de sens.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Produit des solutions prouvées optimales avec un écart d'optimalité quantifiable, permettant une justification rigoureuse des décisions.
- Gère nativement les variables binaires et entières générales, capturant l'indivisibilité du monde réel et les contraintes logiques.
- Les solveurs modernes (Gurobi, CPLEX, SCIP) exploitent des techniques avancées de séparation et évaluation, de plans coupants et de pré-traitement pour gérer efficacement les grandes instances.
- La formulation transparente du modèle rend les hypothèses explicites et vérifiables par les experts du domaine.
- Prend en charge l'analyse de sensibilité et les études paramétriques pour comprendre comment les solutions évoluent avec les données d'entrée.
- Largement supporté par les langages de modélisation (AMPL, GAMS, Pyomo, JuMP) permettant un prototypage rapide.
Applications
- Chaîne d'approvisionnement et logistique : routage de véhicules, localisation d'installations et optimisation des stocks avec des quantités de livraison entières.
- Planification de la main-d'œuvre : rotation des infirmières, affectation des équipages et planification des postes avec des variables d'affectation binaires.
- Budgétisation des investissements : sélection d'un portefeuille de projets d'investissement indivisibles soumis à des contraintes budgétaires.
- Conception de réseaux et de télécommunications : expansion de capacité et routage avec des décisions binaires d'activation de liens.
- Systèmes énergétiques : engagement des unités dans les réseaux électriques, décidant quelles générateurs allumer ou éteindre chaque heure.
- Fabrication : détermination des tailles de lots de production, ordonnancement des machines et problèmes de découpe avec des tailles de lots entières.
Comment ça marche
Comment ça marche
Définir le modèle d'optimisation : une fonction objectif (combinaison linéaire de variables de décision à minimiser ou maximiser), des contraintes linéaires sous forme d'inégalités et d'égalités, et des exigences d'intégralité. Les variables continues gèrent les quantités qui peuvent être fractionnaires ; les variables binaires (0/1) ou entières générales gèrent les décisions discrètes.
Formule
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pRésoudre la relaxation linéaire en abandonnant temporairement les contraintes d'intégralité. Ceci donne une borne inférieure (pour une minimisation) sur l'objectif optimal de la PLNE et une solution candidate qui peut être fractionnaire.
Formule
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0Sélectionner une variable entière fractionnaire issue de la solution de la relaxation linéaire. Créer deux sous-problèmes enfants en ajoutant une contrainte d'arrondi inférieur dans l'un et une contrainte d'arrondi supérieur dans l'autre, partitionnant ainsi l'espace réalisable sans perdre aucun point réalisable par des entiers.
Formule
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilRésoudre la relaxation linéaire de chaque sous-problème. Si la borne est moins bonne que la meilleure solution entière trouvée jusqu'à présent (l'actuelle meilleure solution, ou 'incumbent'), élaguer cette branche. Si la solution de la relaxation linéaire se trouve être réalisable par des entiers, mettre à jour l'incumbent si elle améliore l'objectif.
Formule
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Optionnellement, ajouter des plans coupants — des inégalités valides qui coupent la solution fractionnaire de la relaxation linéaire sans retirer aucun point réalisable par des entiers. Les coupures de Gomory sont l'approche classique ; des coupures spécifiques au problème (par exemple, coupures de clique, coupures de flot) peuvent réduire considérablement la taille de l'arbre de recherche.
Formule
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Arrêter lorsque l'arbre de séparation et évaluation est entièrement exploré ou lorsque l'écart entre la meilleure solution entière et la borne inférieure globale tombe dans une tolérance spécifiée par l'utilisateur (par exemple, 0.01%). Retourner la solution incumbent avec son certificat d'optimalité.
Formule
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonPièges courants
- Choisir une tolérance d'écart d'optimalité trop faible peut faire tourner le solveur indéfiniment ; définissez toujours un écart pratique (par exemple, 1%) pour les grandes instances.
- La symétrie dans le modèle (par exemple, des installations interchangeables) crée des branches redondantes et fait exploser l'arbre de recherche — utilisez des contraintes de rupture de symétrie.
- Des relaxations linéaires faibles (grand écart d'intégralité) conduisent à de très grands arbres de séparation et évaluation ; investissez du temps dans l'ajout d'inégalités valides ou dans le resserrement de la formulation.
- Traiter toutes les variables comme entières alors que seules certaines le nécessitent est inutilement coûteux ; utilisez des variables binaires uniquement là où les contraintes logiques l'exigent.
- Ignorer le démarrage à chaud ('warm-starting') avec une bonne solution réalisable initiale gaspille le temps du solveur à trouver le premier incumbent.
Questions fréquentes
Quelle est la différence entre la PLNE et la programmation linéaire (PL) ?
La PL exige que toutes les variables de décision soient continues (à valeurs réelles), ce qui peut donner des solutions fractionnaires physiquement irréalisables (par exemple, 2.7 camions). La PLNE ajoute des contraintes d'intégralité sur certaines ou toutes les variables, imposant des solutions en nombres entiers ou binaires au prix d'une complexité de calcul accrue.
Quand devrais-je utiliser une heuristique au lieu de la PLNE ?
Lorsque le problème comporte des millions de variables, une structure fortement non linéaire, ou nécessite une solution quasi temps réel, la PLNE exacte peut être trop lente. Les métaheuristiques (algorithmes génétiques, recuit simulé) peuvent produire de bonnes solutions rapidement, mais sans garantie d'optimalité. La PLNE est préférée lorsque la certification de la qualité de la solution est importante.
Qu'est-ce que l'écart d'optimalité et quelle doit être sa valeur ?
L'écart est (objectif incumbent - borne PL) / borne PL, exprimé en pourcentage. Il certifie à quel point la meilleure solution entière connue peut être éloignée de l'optimum réel. Pour la plupart des applications pratiques, un écart de 0.1 à 1% est suffisant ; des écarts plus faibles nécessitent un temps de calcul exponentiellement plus long.
La PLNE peut-elle gérer des objectifs ou des contraintes non linéaires ?
La PLNE standard suppose la linéarité. Les relations non linéaires doivent être linéarisées (par exemple, approximation par morceaux linéaires, expansion binaire de produits) ou traitées par des solveurs de programmation non linéaire en nombres entiers mixtes (MINLP), qui sont significativement plus difficiles à résoudre.
Quels solveurs sont recommandés pour la PLNE ?
Commerciaux : Gurobi et CPLEX sont les références de l'industrie. Open-source : SCIP, CBC (via COIN-OR) et HiGHS sont compétitifs pour les problèmes de taille modérée. Tous supportent les interfaces de modélisation standard telles que AMPL, Pyomo et JuMP.
Méthodes associées
Sources
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN : 9780471359432Copié.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN : 9780471283669Copié.