Programmation linéaire

La programmation linéaire ( LP ), également appelée optimisation linéaire , est une méthode permettant d'obtenir le meilleur résultat (comme le profit maximal ou le coût le plus bas) dans un modèle mathématique dont les exigences et l'objectif sont représentés par des relations linéaires . La programmation linéaire est un cas particulier de programmation mathématique (également appelée optimisation mathématique ).

Plus formellement, la programmation linéaire est une technique d' optimisation d'une fonction objective linéaire , soumise à des contraintes d'égalité linéaire et d'inégalité linéaire . Sa région réalisable est un polytope convexe , qui est un ensemble défini comme l' intersection d'un nombre fini de demi-espaces , chacun étant défini par une inégalité linéaire. Sa fonction objective est une fonction affine (linéaire) à valeurs réelles définie sur ce polytope. Un algorithme de programmation linéaire trouve un point dans le polytope où cette fonction a la plus grande (ou la plus petite) valeur si un tel point existe.

Les programmes linéaires sont des problèmes qui peuvent être exprimés sous forme standard comme

Ici, les composantes de sont les variables à déterminer, et sont des vecteurs donnés , et est une matrice donnée . La fonction dont la valeur doit être maximisée ( dans ce cas) est appelée fonction objective . Les contraintes et spécifient un polytope convexe sur lequel la fonction objective doit être optimisée.

La programmation linéaire peut être appliquée à divers domaines d'étude. Elle est largement utilisée en mathématiques et, dans une moindre mesure, en affaires, en économie et dans certains problèmes d'ingénierie. Il existe un lien étroit entre les programmes linéaires, les équations propres, le modèle d'équilibre général de John von Neumann et les modèles d'équilibre structurel (voir le programme linéaire dual pour plus de détails). Les industries qui utilisent des modèles de programmation linéaire comprennent les transports, l'énergie, les télécommunications et la fabrication. Elle s'est avérée utile pour modéliser divers types de problèmes de planification , de routage , d'ordonnancement , d'affectation et de conception.

Le problème de la résolution d'un système d'inéquations linéaires remonte au moins à Fourier , qui en 1827 publia une méthode pour les résoudre, et qui donna son nom à la méthode d' élimination de Fourier-Motzkin .

À la fin des années 1930, le mathématicien soviétique Leonid Kantorovich et l'économiste américain Wassily Leontief se sont penchés indépendamment sur les applications pratiques de la programmation linéaire. Kantorovich s'est concentré sur les calendriers de fabrication, tandis que Leontief s'est penché sur les applications économiques. Leurs travaux révolutionnaires ont été largement négligés pendant des décennies.

Le tournant s'est produit pendant la Seconde Guerre mondiale, lorsque la programmation linéaire est devenue un outil essentiel. Elle a été largement utilisée pour relever des défis complexes en temps de guerre, notamment la logistique des transports, la planification et l'allocation des ressources. La programmation linéaire s'est avérée inestimable pour optimiser ces processus tout en tenant compte de contraintes critiques telles que les coûts et la disponibilité des ressources.

Malgré son obscurité initiale, les succès remportés pendant la guerre ont propulsé la programmation linéaire sous les projecteurs. Après la Seconde Guerre mondiale, la méthode a acquis une large reconnaissance et est devenue une pierre angulaire dans divers domaines, de la recherche opérationnelle à l'économie. Les contributions négligées de Kantorovich et Leontief à la fin des années 1930 sont finalement devenues fondamentales pour l'acceptation et l'utilisation plus larges de la programmation linéaire dans l'optimisation des processus de prise de décision.

