Skip to content
Retour aux résultats

Programmation en nombres entiers déterministe — Optimisation exacte avec variables de décision entières

Introduite par
Ralph E. Gomory
Année
1958
Type
Exact combinatorial optimization
Famille
Simulation / optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Programmation en Nombres Entiers Déterministe (PNED) est une approche d'optimisation mathématique qui trouve la meilleure solution à des problèmes où certaines ou toutes les variables de décision doivent prendre des valeurs entières, étant donné des données d'objectif et de contrainte entièrement connues (déterministes).

C'est la forme classique, non stochastique, de la programmation en nombres entiers, fondamentale pour la recherche opérationnelle et l'optimisation combinatoire depuis la fin des années 1950.

L’intuition derrière la méthode

De nombreuses décisions du monde réel sont intrinsèquement discrètes : on ouvre une installation ou on ne l'ouvre pas ; on assigne un travailleur à un poste ou on ne l'assigne pas. Les méthodes d'optimisation continues ne peuvent pas imposer ces exigences de nombres entiers. La Programmation en Nombres Entiers Déterministe gère cela en restreignant les variables à des entiers tandis que tous les paramètres du problème — coûts, capacités, demandes — sont connus avec certitude. Le résultat est une solution exacte, prouvablement optimale dans le cadre de cette hypothèse de certitude, ce qui en fait la formulation de référence par rapport à laquelle les variantes stochastiques et robustes sont comparées.

Histoire

La programmation en nombres entiers a émergé de la programmation linéaire à la fin des années 1950. L'algorithme de plans coupants de Ralph Gomory en 1958 fut la première méthode exacte systématique. Concurremment à la séparation et évaluation (Land et Doig, 1960), ces approches ont défini le domaine. L'adjectif 'déterministe' distingue la formulation classique de la programmation en nombres entiers stochastique (Birge et Louveaux, 1997) et est devenu une terminologie standard à mesure que les variantes tenant compte de l'incertitude proliféraient.

Quand l’utiliser

