Programmation Linéaire à valeurs 0/1


Ces particulier de la programmation "linéaire" :

Le problème à résoudre se modélise également sous la forme d'une fonction "objectif" (somme pondérée de variables) à optimiser, ainsi qu'un ensemble de contraintes à respecter (système d'équations linéaires).

Mais dans ce cas, les variables ont toutes pour valeurs "binaires", et ont pour valeurs possibles '0' et '1'.


Le méthode consistant à considérer toutes les combinaisons possibles d'affectations des variables peut bien entendu vite devenir inutilisable.


Nous présentons ici une méthode d'affectation progressive des variables en constituant un "arbre (binaire) d'analyse". Plutôt que de construire l'intégralité de cet arbre, ce qui reviendrait à tester toutes les combinaisons possibles, nous intégrons à la recherche des méthodes d'élagage : on ne progresse dans une voie donnée que si l'on est certain qu'une solution respectant toutes les contraintes est encore possible, et que si on a encore une possibilité d'y trouver l'optimum recherché.

A cet arbre de recherche et aux méthodes d'élagage se greffent des stratégies de recherche basées sur l'ordre de prise en compte des variables et des valeurs.