Les travaux de Kantorovitch furent initialement négligés en URSS . À peu près à la même époque que Kantorovitch, l'économiste américano-néerlandais TC Koopmans formula des problèmes économiques classiques sous forme de programmes linéaires. Kantorovitch et Koopmans se partagèrent plus tard le prix Nobel d'économie en 1975. [ 4 En 1941, Frank Lauren Hitchcock formula également des problèmes de transport sous forme de programmes linéaires et donna une solution très similaire à la méthode du simplexe ultérieure . Hitchcock était décédé en 1957 et le prix Nobel n'est pas décerné à titre posthume.

De 1946 à 1947, George B. Dantzig a développé de manière indépendante une formulation générale de programmation linéaire à utiliser pour les problèmes de planification dans l'US Air Force. En 1947, Dantzig a également inventé la méthode du simplexe qui, pour la première fois, a abordé efficacement le problème de programmation linéaire dans la plupart des cas. Lorsque Dantzig a organisé une réunion avec John von Neumann pour discuter de sa méthode du simplexe, von Neumann a immédiatement conjecturé la théorie de la dualité en réalisant que le problème sur lequel il avait travaillé en théorie des jeux était équivalent. Dantzig a fourni une preuve formelle dans un rapport non publié « Un théorème sur les inégalités linéaires » le 5 janvier 1948. Le travail de Dantzig a été rendu public en 1951. Dans les années d'après-guerre, de nombreuses industries l'ont appliqué dans leur planification quotidienne.

L'exemple original de Dantzig consistait à trouver la meilleure affectation de 70 personnes à 70 emplois. La puissance de calcul requise pour tester toutes les permutations afin de sélectionner la meilleure affectation est énorme ; le nombre de configurations possibles dépasse le nombre de particules dans l' univers observable . Cependant, il suffit d'un instant pour trouver la solution optimale en posant le problème sous la forme d'un programme linéaire et en appliquant l' algorithme du simplexe . La théorie sur laquelle repose la programmation linéaire réduit considérablement le nombre de solutions possibles à vérifier.

Le problème de programmation linéaire a été démontré pour la première fois comme pouvant être résolu en temps polynomial par Leonid Khachiyan en 1979, mais une avancée théorique et pratique plus importante dans le domaine a eu lieu en 1984 lorsque Narendra Karmarkar a introduit une nouvelle méthode du point intérieur pour résoudre les problèmes de programmation linéaire.

La programmation linéaire est un domaine d'optimisation largement utilisé pour plusieurs raisons. De nombreux problèmes pratiques de la recherche opérationnelle peuvent être exprimés sous forme de problèmes de programmation linéaire. Certains cas particuliers de programmation linéaire, tels que les problèmes de flux de réseau et les problèmes de flux multi-produits , sont considérés comme suffisamment importants pour faire l'objet de nombreuses recherches sur des algorithmes spécialisés. Un certain nombre d'algorithmes pour d'autres types de problèmes d'optimisation fonctionnent en résolvant les problèmes de programmation linéaire en tant que sous-problèmes. Historiquement, les idées issues de la programmation linéaire ont inspiré de nombreux concepts centraux de la théorie de l'optimisation, tels que la dualité, la décomposition et l'importance de la convexité et de ses généralisations. De même, la programmation linéaire a été largement utilisée dans la formation précoce de la microéconomie , et elle est actuellement utilisée dans la gestion des entreprises, comme la planification, la production, le transport et la technologie. Bien que les problèmes de gestion modernes soient en constante évolution, la plupart des entreprises souhaitent maximiser les profits et minimiser les coûts avec des ressources limitées. Google utilise également la programmation linéaire pour stabiliser les vidéos YouTube.

La forme standard est la forme habituelle et la plus intuitive pour décrire un problème de programmation linéaire. Elle se compose des trois parties suivantes :

• Une fonction linéaire (ou affine) à maximiser

par exemple

• Problème de contraintes de la forme suivante

par exemple

• Variables non négatives

par exemple

Le problème est généralement exprimé sous forme matricielle , et devient alors :

D'autres formes, telles que les problèmes de minimisation, les problèmes avec contraintes sur les formes alternatives et les problèmes impliquant des variables négatives peuvent toujours être réécrits dans un problème équivalent sous forme standard.

Supposons qu'un agriculteur possède une parcelle de terre agricole, disons L hectares , à planter soit avec du blé, soit avec de l'orge, soit avec une combinaison des deux. L'agriculteur dispose de F kilogrammes d'engrais et de P kilogrammes de pesticide. Chaque hectare de blé nécessite F ₁ kilogramme d'engrais et P ₁ kilogramme de pesticide, tandis que chaque hectare d'orge nécessite F ₂ kilogrammes d'engrais et P ₂ kilogrammes de pesticide. Soit S ₁ le prix de vente du blé et S ₂ le prix de vente de l'orge, par hectare. Si nous désignons la surface de terre plantée en blé et en orge par x ₁ et x ₂ respectivement, alors le profit peut être maximisé en choisissant des valeurs optimales pour x ₁ et x ₂ . Ce problème peut être exprimé par le problème de programmation linéaire suivant sous la forme standard :

Sous forme matricielle cela devient :

maximiser

sujet à

Les problèmes de programmation linéaire peuvent être convertis en une forme augmentée afin d'appliquer la forme courante de l' algorithme du simplexe . Cette forme introduit des variables d'écart non négatives pour remplacer les inégalités par des égalités dans les contraintes. Les problèmes peuvent alors être écrits sous la forme de matrice en blocs suivante :

Maximiser :

où sont les variables de mou nouvellement introduites, sont les variables de décision et est la variable à maximiser.

L'exemple ci-dessus est converti dans la forme augmentée suivante :

où sont les variables d'écart (non négatives), représentant dans cet exemple la surface inutilisée, la quantité d'engrais non utilisée et la quantité de pesticide non utilisée.

Sous forme matricielle cela devient :

Maximiser :

Tout problème de programmation linéaire, appelé problème primal , peut être transformé en un problème dual , qui fournit une borne supérieure à la valeur optimale du problème primal. Sous forme matricielle, nous pouvons exprimer le problème primal comme suit :

Maximiser c ^T x sous réserve de A x ≤ b , x ≥ 0 ;

avec le problème dual symétrique correspondant ,

Minimiser b ^T y sous réserve que A ^T y ≥ c , y ≥ 0.

Une formulation primaire alternative est :

Maximiser c ^T x sous réserve que A x ≤ b ;

avec le problème dual asymétrique correspondant ,

Minimiser b ^T y sous réserve de A ^T y = c , y ≥ 0.

La théorie de la dualité repose sur deux idées fondamentales. L'une d'elles est le fait que (pour le dual symétrique) le dual d'un programme linéaire dual est le programme linéaire primal d'origine. De plus, chaque solution réalisable pour un programme linéaire donne une limite à la valeur optimale de la fonction objective de son dual. Le théorème de dualité faible stipule que la valeur de la fonction objective du dual à toute solution réalisable est toujours supérieure ou égale à la valeur de la fonction objective du primal à toute solution réalisable. Le théorème de dualité forte stipule que si le primal a une solution optimale, x ^* , alors le dual a également une solution optimale, y ^* , et c ^T x ^* = b ^T y ^* .

Un programme linéaire peut aussi être illimité ou irréalisable. La théorie de la dualité nous dit que si le programme primal est illimité, alors le programme dual est irréalisable par le théorème de dualité faible. De même, si le programme dual est illimité, alors le programme primal doit être irréalisable. Cependant, il est possible que le programme dual et le programme primal soient tous deux irréalisables. Voir programme linéaire dual pour plus de détails et plusieurs autres exemples.

Un LP de recouvrement est un programme linéaire de la forme :

Réduire : b ^T y ,

sous réserve de : A ^T y ≥ c , y ≥ 0 ,

tel que la matrice A et les vecteurs b et c soient non négatifs.

Le dual d'un LP de recouvrement est un LP d'emballage , un programme linéaire de la forme :

Maximiser : c ^T x ,

sous réserve de : A x ≤ b , x ≥ 0 ,

tel que la matrice A et les vecteurs b et c soient non négatifs.

Les LP de recouvrement et d'empaquetage apparaissent généralement comme une relaxation de programmation linéaire d'un problème combinatoire et sont importantes dans l'étude des algorithmes d'approximation . Par exemple, les relaxations LP du problème d'empaquetage d'ensemble , du problème d'ensemble indépendant et du problème de mise en correspondance sont des LP d'empaquetage. Les relaxations LP du problème de recouvrement d'ensemble , du problème de recouvrement de sommets et du problème d'ensemble dominant sont également des LP de recouvrement.

La recherche d'une coloration fractionnaire d'un graphe est un autre exemple de PL de recouvrement. Dans ce cas, il existe une contrainte pour chaque sommet du graphe et une variable pour chaque ensemble indépendant du graphe.

Il est possible d'obtenir une solution optimale au dual lorsque seule une solution optimale au primal est connue en utilisant le théorème de la marge complémentaire. Le théorème stipule :

Supposons que x = ( x ₁ , x ₂ , ... , x _n ) est réalisable primal et que y = ( y ₁ , y ₂ , ... , y _m ) est réalisable dual. Soit ( w ₁ , w ₂ , ..., w _m ) les variables d'écart primal correspondantes, et soit ( z ₁ , z ₂ , ... , z _n ) les variables d'écart dual correspondantes. Alors x et y sont optimaux pour leurs problèmes respectifs si et seulement si

• x _j z _j = 0, pour j = 1, 2, ... , n , et
• w _i y _i = 0, pour i = 1, 2, ... , m .

Ainsi, si la i -ième variable d'écart de la primitive n'est pas nulle, alors la i -ième variable du dual est égale à zéro. De même, si la j -ième variable d'écart de la primitive n'est pas nulle, alors la j -ième variable du primal est égale à zéro.

Cette condition nécessaire à l'optimalité traduit un principe économique assez simple. Dans sa forme standard (lors de la maximisation), s'il existe une marge de manœuvre dans une ressource primaire contrainte (c'est-à-dire s'il existe des « restes »), alors les quantités supplémentaires de cette ressource ne doivent avoir aucune valeur. De même, s'il existe une marge de manœuvre dans la contrainte de non-négativité du prix double (c'est-à-dire si le prix n'est pas nul, alors il doit y avoir des approvisionnements rares (pas de « restes »).

Géométriquement, les contraintes linéaires définissent la région réalisable , qui est un polytope convexe . Une fonction linéaire est une fonction convexe , ce qui implique que tout minimum local est un minimum global ; de même, une fonction linéaire est une fonction concave , ce qui implique que tout maximum local est un maximum global .

Une solution optimale n'est pas nécessairement possible, pour deux raisons. D'abord, si les contraintes sont incohérentes, alors aucune solution réalisable n'existe : par exemple, les contraintes x ≥ 2 et x ≤ 1 ne peuvent pas être satisfaites conjointement ; dans ce cas, on dit que le LP est infaisable . Ensuite, lorsque le polytope est non borné dans la direction du gradient de la fonction objective (où le gradient de la fonction objective est le vecteur des coefficients de la fonction objective), alors aucune valeur optimale n'est atteinte car il est toujours possible de faire mieux que n'importe quelle valeur finie de la fonction objective.

Autrement, si une solution réalisable existe et si l'ensemble de contraintes est borné, alors la valeur optimale est toujours atteinte sur la frontière de l'ensemble de contraintes, par le principe du maximum pour les fonctions convexes (alternativement, par le principe du minimum pour les fonctions concaves ) puisque les fonctions linéaires sont à la fois convexes et concaves. Cependant, certains problèmes ont des solutions optimales distinctes ; par exemple, le problème de trouver une solution réalisable à un système d'inéquations linéaires est un problème de programmation linéaire dans lequel la fonction objective est la fonction nulle (c'est-à-dire la fonction constante prenant la valeur zéro partout). Pour ce problème de faisabilité avec la fonction nulle pour sa fonction objective, s'il y a deux solutions distinctes, alors chaque combinaison convexe des solutions est une solution.

