Programmation en nombres entiers — Programmation en nombres entiers (IP) et programmation mixte en nombres entiers (MIP)
- Introduite par
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Année
- 1958
- Type
- Mathematical optimisation — exact combinatorial method
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La programmation en nombres entiers (IP), également appelée programmation mixte en nombres entiers (MIP) lorsque seules certaines variables sont restreintes à des nombres entiers, est une branche de l'optimisation mathématique dans laquelle tout ou partie des variables de décision doivent prendre des valeurs entières ou binaires.
S'appuyant sur la programmation linéaire, elle a été formalisée par la méthode des plans coupants de Ralph Gomory (1958) et l'algorithme de séparation et évaluation de Land et Doig (1960), et est depuis devenue le cadre exact standard pour les problèmes d'ordonnancement, d'affectation, de tournées et d'allocation de ressources.
L’intuition derrière la méthode
La programmation linéaire ordinaire trouve le meilleur point dans une région réalisable continue. Mais de nombreuses décisions réelles sont discrètes : on ne peut pas affecter 2,7 infirmières ou ouvrir un demi-entrepôt. La programmation en nombres entiers ajoute la contrainte que certaines ou toutes les variables doivent être des nombres entiers (ou des choix binaires 0/1). Le prix de cette contrainte est le coût de calcul : l'ensemble réalisable n'est plus une surface lisse mais un ensemble de points dispersés, et trouver le meilleur peut nécessiter l'examen d'un nombre énorme de solutions candidates. Les solveurs gèrent cela en divisant intelligemment le problème en sous-problèmes plus petits (séparation) et en élaguant les branches qui ne peuvent pas surpasser la meilleure solution trouvée jusqu'à présent (évaluation), tout en resserrant l'approximation continue par des inégalités ajoutées (plans coupants).
Histoire
La programmation en nombres entiers a émergé à la fin des années 1950 alors que les chercheurs cherchaient à étendre la programmation linéaire aux décisions discrètes. Ralph Gomory a introduit la méthode systématique des plans coupants en 1958, prouvant que tout programme entier pouvait en principe être résolu en ajoutant un nombre fini de coupes. Land et Doig (1960) ont formalisé la méthode de séparation et évaluation (branch-and-bound), qui est devenue l'algorithme exact dominant. Wolsey (1998) et Nemhauser et Wolsey (1988) ont fourni les traitements de manuels canoniques sur lesquels le domaine repose encore. La révolution pratique est venue avec le développement des solveurs de branchement et coupe (branch-and-cut) dans les années 1990, combinant les deux techniques avec des heuristiques avancées, et plus tard avec l'explosion des performances des solveurs commerciaux et open-source qui permettent aujourd'hui des applications à grande échelle dans le monde réel.
Quand l’utiliser
Utilisez la programmation en nombres entiers lorsque les décisions sont intrinsèquement discrètes — choix binaires oui/non, quantités entières, ou contraintes logiques marche/arrêt — et lorsque vous avez besoin d'une solution optimale exacte ou quasi exacte avec une borne de qualité prouvable. Elle convient à l'ordonnancement, à l'affectation d'équipes et de ressources, à la planification des tournées de véhicules, à la localisation d'installations, à la budgétisation des investissements et à la sélection de portefeuille. Il n'y a pas d'exigence de taille d'échantillon minimale car la PI est un cadre d'optimisation déterministe plutôt qu'une procédure d'inférence statistique. Les types de variables peuvent être binaires, catégorielles (codées en binaires) ou continues (dans le cas mixte). L'exigence pratique clé est que le problème puisse être modélisé avec un objectif linéaire et des contraintes linéaires ; si l'objectif ou les contraintes sont non linéaires, des extensions de programmation non linéaire mixte en nombres entiers (MINLP) sont nécessaires.
Limites et points d’attention
- La programmation en nombres entiers est généralement NP-difficile ; le temps de résolution peut croître exponentiellement avec la taille du problème et une mauvaise formulation.
- Une relaxation LP faible (grand écart d'intégralité) conduit à des arbres de recherche profonds et coûteux et à de longs temps d'exécution.
- L'expansion binaire de variables catégorielles de grande cardinalité peut faire exploser la taille du modèle.
- Pour les instances très volumineuses, les solveurs peuvent devoir être arrêtés prématurément avec une tolérance d'écart plutôt que d'atteindre un écart nul.
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 optimales exactes avec un écart d'optimalité certifié, contrairement aux heuristiques qui n'offrent aucune garantie de qualité.
- Gère nativement les variables binaires et générales entières, ce qui en fait le cadre naturel pour les décisions combinatoires.
- Applicable à un large éventail de problèmes de domaine — ordonnancement, tournées, affectation, sac à dos — avec le même appareil mathématique.
- Les solveurs modernes de type branchement et coupe peuvent résoudre des problèmes avec des millions de variables et de contraintes qui auraient été insolubles il y a des décennies.
Applications
- Ordonnancement du personnel et des infirmières — affectation des quarts de travail pour répondre aux exigences de couverture tout en respectant la réglementation sur les heures de travail.
- Planification des tournées de véhicules et logistique — recherche des itinéraires de livraison à coût minimal sous contraintes de capacité et de fenêtres temporelles.
- Localisation d'installations — décision d'ouvrir quels entrepôts ou usines pour minimiser le coût total de distribution.
- Budgétisation des investissements — sélection d'un portefeuille de projets d'investissement dans les limites d'un budget pour maximiser le rendement total.
- Planification de la production — détermination des tailles de lots entières sur plusieurs périodes pour équilibrer les coûts de mise en route et les coûts de stockage.
- Conception de réseaux — choix des liens à installer dans un réseau de communication ou de transport.
Comment ça marche
Comment ça marche
Le problème est formulé comme un programme mathématique : définir les variables de décision (qui doivent être déclarées comme entières ou binaires lorsque le problème l'exige), écrire une fonction objectif linéaire à minimiser ou maximiser, et lister toutes les contraintes linéaires. Une formulation serrée — dont la relaxation linéaire (LP) est aussi proche que possible de l'optimum entier réel — réduit considérablement le temps de résolution.
Les restrictions d'intégralité sont temporairement abandonnées pour obtenir la relaxation LP. La résolution de cette relaxation est rapide et donne une borne : sa valeur optimale est toujours au moins aussi bonne que l'optimum entier réel (une borne inférieure pour la minimisation). Si la solution de relaxation s'avère être entièrement entière, le problème est résolu. Sinon, l'écart entre la relaxation et l'intégralité guide la recherche.
Une variable fractionnaire dans la solution de relaxation est sélectionnée et le problème est divisé en deux sous-problèmes — l'un exigeant que cette variable soit arrondie à l'inférieure, l'autre arrondie à la supérieure. Chaque sous-problème est lui-même relaxé et résolu, créant un arbre de recherche. Les branches dont la borne de relaxation est pire que la meilleure solution entière trouvée jusqu'à présent sont élaguées sans exploration supplémentaire.
Les plans coupants sont des inégalités linéaires valides qui coupent une partie de la région réalisable de la relaxation LP sans supprimer aucun point réalisable entier. L'ajout de coupes fortes (coupes de Gomory, inégalités de couverture, coupes de clique) resserre la borne LP et réduit le nombre de nœuds que le solveur doit explorer.
La meilleure solution entière réalisable trouvée sur tous les nœuds explorés est retournée comme optimum. L'écart d'optimalité — la différence en pourcentage entre la meilleure solution entière et la meilleure borne restante — est rapporté ; un écart de zéro certifie l'optimalité globale. Pour les instances NP-difficiles de grande taille, le solveur peut se terminer prématurément avec une tolérance d'écart spécifiée par l'utilisateur, retournant une solution quasi optimale avec une borne prouvable.
Pièges courants
- Déclarer des variables comme continues alors qu'elles devraient être entières — ou vice versa — produit silencieusement des solutions erronées ; vérifiez toujours que les types de variables correspondent à la réalité physique du problème.
- Une formulation lâche avec un grand écart de relaxation LP provoque un branchement excessif ; investissez du temps dans le resserrement de la formulation (inégalités fortes, rupture de symétrie) avant la résolution.
- Ignorer l'écart d'intégralité dans la sortie du solveur : une valeur objectif rapportée n'est que la meilleure solution entière trouvée, pas nécessairement l'optimum global à moins que l'écart ne soit nul.
- Appliquer la PI à des problèmes dont l'objectif ou les contraintes sont non linéaires sans traitement MINLP approprié produira des modèles incorrects.
- Pour les problèmes d'ordonnancement ou de tournées, omettre d'ajouter des inégalités valides (telles que les coupes de clique ou de couverture) laisse des gains de performance substantiels sur la table.
Questions fréquentes
Quelle est la différence entre IP et MIP ?
En programmation entière pure (IP), toutes les variables de décision doivent être des entiers. En programmation mixte en nombres entiers (MIP), certaines variables sont entières ou binaires tandis que d'autres sont autorisées à être continues. MIP est le cadre le plus général et le plus couramment utilisé en pratique, car la plupart des problèmes réels mélangent des choix discrets avec des quantités continues.
Pourquoi la programmation en nombres entiers est-elle NP-difficile si la programmation linéaire est polynomiale ?
La programmation linéaire optimise sur un polytope convexe et peut être résolue en temps polynomial par les méthodes du simplexe ou des points intérieurs. L'ajout de contraintes d'intégralité brise cette convexité : l'ensemble réalisable devient un ensemble fini mais potentiellement astronomiquement grand de points entiers, et aucun algorithme en temps polynomial n'est connu pour trouver le meilleur en général. La relaxation LP fournit une borne mais pas une solution directe.
Comment savoir si ma solution est optimale ?
Le solveur rapporte un écart d'optimalité — la différence en pourcentage entre la meilleure solution entière trouvée et la meilleure borne inférieure restante. Un écart de 0 % certifie l'optimalité globale. Pour les problèmes volumineux, vous pouvez définir une tolérance d'écart (par exemple, 1 %) et accepter une solution quasi optimale ; la borne garantit toujours que l'optimum réel ne peut pas être meilleur de plus de ce pourcentage.
Qu'est-ce qu'une formulation 'serrée' et pourquoi est-ce important ?
Une formulation serrée est celle dont la relaxation LP donne une borne proche de l'optimum entier, laissant un petit écart d'intégralité. Lorsque l'écart est petit, la méthode de séparation et évaluation doit explorer moins de nœuds et se termine plus rapidement. L'ajout d'inégalités valides telles que les coupes de Gomory, les inégalités de couverture ou les coupes de clique resserre la formulation et est souvent le moyen le plus efficace d'accélérer un solveur.
Méthodes associées
Sources
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN : 9780471283669Copié.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN : 9780471359432Copié.