Worldlex Wiki Un problème de programmation linéaire en nombres entiers , également appelé optimisation en nombres entiers , est un programme d'optimisation mathématique ou de faisabilité dans lequel certaines ou toutes les variables sont des entiers . Dans de nombreux contextes, le terme désigne la programmation linéaire en nombres entiers (PLNE), où la fonction objectif et les contraintes (autres que les contraintes d'intégrité) sont linéaires .
La programmation linéaire en nombres entiers est NP-complète (la difficulté réside dans la démonstration de son appartenance à la classe NP ). En particulier, le cas particulier de la programmation linéaire en nombres entiers binaires (0-1), où les inconnues sont binaires et où seules les contraintes doivent être respectées, fait partie des 21 problèmes NP-complets de Karp .
Si certaines variables de décision ne sont pas discrètes, le problème est connu sous le nom de problème de programmation linéaire en nombres entiers mixtes .
et un ILP sous forme standard est exprimé comme
où les vecteurs sont et est une matrice. Comme pour les programmes linéaires, les programmes linéaires en nombres entiers (PLNE) qui ne sont pas sous forme standard peuvent être convertis en forme standard en éliminant les inégalités, en introduisant des variables d'écart ( ) et en remplaçant les variables qui ne sont pas contraintes par leur signe par la différence de deux variables contraintes par leur signe.
Exemple
Le graphique de droite illustre le problème suivant.
Les points entiers admissibles sont représentés en rouge, et les lignes pointillées rouges indiquent leur enveloppe convexe , qui est le plus petit polyèdre convexe contenant tous ces points. Les lignes bleues, associées aux axes de coordonnées, définissent le polyèdre de la relaxation linéaire, donné par les inégalités sans la contrainte d'intégralité. L'objectif de l'optimisation est de déplacer la ligne pointillée noire le plus haut possible tout en restant tangente au polyèdre. Les solutions optimales du problème entier sont les points et , qui ont tous deux une valeur objectif de 2. L'optimum unique de la relaxation est , avec une valeur objectif de 2,8. Si la solution de la relaxation est arrondie à l'entier le plus proche, elle n'est pas admissible pour le programme linéaire en nombres entiers (PLNE). Voir la projection sur le simplexe.
Preuve de la dureté NP
Ce qui suit est une réduction de la couverture minimale de sommets à la programmation en nombres entiers qui servira de preuve de la NP-difficulté.
Soit un graphe non orienté. Définissons un programme linéaire comme suit :
Toute solution réalisable du programme linéaire en nombres entiers sera non nulle sur un sous-ensemble de sommets. La première contrainte implique qu'au moins une extrémité de chaque arête est incluse dans ce sous-ensemble. Par conséquent, la solution décrit une couverture de sommets. De plus, étant donné une couverture de sommets C, on peut fixer la somme des coefficients à 1 pour tout sommet et à 0 pour tout autre sommet, ce qui nous donne une solution réalisable du programme linéaire en nombres entiers. Ainsi, nous pouvons conclure que si nous minimisons la somme des coefficients, nous avons également trouvé la couverture de sommets minimale.
Variantes
La programmation linéaire en nombres entiers mixtes ( MILP ) concerne des problèmes dans lesquels seules certaines variables, , sont contraintes d'être des entiers, tandis que d'autres variables peuvent être non entières.
La programmation linéaire binaire (ou programmation en nombres entiers ) traite des problèmes où les variables sont limitées aux valeurs 0 ou 1. Toute variable entière bornée peut être exprimée comme une combinaison de variables binaires . Par exemple, étant donné une variable entière, , la variable peut être exprimée à l'aide de variables binaires :
Applications
Il existe deux raisons principales d'utiliser des variables entières lors de la modélisation de problèmes sous forme de programme linéaire :
- Certaines variables entières représentent des quantités qui ne peuvent être que des entiers. Par exemple, il est impossible de construire 3,7 voitures.
- Les autres variables entières représentent des décisions (par exemple, inclure ou non une arête dans un graphe ) et ne devraient donc prendre que la valeur 0 ou 1.
Ces considérations se présentent fréquemment en pratique et la programmation linéaire en nombres entiers peut donc être utilisée dans de nombreux domaines d'application, dont certains sont brièvement décrits ci-dessous.
planification de la production
La programmation linéaire en nombres entiers mixtes trouve de nombreuses applications dans la production industrielle, notamment la modélisation d'ateliers de production. Un exemple important concerne la planification de la production agricole et consiste à déterminer le rendement de plusieurs cultures partageant des ressources (terre, main-d'œuvre, capital, semences, engrais, etc.). Un objectif possible est de maximiser la production totale sans dépasser les ressources disponibles. Dans certains cas, cela peut être exprimé sous forme de programme linéaire, mais les variables doivent être des entiers.
Planification
Ces problèmes concernent la planification des services et des véhicules dans les réseaux de transport. Par exemple, il peut s'agir d'affecter des bus ou des métros à des itinéraires précis afin de respecter un horaire, et de leur attribuer des conducteurs. Dans ce cas, des variables de décision binaires indiquent si un bus ou un métro est affecté à un itinéraire et si un conducteur est affecté à un train ou une rame de métro spécifique. La technique de programmation binaire (ou programmation par zéro-un) a été appliquée avec succès à la résolution d'un problème de sélection de projets où les projets sont mutuellement exclusifs et/ou technologiquement interdépendants.
Partitionnement territorial
Les problèmes de découpage territorial consistent à diviser une région géographique en districts afin de planifier des opérations, en tenant compte de différents critères et contraintes. Parmi les exigences de ce type de problème figurent la contiguïté, la compacité, l'équilibre ou l'équité, le respect des frontières naturelles et l'homogénéité socio-économique. On retrouve ce type de problème dans des applications telles que le découpage des circonscriptions électorales, scolaires, sanitaires et de gestion des déchets.
Réseaux de télécommunications
L'objectif de ces problèmes est de concevoir un réseau de lignes à installer de manière à satisfaire un ensemble prédéfini d'exigences de communication et à minimiser le coût total du réseau . Cela nécessite d'optimiser à la fois la topologie du réseau et de définir les capacités des différentes lignes. Dans de nombreux cas, les capacités sont contraintes à être des nombres entiers. Généralement, selon la technologie utilisée, des contraintes supplémentaires peuvent être modélisées par des inégalités linéaires à variables entières ou binaires.
Réseaux cellulaires
La planification des fréquences dans les réseaux mobiles GSM consiste à répartir les fréquences disponibles entre les antennes afin de desservir les utilisateurs et de minimiser les interférences entre les antennes. Ce problème peut être formulé comme un programme linéaire en nombres entiers dans lequel des variables binaires indiquent si une fréquence est attribuée à une antenne.
Autres applications
Algorithmes
La méthode naïve pour résoudre un programme linéaire en nombres entiers (PLNE) consiste simplement à supprimer la contrainte d'entierité de x , à résoudre le programme linéaire correspondant (appelé relaxation linéaire du PLNE), puis à arrondir les éléments de la solution à la valeur de cette relaxation. Cependant, non seulement cette solution peut ne pas être optimale, mais elle peut même être irréalisable ; autrement dit, elle peut enfreindre une contrainte.
Utilisation de l'unimodularité totale
Bien que la solution de la relaxation linéaire ne soit généralement pas garantie d'être entière, si le programme linéaire en nombres entiers (PLNE) est de la forme où et ont tous leurs coefficients entiers et est totalement unimodulaire , alors toute solution de base admissible est entière. Par conséquent, la solution renvoyée par l' algorithme du simplexe est garantie d'être entière. Pour montrer que toute solution de base admissible est entière, soit une solution de base admissible arbitraire . Puisque est admissible, nous savons que . Soient les éléments correspondant aux colonnes de la base de la solution de base . Par définition d'une base, il existe une sous-matrice carrée de dont les colonnes sont linéairement indépendantes telle que .
Puisque les colonnes de sont linéairement indépendantes et que est carrée, est non singulière, et donc, par hypothèse, est unimodulaire et donc . De plus, puisque est non singulière, elle est inversible et donc . Par définition, . Ici, désigne l' adjoint de et est entier car est entier. Par conséquent, . Ainsi, si la matrice d'un programme linéaire en nombres entiers (PLNE) est totalement unimodulaire, plutôt que d'utiliser un algorithme de PLNE, la méthode du simplexe peut être utilisée pour résoudre la relaxation linéaire et la solution sera entière.
Algorithmes exacts
Lorsque la matrice n'est pas totalement unimodulaire, divers algorithmes permettent de résoudre exactement les programmes linéaires en nombres entiers. Parmi ces algorithmes, on trouve les méthodes des plans sécants , qui consistent à résoudre la relaxation linéaire puis à ajouter des contraintes linéaires afin de contraindre la solution à être entière sans exclure aucun point admissible entier.
Une autre catégorie d'algorithmes regroupe les variantes de la méthode de séparation et d'évaluation . Par exemple, la méthode de séparation et d'évaluation combinée combine les méthodes de séparation et d'évaluation et de plans de coupe. Les algorithmes de séparation et d'évaluation présentent plusieurs avantages par rapport aux algorithmes utilisant uniquement des plans de coupe. L'un d'eux est la possibilité d'interrompre l'exécution prématurément ; dès lors qu'au moins une solution entière a été trouvée, une solution réalisable, bien que non nécessairement optimale, peut être renvoyée. De plus, les solutions des relaxations linéaires permettent d'estimer, dans le pire des cas, l'écart à l'optimalité de la solution obtenue. Enfin, les méthodes de séparation et d'évaluation peuvent fournir plusieurs solutions optimales.