Les sommets du polytope sont également appelés solutions réalisables de base . La raison de ce choix de nom est la suivante. Soit d le nombre de variables. Alors le théorème fondamental des inégalités linéaires implique (pour les problèmes réalisables) que pour chaque sommet x ^* de la région réalisable LP, il existe un ensemble de d (ou moins) contraintes d'inégalité du LP telles que, lorsque nous traitons ces d contraintes comme des égalités, la solution unique est x ^* . Ainsi, nous pouvons étudier ces sommets en examinant certains sous-ensembles de l'ensemble de toutes les contraintes (un ensemble discret), plutôt que le continuum des solutions LP. Ce principe sous-tend l' algorithme du simplexe pour résoudre les programmes linéaires.

L' algorithme du simplexe , développé par George Dantzig en 1947, résout les problèmes LP en construisant une solution réalisable à un sommet du polytope , puis en parcourant un chemin sur les bords du polytope jusqu'à des sommets avec des valeurs non décroissantes de la fonction objective jusqu'à ce qu'un optimum soit atteint à coup sûr. Dans de nombreux problèmes pratiques, un « blocage » se produit : de nombreux pivots sont effectués sans augmentation de la fonction objective. Dans de rares problèmes pratiques, les versions habituelles de l'algorithme du simplexe peuvent en fait « faire des cycles ». Pour éviter les cycles, les chercheurs ont développé de nouvelles règles de pivotement.

