3.6.1.2 Méthode de coupes planes
(Cutting-Plane)
La méthode de coupes planes a été
développée par (Schrijver 1986), elle est destinée
à résoudre des problèmes d'optimisation combinatoire (POC)
qui se formulent sous la forme d'un programme linéaire.
3.6 Méthodes de résolution 37
-Page 37-
3.6 Méthodes de résolution 38
Dans le cas où le POC est de grande taille pour le
représenter explicitement en mémoire ou pour qu'il tient dans un
solveur de programmation linéaire, on utilise une technique qui consiste
à enlever une partie de ces contraintes et de résoudre le
problème relaxé (PR). La solution optimale de (PL) est contenue
dans l'ensemble de solutions réalisables de cette relaxation. Pour un
problème de maximisation la solution optimale du problème (PR)
est supérieure ou égale à la solution optimale
donnée par (POC).
Cette méthode consiste à résoudre un
problème relaxé, et à ajouter itérativement des
contraintes du problème initial. On définit une contrainte pour
le problème de maximisation par le couple (s, s ) où
s E Rn et s E R, cette contrainte est dite
violée par la solution
courante x si pour tout y E {x : Ax
b} on a sx < s et sy ~ s , on appelle alors
ces
contraintes des coupes planes. On arrête l'algorithme lorsqu'il
n'y a plus de contraintes violées par la solution courante, on obtient
ainsi une solution optimale pour le problème initial [10].
Remarque 3.6.1. La méthode des
coupes planes est peu performante mais sa performance est
améliorée lorsqu'elle est combinée avec la méthode
"Branch and Bound".
3.6.1.3 Méthode de Branch and Cut
La méthode des coupes planes n'est pas toujours
efficace face aux problèmes difficiles. De même, bien que
l'algorithme du "Branch and Bound" puisse être très performant
pour une certaine classe de problèmes, pour cela on utilise la
méthode "Branch and Cut" qui combine entre l'algorithme du "Branch and
Bound" et de la méthode des coupes planes. Pour une résolution
d'un programme linéaire en nombres entiers (PLNE), la méthode
"Branch and Cut" commence d'abord par relaxer le problème puis appliquer
la méthode des coupes planes sur la solution trouvée. Si on
n'obtient pas une solution entière alors le problème sera
divisé en plusieurs sous-problèmes qui seront résolus de
la même manière [10].
3.6.2 Méthodes approchées:
Le but de ces méthodes est de trouver une solution de
bonne qualité pour un problème d'optimisation de grande taille en
un temps de calcul raisonnable sans garantir l'optimalité de la solution
obtenue [14]. Les méthodes approchées sont réparties en
deux catégories principales : les heuristiques et les
méta-heuristiques.
-Page 38-
| 
