Programmation en nombres entiers

La programmation en nombres entiers (PNE; en anglais integer programming, IP) est une branche de l'optimisation mathématique qui étudie les problèmes où certaines ou toutes les variables sont contraintes à prendre des valeurs entières.

Le cas particulier le plus étudié est la programmation linéaire en nombres entiers (PLNE; en anglais integer linear programming, ILP), où la fonction objectif et les contraintes sont linéaires. Contrairement à la programmation linéaire, où les variables peuvent prendre n'importe quelle valeur réelle, la contrainte d'intégrité rend les problèmes de PNE beaucoup plus difficiles à résoudre.

La programmation en nombres entiers trouve de nombreuses applications en économie, en logistique, en planification de la production et dans d'autres domaines où les variables sont par nature discrètes (par exemple, le nombre d'unités produites ou le nombre d'employés).

Définition et terminologie

Un problème général de programmation linéaire en nombres entiers peut s'écrire sous la forme suivante :

Trouver un vecteur $x$ qui :

maximise (ou minimise) $c^{T}x$

sous les contraintes :

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (toutes les composantes du vecteur $x$ sont des entiers)

où $x$ est le vecteur des variables, $c$ et $b$ sont des vecteurs, et $A$ est la matrice des coefficients.

Selon les contraintes sur les variables, on distingue les types de problèmes suivants :

• Programmation en nombres entiers purs : toutes les variables doivent être des entiers.
• Programmation en nombres entiers mixtes (en anglais mixed-integer programming, MIP) : seule une partie des variables doit être entière.
• Programmation en 0-1 (ou binaire) : les variables ne peuvent prendre que les valeurs 0 ou 1, ce qui permet de modéliser des décisions logiques de type « oui/non ».

Propriétés clés et complexité

Complexité algorithmique

Le problème de la programmation linéaire en nombres entiers est, en général, NP-difficile. Cela signifie qu'il n'existe aucun algorithme connu capable de trouver une solution optimale exacte pour un problème de PNE arbitraire en temps polynomial. La complexité est due à la nature combinatoire du problème, car le nombre de solutions entières possibles peut croître de manière exponentielle avec le nombre de variables.

Lien avec la programmation linéaire (relaxation PL)

Pour tout problème de PNE, on peut formuler sa relaxation linéaire — un problème de programmation linéaire (PL) dans lequel la contrainte d'intégrité des variables est omise. La solution de la relaxation PL possède deux propriétés importantes :

1. On peut la trouver beaucoup plus rapidement (en temps polynomial).
2. La valeur optimale de la fonction objectif de la relaxation PL fournit une borne (une borne supérieure pour un problème de maximisation et une borne inférieure pour un problème de minimisation) pour la valeur optimale du problème en nombres entiers original.

Cependant, l'arrondi simple de la solution fractionnaire de la relaxation PL aux entiers les plus proches ne mène généralement pas à une solution optimale, ni même réalisable, pour le problème en nombres entiers.

Propriété d'unimodularité totale

Il existe une classe importante de problèmes de PLNE qui se résolvent aussi facilement que leurs relaxations PL. Ce sont des problèmes où la matrice des contraintes $A$ est totalement unimodulaire (c'est-à-dire que le déterminant de toute sous-matrice carrée est égal à 0, +1 ou −1). Si la matrice $A$ est totalement unimodulaire et que le vecteur $b$ est entier, alors tous les sommets du polyèdre des solutions réalisables de la relaxation PL seront automatiquement des entiers. Par conséquent, la solution trouvée par la méthode du simplexe sera entière. Des exemples de tels problèmes incluent le problème du transport et le problème d'affectation.

Méthodes de résolution

Pour résoudre les problèmes généraux de PNE qui ne possèdent pas la propriété d'unimodularité totale, des méthodes exactes basées sur des idées d'énumération implicite ont été développées.

• Méthode de séparation et évaluation (en anglais Branch and Bound) — la principale méthode exacte, basée sur une division systématique de l'ensemble des solutions réalisables en sous-ensembles (séparation) et l'élimination des sous-ensembles qui ne peuvent manifestement pas contenir de solution optimale. La relaxation PL est utilisée pour évaluer le potentiel des sous-ensembles.

• Méthode des plans sécants (méthode de Gomory ; en anglais Cutting Plane Method) — une approche itérative qui ajoute successivement de nouvelles contraintes linéaires (« coupes ») au problème. Ces coupes « coupent » les solutions fractionnaires de la relaxation PL sans éliminer aucune solution entière réalisable, rapprochant progressivement la région réalisable de la relaxation PL de l'enveloppe convexe des solutions entières.

Les solveurs modernes utilisent généralement des algorithmes hybrides, tels que la méthode de séparation et coupe (en anglais Branch and Cut), qui combine les avantages des deux approches.

Exemples et domaines d'application

La programmation en nombres entiers permet de modéliser de nombreux problèmes classiques d'optimisation combinatoire.

• Problème du sac à dos : un problème classique de programmation en 0-1 où l'on doit sélectionner un ensemble d'objets ayant la plus grande valeur totale, sans dépasser une contrainte de poids total.
• Problème du voyageur de commerce : le problème de trouver le plus court chemin qui passe par un ensemble donné de villes. Il peut être formulé comme un problème de programmation en nombres entiers, où les variables indiquent si une arête du graphe est incluse dans le chemin final.

Grâce à sa flexibilité, la PNE est l'un des outils les plus demandés en recherche opérationnelle et trouve des applications dans des domaines tels que :

• Logistique et gestion de la chaîne d'approvisionnement : optimisation des itinéraires de transport, localisation des entrepôts, gestion des stocks.
• Planification de la production : élaboration des plannings de production, allocation des ressources, ordonnancement des machines.
• Finance et économie : constitution de portefeuilles d'investissement, budgétisation des investissements.
• Télécommunications et énergie : conception de réseaux de communication, planification de la production des unités d'énergie.

Voir aussi

• Programmation linéaire
• Méthode de séparation et évaluation