En pratique, l' algorithme du simplexe est assez efficace et permet de trouver l'optimum global si certaines précautions contre le cyclage sont prises. Il a été prouvé que l'algorithme du simplexe résout efficacement les problèmes « aléatoires », c'est-à-dire en un nombre cubique d'étapes, ce qui est similaire à son comportement sur les problèmes pratiques.

Cependant, l'algorithme du simplexe a un comportement médiocre dans le pire des cas : Klee et Minty ont construit une famille de problèmes de programmation linéaire pour lesquels la méthode du simplexe prend un nombre d'étapes exponentielles dans la taille du problème. En fait, pendant un certain temps, on ne savait pas si le problème de programmation linéaire était résoluble en temps polynomial , c'est-à-dire de classe de complexité P.

Comme l'algorithme simplex de Dantzig, l' algorithme criss-cross est un algorithme d'échange de base qui pivote entre les bases. Cependant, l'algorithme criss-cross n'a pas besoin de maintenir la faisabilité, mais peut plutôt pivoter d'une base faisable vers une base infaisable. L'algorithme criss-cross n'a pas de complexité temporelle polynomiale pour la programmation linéaire. Les deux algorithmes visitent tous les coins ^2D d'un cube (perturbé) en dimension D , le cube de Klee-Minty , dans le pire des cas .

