Discussion :

[tomjr]

Bonjour,

Dans le cas d'un problème d'affectation à multiples contraintes NP-difficile, je dois coder une méthode arborescente permettant de résoudre le problème de manière exacte.

Or, le seul squelette de méthode arborescente que j'ai trouvé sur internet est plûtot vague :

ViderPile (P)
Empiler dans P le problème initial S0, avec le statut Nouveau
Répéter
Soit S le noeud en sommet de pile
Si S.Statut = Nouveau alors
Si S est une solution unique s alors
Si f(s) < z* alors s* := s ; z* := f(s*) FS
Dépiler (P,S)
Sinon Si (S = ∅) ou (ev(S) ≥ z*) alors
Dépiler (P,S)
Sinon {S doit être séparé}
Choisir la décision à appliquer
Construire le fils gauche dans un record R, statut Nouveau
S.Statut := Gauche
Empiler (P,R)
FS
Sinon Si S.Statut = Gauche alors
S.Statut := Droit;
Construire le fils droit dans un record R, statut Nouveau
S.Statut := Droit
Empiler (P,R)
Sinon {Les 2 fils de S ont déjà été traités, et S.Statut = Droit}
Dépiler (P,S)
FS
Jusqu’à PileVide (P).

Notamment ici :

Empiler dans P le problème initial S0, avec le statut Nouveau

et ici :

S.Statut := Droit;
Construire le fils droit dans un record R, statut Nouveau
S.Statut := Droit

Si quelqu'un pouvait m'éclairer sur ces points ou si quelqu'un connait des squelettes d'algorithme plus précis, je suis preneur!

[Acrim]

Tu peux faire un tour du cote du branch-and-bound et de l'article wikipédia sur Séparation et évaluation. Le principe en lui même n'est pas compliqué : il s'agit de tester toutes les solutions possibles.

Pour cela, a chaque étape on crée plusieurs sous-problème à partir du problème initial (en décidant de fixer la valeur d'une variable par exemple). A l'étape suivante on considère un de ces sous problèmes et on lui fait subir le même traitement. Etc... On fini par soit tomber sur une solution, soit par se rendre compte que le sous-problème considéré n'a pas de solutions (intéressantes au sens de ta fonction objectif). Il faut alors considérer l'un des sous problèmes crées aux étapes précédentes.

On peut voir cela comme le parcours (DFS) d'un arbre dans lequel chaque nœud correspond à un sous problème et où ses descendants sont les sous-problèmes qui en sont tirés.

[tomjr]

Merci pour ta réponse rapide. J'ai commencé l'implémentation de la méthode, mais, je bloque encore sur un point : La remontée dans l'arbre vers le dernier nœud "valable". En effet, je dispose d'une borne inférieure et je supprime un sous-ensemble si son évaluation (par relaxation lagrangienne) est inférieure à ma borne inférieure.

Si l'évaluation de mon fils gauche est inférieure à ma borne inférieure, je passe au fils droit. Mais, si l'évaluation de mon fils droit est inférieure à ma borne inférieure, je ne parviens pas à revenir au niveau précédent...

Voici mon algorithme pour l'instant :

public void methodeArbo(){
resultat = Lagrange(); // Calcule la borne supérieure du problème
Noeud n = meilleurNoeud();// Choisit heuristiquement le meilleur noeud
P.add(n); //Ajoute ce meilleur nœud à la liste des nœuds choisis

while(P.size()<50){ //Tant que je n'ai pas constitué ma solution

Noeud m=meilleurNoeud();

if(verification(m)){ // Si mon noeud est réalisable
compteur=0; //Initialisation d'un compteur à 0 pour dire que le dernier noeud rencontré était réalisable

P.add(m);// Ajout de ce noeud à la solution

}
else{

compteur++; //On entre dans un fils droit


PlaceInterdit.add(m); // On place m dans une liste des placements interdits

Noeud l=meilleurNoeud();

// Verification: Le noeud dans mon fils droit est-il réalisable?
// Si non :
if(!verification(l)){
//On supprime autant de placements interdits que de nombre de fois où on bouclait dans un fils droit
for(int j=0;j<compteur;j++){
PlaceInterdit.pollLast();

}
// On supprime des noeuds de la solution courante
for(int k=0;k<compteur-1;k++){
P.pollLast();
}
//Le dernier noeud de la solution courante devient un placement interdit
PlaceInterdit.add(P.getLast());
// System.out.println(P.getLast().getPlage());
//On supprime alors ce noeud de la solution courante
P.pollLast();
}
}
}

Mes résultats sont loin d'être satisfaisants... La liste des placements interdits augmente, augmente jusqu'à ce que je n'ai plus de placements possibles et donc, ma méthode avorte avant la fin...

[Acrim]

En effet, je dispose d'une borne inférieure et je supprime un sous-ensemble si son évaluation (par relaxation lagrangienne) est inférieure à ma borne inférieure.

N'est ce pas l'inverse ? Si ton évaluation de la borne inférieure t'indique qu'il est potentiellement possible de trouver dans ce sous-arbre une solution de cout inférieur au meilleur cout déjà trouvé alors, il faut continuer. Sinon passer au fils droit.

[tomjr]

N'est ce pas l'inverse ? Si ton évaluation de la borne inférieure t'indique qu'il est potentiellement possible de trouver dans ce sous-arbre une solution de cout inférieur au meilleur cout déjà trouvé alors, il faut continuer. Sinon passer au fils droit.

J'ai oublié de préciser que c'est un problème de maximisation.

Donc si je trouve dans un sous-arbre, une solution de coût inférieur à ma borne inférieure, je m'arrête et je passe au fils droit.

[Acrim]

J'ai oublié de préciser que c'est un problème de maximisation.

Donc si je trouve dans un sous-arbre, une solution de coût inférieur à ma borne inférieure, je m'arrête et je passe au fils droit.

J'ai un doute : dans le cas de la maximisation ne faudrait il pas plutôt considérer une évaluation de la borne max ? (si cette évaluation est plus petite que le max déjà trouvé on arrête, sinon on continue)

[tomjr]

Je viens de finir de coder la méthode. Merci pour ton aide Acrim. Sujet résolu!