Utiliser la Programmation en Nombres Entiers Déterministe lorsque : (1) les variables de décision sont intrinsèquement discrètes (affectation, ordonnancement, localisation d'installations, problème du sac à dos, conception de réseaux) ; (2) tous les paramètres du problème sont connus avec certitude ou peuvent être estimés de manière fiable comme des valeurs ponctuelles ; (3) une solution optimale exacte est requise plutôt qu'une approximation heuristique. NE PAS utiliser lorsque : les paramètres sont incertains ou dépendants de scénarios (utiliser la programmation en nombres entiers stochastique ou robuste à la place) ; l'échelle du problème est si grande que la séparation et évaluation est calculatoirement intraitable et que des heuristiques sont acceptables ; les variables sont véritablement continues (utiliser la PL) ; ou plusieurs objectifs conflictuels doivent être équilibrés simultanément (utiliser la programmation en nombres entiers multi-objectifs).

Limites et points d’attention

  • Suppose que tous les paramètres du problème sont connus exactement — l'incertitude du monde réel est ignorée par conception.
  • NP-difficile en général ; le temps de résolution dans le pire des cas croît exponentiellement avec la taille du problème.
  • Les grands problèmes combinatoires peuvent nécessiter des heures ou des jours de calcul même avec des solveurs modernes.
  • La qualité de la formulation du modèle (resserrement des contraintes, rupture de symétrie) affecte fortement le temps de résolution.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Garantit une solution prouvablement optimale dans le cadre des hypothèses du modèle déterministe.
  • Gère naturellement les structures de décision discrètes et combinatoires que les méthodes continues ne peuvent pas gérer.
  • Supportée par des solveurs commerciaux et open-source matures et très efficaces (CPLEX, Gurobi, SCIP).
  • Fournit un certificat d'écart d'optimalité, permettant une terminaison anticipée raisonnée pour les grandes instances.
  • Sert de formulation de référence (gold standard) pour comparer les variantes heuristiques et stochastiques.

Applications

  • Planification et ordonnancement de production avec des ressources machines ou humaines discrètes
  • Localisation d'installations : décider quels entrepôts ou usines ouvrir
  • Routage de véhicules et planification d'équipage dans les transports et la logistique
  • Budgétisation des capitaux : sélection d'un portefeuille de projets d'investissement indivisibles
  • Conception de réseaux de télécommunications avec des coûts fixes d'établissement de liens
  • Établissement des plannings du personnel de santé et ordonnancement des blocs opératoires

Comment ça marche

Comment ça marche

1

Définir le modèle d'optimisation : une fonction objectif à minimiser (ou maximiser) comme une combinaison linéaire de variables de décision entières, soumise à un ensemble de contraintes linéaires inégales ou égales. Tous les coefficients (c, A, b) sont fixes et connus — c'est ce qui rend la formulation déterministe. Les variables binaires (0/1) sont un cas particulier pour les décisions oui/non.

Formule
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

Résoudre la relaxation linéaire (LP), qui autorise temporairement les variables à prendre des valeurs continues. Cela donne une borne inférieure sur l'objectif entier optimal. Si la solution de la relaxation LP est déjà à valeurs entières, elle est optimale pour la PN; sinon, le branchement commence.

Formule
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

Choisir une variable fractionnaire de la solution de la relaxation LP et diviser la région réalisable en ajoutant une contrainte de plancher (x_j <= valeur entière inférieure) sur une branche et une contrainte de plafond (x_j >= valeur entière supérieure) sur l'autre, générant deux sous-problèmes à résoudre récursivement.

Formule
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

Résoudre la relaxation LP de chaque sous-problème pour obtenir une borne. Si la borne d'un nœud est pire que la meilleure solution entière connue (incumbent), élaguer ce nœud. Si le sous-problème produit une solution entière réalisable meilleure que l'incumbent, mettre à jour l'incumbent. Le processus forme un arbre de recherche par séparation et évaluation (branch-and-bound).

Formule
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

Les méthodes de plans coupants — notamment les coupes de Gomory — dérivent des inégalités linéaires supplémentaires du tableau LP qui sont satisfaites par toutes les solutions entières mais violées par la solution LP fractionnaire actuelle. L'ajout de ces coupes resserre la relaxation LP et réduit le branchement. Les solveurs modernes combinent la séparation et évaluation avec les coupes dans un cadre de branchement et coupe (branch-and-cut).

Formule
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

L'algorithme se termine lorsque tous les nœuds ouverts sont élagués ou produisent des solutions entières. L'incumbent à la fin est la solution entière prouvablement optimale. Les solveurs rapportent également un écart (gap) entre la meilleure borne et l'incumbent, qui peut être utilisé comme critère d'arrêt pour les grands problèmes.

Formule
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

Pièges courants

  • Traiter les paramètres incertains comme des estimations ponctuelles déterministes peut conduire à des solutions qui fonctionnent mal en pratique — valider cette hypothèse avant d'appliquer la PNED.
  • Des relaxations LP faibles (grands écarts d'intégralité) conduisent à d'énormes arbres de séparation et évaluation ; investir dans des inégalités valides et la reformulation avant de passer à l'échelle.
  • L'explosion des variables binaires due aux formulations big-M peut déstabiliser numériquement la relaxation LP ; préférer des reformulations de contraintes plus serrées.
  • Confondre la faisabilité avec l'optimalité lors de l'utilisation d'une tolérance d'écart non nulle — toujours rapporter l'écart aux côtés de la valeur objectif.
  • Ignorer la symétrie dans les modèles (par exemple, machines ou travailleurs identiques) provoque un branchement redondant ; ajouter des contraintes de rupture de symétrie.

Questions fréquentes

Qu'est-ce qui distingue la programmation en nombres entiers déterministe de la programmation en nombres entiers stochastique ?

En PN déterministe, tous les paramètres de l'objectif et des contraintes sont fixes et connus. La PN stochastique modélise explicitement les paramètres incertains via des distributions de probabilité ou des scénarios, produisant des solutions qui sont robustes ou optimales en espérance sur ces scénarios. La PN déterministe est plus simple et plus rapide à résoudre mais ignore l'incertitude.

La programmation binaire est-elle un cas particulier de la programmation en nombres entiers ?

Oui. La programmation binaire (0-1) restreint chaque variable de décision à {0, 1}. C'est le cas particulier le plus courant, utilisé pour les décisions oui/non telles que l'ouverture d'une installation, la sélection d'un projet ou l'affectation d'un travailleur. La programmation entière générale autorise toute valeur entière non négative.

Quand devrais-je passer de la PN déterministe à une méthode heuristique ?

Lorsque l'arbre de séparation et évaluation est trop grand pour être exploré dans un délai acceptable et que l'écart d'optimalité d'une bonne heuristique (algorithme génétique, recuit simulé, recherche dans un grand voisinage) est tolérable pour l'application. Rapporter et justifier l'écart lors de la déviation de l'optimisation exacte.

La PN déterministe peut-elle gérer des objectifs ou des contraintes non linéaires ?

La PN déterministe classique suppose la linéarité (programmation linéaire en nombres entiers). La programmation non linéaire en nombres entiers existe mais est considérablement plus difficile ; de nombreuses formes non linéaires peuvent être linéarisées via des variables binaires auxiliaires et des reformulations big-M. La programmation quadratique en nombres entiers (QIP) est directement supportée par certains solveurs modernes.

Quel solveur devrais-je utiliser pour la PN déterministe en pratique ?

Commercial : Gurobi ou IBM CPLEX pour les meilleures performances. Académique/open-source : SCIP, CBC (via COIN-OR), ou HiGHS. Tous implémentent le branchement et coupe avec prétraitement automatique. Pour les utilisateurs Python, PuLP, Pyomo, ou scipy.optimize.milp fournissent des interfaces de modélisation pratiques.

Méthodes associées

Sources

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    Ouvrir la référence DOI
    Copié.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN : 9780471283669
    Copié.