Contrairement à l'algorithme du simplexe, qui trouve une solution optimale en parcourant les arêtes entre les sommets d'un ensemble polyédrique, les méthodes de points intérieurs se déplacent à l'intérieur de la région réalisable.

Il s'agit du premier algorithme polynomial du pire cas jamais trouvé pour la programmation linéaire. Pour résoudre un problème qui a n variables et peut être codé en L bits d'entrée, cet algorithme s'exécute en temps. Leonid Khachiyan a résolu ce problème de complexité de longue date en 1979 avec l'introduction de la méthode de l'ellipsoïde . L'analyse de convergence a des prédécesseurs (en nombres réels), notamment les méthodes itératives développées par Naum Z. Shor et les algorithmes d'approximation d'Arkadi Nemirovski et D. Yudin.

L'algorithme de Khachiyan a joué un rôle déterminant dans l'établissement de la solvabilité en temps polynomial des programmes linéaires. L'algorithme n'a pas constitué une avancée informatique majeure, car la méthode du simplexe est plus efficace pour tous les programmes linéaires, à l'exception des familles spécialement construites.

Cependant, l'algorithme de Khachiyan a inspiré de nouvelles pistes de recherche en programmation linéaire. En 1984, N. Karmarkar a proposé une méthode projective pour la programmation linéaire. L'algorithme de Karmarkar a amélioré la borne polynomiale du pire cas de Khachiyan (donnant ). Karmarkar a affirmé que son algorithme était beaucoup plus rapide en LP pratique que la méthode du simplexe, une affirmation qui a suscité un grand intérêt pour les méthodes du point intérieur. Depuis la découverte de Karmarkar, de nombreuses méthodes du point intérieur ont été proposées et analysées.

En 1987, Vaidya a proposé un algorithme qui s'exécute dans le temps.

En 1989, Vaidya a développé un algorithme qui s'exécute dans le temps. Formellement parlant, l'algorithme prend des opérations arithmétiques dans le pire des cas, où est le nombre de contraintes, est le nombre de variables et est le nombre de bits.

En 2015, Lee et Sidford ont montré que la programmation linéaire peut être résolue en temps, où désigne la notation O douce , et représente le nombre d'éléments non nuls, et elle reste prise dans le pire des cas.

En 2019, Cohen, Lee et Song ont amélioré le temps d'exécution en temps, est l'exposant de la multiplication matricielle et est le double exposant de la multiplication matricielle . est (approximativement) défini comme étant le plus grand nombre tel que l'on puisse multiplier une matrice par une matrice dans le temps. Dans un travail de suivi de Lee, Song et Zhang, ils reproduisent le même résultat via une méthode différente. Ces deux algorithmes restent lorsque et . Le résultat dû à Jiang, Song, Weinstein et Zhang s'est amélioré à .

