Une méthode d'optimisation qui choisit des variables de décision à valeurs entières pour maximiser ou minimiser une fonction objective linéaire sous un ensemble fini de contraintes linéaires d'égalité et d'inégalité.

Principe

La contrainte d'intégralité restreint l'ensemble des solutions admissibles à un sous-ensemble discret du polyèdre de la relaxation linéaire ; on trouve des optima entiers en explorant ce sous-ensemble discret par branchement, ajout de plans de coupe ou énumération guidée par des bornes linéaires.

Démonstration

Situation : Une usine affecte des machines (0 ou 1) à deux produits sous contraintes de capacité et de demande. Reconnaissance : Les variables représentent des nombres entiers de machines et doivent être entières. Action : Formuler l'objectif linéaire de profit, les contraintes de capacité linéaires, et résoudre par branch-and-bound sur la relaxation LP. Conséquence : Le solveur renvoie une affectation entière maximisant le profit total tout en respectant les contraintes.

Mauvaise application

Traiter la PLNE comme équivalente à la résolution du programme linéaire continu puis arrondir l'optimum continu. L'erreur consiste à supposer que l'arrondi garantit la faisabilité entière et l'optimalité ; l'arrondi peut violer des contraintes et donner des solutions sous-optimales ou irréalisables.

Conséquence

Une application correcte produit des plans réalisables et des bornes d'optimalité valides (par ex. nombre d'unités, itinéraires) ; une mauvaise application (arrondi naïf) peut mener à des plannings infaisables, à des coûts imprévus ou à une surestimation des performances.

Inversion

Si les décisions entières interagissent non linéairement (produits de variables entières) ou si l'on accepte des décisions fractionnaires interprétées statistiquement (par ex. allocations attendues), l'hypothèse d'ILP standard tombe et il faut recourir à des formulations mixtes non linéaires ou stochastiques.

Limite

Clairement dans : Un problème d'implantation avec variables binaires d'ouverture/fermeture et contraintes linéaires de capacité. Cas frontière : Variables de comptage élevées où la relaxation LP donne des bornes serrées mais des plans de coupe sont nécessaires. Claire­ment hors : Une optimisation entière à objectifs ou contraintes non linéaires (pas une PLNE).

Tension sémantique

Optimalité ↔ Faisabilité calculable — l'intégralité assure des solutions exploitables mais complexifie la résolution par rapport aux relaxations continues.

Synthèse

La PLNE sépare la faisabilité opérationnelle discrète du monde convexe continu ; son usage efficace combine bornes LP, branchement et coupes pour concilier exactitude et complexité combinatoire.