L'opinion actuelle est que les efficacités des bonnes implémentations de méthodes basées sur le simplexe et de méthodes de points intérieurs sont similaires pour les applications courantes de la programmation linéaire. Cependant, pour des types spécifiques de problèmes LP, il se peut qu'un type de solveur soit meilleur qu'un autre (parfois beaucoup meilleur), et que la structure des solutions générées par les méthodes de points intérieurs par rapport aux méthodes basées sur le simplexe soit significativement différente, l'ensemble de variables actives supportées étant généralement plus petit pour ces dernières.

Il existe plusieurs problèmes ouverts dans la théorie de la programmation linéaire, dont la solution représenterait des avancées fondamentales en mathématiques et potentiellement des avancées majeures dans notre capacité à résoudre des programmes linéaires à grande échelle.

• LP admet-il un algorithme fortement polynomial ?
• LP admet-il un algorithme fortement polynomial pour trouver une solution strictement complémentaire ?
• Le LP admet-il un algorithme en temps polynomial dans le modèle de calcul à nombres réels (coût unitaire) ?

Stephen Smale a cité cet ensemble de problèmes étroitement liés comme l'un des 18 plus grands problèmes non résolus du 21e siècle. Selon Smale, la troisième version du problème « est le principal problème non résolu de la théorie de la programmation linéaire ». Bien qu'il existe des algorithmes pour résoudre la programmation linéaire en temps faiblement polynomial , tels que les méthodes ellipsoïdales et les techniques de point intérieur , aucun algorithme n'a encore été trouvé qui permette des performances en temps fortement polynomial en termes de nombre de contraintes et de nombre de variables. Le développement de tels algorithmes présenterait un grand intérêt théorique et permettrait peut-être également des gains pratiques dans la résolution de grands LP.

Bien que la conjecture de Hirsch ait été récemment réfutée pour les dimensions supérieures, elle laisse toujours les questions suivantes ouvertes.

• Existe-t-il des règles pivot qui conduisent à des variantes simplexes en temps polynomial ?
• Tous les graphes polytopaux ont-ils un diamètre polynomialement borné ?

Ces questions concernent l'analyse des performances et le développement de méthodes de type simplex. L'immense efficacité de l'algorithme du simplex dans la pratique malgré ses performances théoriques en temps exponentiel suggère qu'il peut y avoir des variantes du simplex qui s'exécutent en temps polynomial ou même fortement polynomial. Il serait d'une grande importance pratique et théorique de savoir si de telles variantes existent, en particulier comme approche pour décider si LP peut être résolu en temps fortement polynomial.

L'algorithme du simplexe et ses variantes appartiennent à la famille des algorithmes de suivi d'arêtes, ainsi nommés parce qu'ils résolvent des problèmes de programmation linéaire en se déplaçant d'un sommet à l'autre le long des arêtes d'un polytope. Cela signifie que leurs performances théoriques sont limitées par le nombre maximal d'arêtes entre deux sommets quelconques du polytope LP. Par conséquent, nous souhaitons connaître le diamètre théorique maximal des graphes polytopaux . Il a été prouvé que tous les polytopes ont un diamètre sous-exponentiel. La récente réfutation de la conjecture de Hirsch est la première étape pour prouver si un polytope a un diamètre superpolynomial. Si de tels polytopes existent, alors aucune variante de suivi d'arêtes ne peut s'exécuter en temps polynomial. Les questions sur le diamètre des polytopes présentent un intérêt mathématique indépendant.

Les méthodes de pivot simplex préservent la faisabilité primaire (ou duale). En revanche, les méthodes de pivot entrecroisé ne préservent pas la faisabilité (primaire ou duale) – elles peuvent visiter des bases réalisables primaires, réalisables duales ou irréalisables primaires et duales dans n’importe quel ordre. Les méthodes de pivot de ce type sont étudiées depuis les années 1970. Essentiellement, ces méthodes tentent de trouver le chemin de pivot le plus court sur le polytope d’arrangement dans le cadre du problème de programmation linéaire. Contrairement aux graphes polytopaux, les graphes de polytopes d’arrangement sont connus pour avoir un petit diamètre, ce qui permet la possibilité d’un algorithme de pivot entrecroisé fortement polynomial sans résoudre les questions sur le diamètre des polytopes généraux.

Si toutes les variables inconnues doivent être des entiers, le problème est alors appelé problème de programmation en nombres entiers (PI) ou de programmation linéaire en nombres entiers (PLI). Contrairement à la programmation linéaire, qui peut être résolue efficacement dans le pire des cas, les problèmes de programmation en nombres entiers sont dans de nombreuses situations pratiques (celles avec des variables bornées) NP-difficiles . La programmation en nombres entiers 0-1 ou programmation en nombres entiers binaires (PBI) est le cas particulier de la programmation en nombres entiers où les variables doivent être 0 ou 1 (plutôt que des entiers arbitraires). Ce problème est également classé comme NP-difficile, et en fait la version de décision était l'un des 21 problèmes NP-complets de Karp .

Si seules certaines des variables inconnues doivent être des entiers, le problème est alors appelé un problème de programmation mixte en nombres entiers (linéaire) (MIP ou MILP). Ces problèmes sont généralement aussi NP-difficiles car ils sont encore plus généraux que les programmes ILP.

Il existe cependant quelques sous-classes importantes de problèmes IP et MIP qui sont efficacement solubles, notamment les problèmes où la matrice de contraintes est totalement unimodulaire et les côtés droits des contraintes sont des entiers ou – plus général – où le système a la propriété d'intégralité duale totale (TDI).

Les algorithmes avancés pour résoudre des programmes linéaires en nombres entiers incluent :

• méthode du plan de coupe
• Branche et limite
• Branche et coupe
• Filiale et prix
• si le problème présente une structure supplémentaire, il peut être possible d'appliquer une génération de colonnes retardée .

De tels algorithmes de programmation en nombres entiers sont discutés par Padberg et Beasley.

Un programme linéaire en variables réelles est dit intégral s'il possède au moins une solution optimale intégrale, c'est-à-dire constituée uniquement de valeurs entières. De même, un polyèdre est dit intégral si pour toute fonction objective réalisable bornée c , le programme linéaire possède un optimum de coordonnées entières. Comme l'ont observé Edmonds et Giles en 1977, on peut dire de manière équivalente que le polyèdre est intégral si pour toute fonction objective réalisable bornée c , la valeur optimale du programme linéaire est un entier.

Les programmes linéaires intégraux sont d'une importance capitale dans l'aspect polyédrique de l'optimisation combinatoire car ils fournissent une caractérisation alternative d'un problème. Plus précisément, pour tout problème, l'enveloppe convexe des solutions est un polyèdre intégral ; si ce polyèdre a une description compacte, alors nous pouvons trouver efficacement la solution optimale réalisable sous n'importe quel objectif linéaire. Inversement, si nous pouvons prouver qu'une relaxation de programmation linéaire est intégrale, alors c'est la description souhaitée de l'enveloppe convexe des solutions réalisables (intégrales).

La terminologie n’est pas cohérente dans toute la littérature, il faut donc veiller à distinguer les deux concepts suivants,

• dans un programme linéaire en nombres entiers, décrit dans la section précédente, les variables sont contraintes d'être des entiers, et ce problème est NP-difficile en général,
• dans un programme linéaire intégral, décrit dans cette section, les variables ne sont pas contraintes d'être des entiers, mais on a plutôt prouvé d'une manière ou d'une autre que le problème continu a toujours une valeur optimale intégrale (en supposant que c est intégral), et cette valeur optimale peut être trouvée efficacement puisque tous les programmes linéaires de taille polynomiale peuvent être résolus en temps polynomial.

Une façon courante de prouver qu'un polyèdre est intégral est de montrer qu'il est totalement unimodulaire . Il existe d'autres méthodes générales, notamment la propriété de décomposition en nombres entiers et l'intégralité duale totale . D'autres LP intégrales bien connues incluent le polytope correspondant, les polyèdres en treillis, les polyèdres de flux sous-modulaires et l'intersection de deux polymatroïdes généralisés/ g -polymatroïdes – par exemple, voir Schrijver 2003.

Licences permissives :

Licences copyleft (réciproques) :

MINTO (Mixed Integer Optimizer, un solveur de programmation en nombres entiers qui utilise un algorithme de branchement et de liaison) a un code source disponible publiquement mais n'est pas open source.

Licences propriétaires :