A voir également:
- Algorithme de branch and bound
- And i miss you ✓ - Forum Musique / Radio / Clip
- Pourquoi han est vivant fast and furious 4 - Forum Cinéma / Télé
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Disk boot failure insert system disk and press enter - Guide
- Your device ran into a problem and needs to restart - Forum Windows 10
10 réponses
slt
je cherche si l'un p vos a déja programme le probleme de voiyageur d e commerce avec branche and bound
je cherche si l'un p vos a déja programme le probleme de voiyageur d e commerce avec branche and bound
de quoi a tu besoin ?
je ne passe pas souvent ici, si tu as besoin d'info precise ecrit moi
et met qqch comme [CCM] dans le sujet (que je ne le prenne pas pour un spam)
bon sinon a propos de Branch and Boubnd
ce n'est pas vraiment un algo
mais plutot un meta-algo, une methode.
l'idee de base est de cree une arbre qui exprimme toute les solutions de ton probleme (en fait pas toute on va voir)
a chaque hauteur de l'arbre tu fixe la valeur d'une variable (ou un intervalle ou qqch comme ca) et tu fais un sous arbre par valeur que peut prendre ta variable
quand tu arrive a une feuille de l'arbre en principe tu obtiens une solution de ton probleme.
mais c'est tres long tel quel (et tres stupide)
(je me place en minimisation)
alors tu va faire une evaluation (une borne inf) en chaque noeud de la qualite du sous arbre enraciner au noeud local
et en parallele a ca, tu stocke al meilleur solution que tu connait (tu pars a 1 milliion ou alors tu initialise avec une heuristique garantie)
si la branche est moins bonne que la solution que tu connait deja, tu arrete d'explorer sinon tu continue
ca c'est le principe de base. apres tu as une notion de strategie.
sois tu fais une
recherche en profondeur d'abors (DFS: deepest first search)
et la tu va essayer de trouver des solution rapidemnet dans le but d'ameliorer ta borne.
soit tu ais une recherche au meilleur d'abors (best first search) et dans ce cas la premiere solution que tu trouve sera l'optimal.
au niveau de l'evaluation souvent ton branch and bound est equivalent a la resolution d'un programme lineaire en nombre entier et il est parfois pas mal d'utiliser le plne relaxe comme fonction d'evaluation...
vala, si tu as des question, tu as mon adresse.
je ne passe pas souvent ici, si tu as besoin d'info precise ecrit moi
et met qqch comme [CCM] dans le sujet (que je ne le prenne pas pour un spam)
bon sinon a propos de Branch and Boubnd
ce n'est pas vraiment un algo
mais plutot un meta-algo, une methode.
l'idee de base est de cree une arbre qui exprimme toute les solutions de ton probleme (en fait pas toute on va voir)
a chaque hauteur de l'arbre tu fixe la valeur d'une variable (ou un intervalle ou qqch comme ca) et tu fais un sous arbre par valeur que peut prendre ta variable
quand tu arrive a une feuille de l'arbre en principe tu obtiens une solution de ton probleme.
mais c'est tres long tel quel (et tres stupide)
(je me place en minimisation)
alors tu va faire une evaluation (une borne inf) en chaque noeud de la qualite du sous arbre enraciner au noeud local
et en parallele a ca, tu stocke al meilleur solution que tu connait (tu pars a 1 milliion ou alors tu initialise avec une heuristique garantie)
si la branche est moins bonne que la solution que tu connait deja, tu arrete d'explorer sinon tu continue
ca c'est le principe de base. apres tu as une notion de strategie.
sois tu fais une
recherche en profondeur d'abors (DFS: deepest first search)
et la tu va essayer de trouver des solution rapidemnet dans le but d'ameliorer ta borne.
soit tu ais une recherche au meilleur d'abors (best first search) et dans ce cas la premiere solution que tu trouve sera l'optimal.
au niveau de l'evaluation souvent ton branch and bound est equivalent a la resolution d'un programme lineaire en nombre entier et il est parfois pas mal d'utiliser le plne relaxe comme fonction d'evaluation...
vala, si tu as des question, tu as mon adresse.
halloumati
Messages postés
1
Date d'inscription
jeudi 8 novembre 2007
Statut
Membre
Dernière intervention
8 novembre 2007
2
8 nov. 2007 à 12:28
8 nov. 2007 à 12:28
Bonjour,
Je cherche des infos sur l'algorithme du Branch and Bound (dans le cadre del'optimisation de l'affectation de la flotte pour une compagnie aérienne ),
Merci
Je cherche des infos sur l'algorithme du Branch and Bound (dans le cadre del'optimisation de l'affectation de la flotte pour une compagnie aérienne ),
Merci
bonjour
s'il vous plait je vous demande de m'envoyez l'algorithme de branch and bound.
je suis étudiant en 2ème année magistére options optimisation globale.
merçi.
s'il vous plait je vous demande de m'envoyez l'algorithme de branch and bound.
je suis étudiant en 2ème année magistére options optimisation globale.
merçi.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Comme je disais au dessus, c'est plus un meta-algorithme qu'un algorithme.
disons que ca peut s'ecrire(en minimisation):
Pour chaque ensemble S de solution:
evaluer la meilleur solution de S
Si l'evaluation est inferieur a la meilleur solution connu
Si c'est une feuille (ie, l'ensemble ne conteint qu'une solution)
On a trouve une meilleur solution
Sinon
Separer S en S_1, S_2, ..., S_n
voila, donc si tu gerer la collectiond e S avec une pile tu as un DFS si tu fais nue liste ordonner par les evaluations, tu as un BFS
disons que ca peut s'ecrire(en minimisation):
Pour chaque ensemble S de solution:
evaluer la meilleur solution de S
Si l'evaluation est inferieur a la meilleur solution connu
Si c'est une feuille (ie, l'ensemble ne conteint qu'une solution)
On a trouve une meilleur solution
Sinon
Separer S en S_1, S_2, ..., S_n
voila, donc si tu gerer la collectiond e S avec une pile tu as un DFS si tu fais nue liste ordonner par les evaluations, tu as un BFS
Bonjour,
Je te remercie de toutes tes explications, mais je ne suis pas une pro de la recherche opérationnelle et donc je ne comprends pas toujours tout... Il s'agit d'un prjet de recherche opérationelle (école d'ingé généraliste) et dc on est un peu debutant en la matière. Je vais me documenter plus amplement et j'aurai des questions un peu plus intelligentes à poser...
En revanche pour ma recherche de doc, j'aimerai savoir s'il y a d'autres méthodes pour répondre à ce problème :
"Une liste de pannes distinctes peuvent être identifiées en réalisant plusieurs tests : chaque test présente un coût, et permet de dire si une panne a lieu parmi plusieurs.
Le problème est de définir les tests à mener, pour identifier de façon certaine la panne à moindre coût.
Vous rechercherez les principales méthodes pouvant être utilisées pour résoudre un problème de couverture (d’ensembles pondérés ou non), tel que celui énoncé.
Vous présenterez la méthode du « Branch and Bounds » (méthode de parcours d’arbres avec marquage binaire) et montrerez comment elle peut être utilisée pour résoudre ce type de problème."
Merci!
Marion
Je te remercie de toutes tes explications, mais je ne suis pas une pro de la recherche opérationnelle et donc je ne comprends pas toujours tout... Il s'agit d'un prjet de recherche opérationelle (école d'ingé généraliste) et dc on est un peu debutant en la matière. Je vais me documenter plus amplement et j'aurai des questions un peu plus intelligentes à poser...
En revanche pour ma recherche de doc, j'aimerai savoir s'il y a d'autres méthodes pour répondre à ce problème :
"Une liste de pannes distinctes peuvent être identifiées en réalisant plusieurs tests : chaque test présente un coût, et permet de dire si une panne a lieu parmi plusieurs.
Le problème est de définir les tests à mener, pour identifier de façon certaine la panne à moindre coût.
Vous rechercherez les principales méthodes pouvant être utilisées pour résoudre un problème de couverture (d’ensembles pondérés ou non), tel que celui énoncé.
Vous présenterez la méthode du « Branch and Bounds » (méthode de parcours d’arbres avec marquage binaire) et montrerez comment elle peut être utilisée pour résoudre ce type de problème."
Merci!
Marion
tu dis:
"Une liste de pannes distinctes peuvent être identifiées en réalisant plusieurs tests : chaque test présente un coût, et permet de dire si une panne a lieu parmi plusieurs.
Le problème est de définir les tests à mener, pour identifier de façon certaine la panne à moindre coût"
Je comprends qu'il y a un test par panne
dans ce cas, tu es morte il faut tout faire.
Mais en suite, le fait de parler de couverture m'indique que ca ne doit pas etre le cas.
Ca doit plutot etre un probleme de couverture qui peut se formaliser comme cela:
k-Couverture:
Instance: un graphe G=(V,E), un entier K
Question: existe t'il A \subset V telque |A| <= K et V = AuN(A)
avec N(A) le voisinage de A
Je ne sais pas si ce probleme est NP-Complet mais etant donné la question, je le suppose. (Ca ressemble un peu a stable max)
On voit bien quel est le PB de maximisation associé:
Couverture Min:
Instance: Un graphe G=(V,E)
Solution: un ensemble A \subset V telque V = AuN(A)
Mesure: |A|
Comment resoudre ca:
bah, en effet par une methode de Branch and Bound.
tu dis qu'une solution c'est un vecteur P de taille |V|
P_i = 1 si i\in A 0 sinon
et tu branche sur toute les combinaisons possible avec une petite fonction d'evaluation, en fait je ne sais pas trop comment.
Mais un PLNE relaxé pourrait faire l'affaire.
eventuelement d'ailleurs tu peux faire une recherche dichotomique
tu cherche une solution de valeur |V|/2
si il y en as tu cherche a 3*|V|/4 sinon a |V|/4 etc...
apres tu peux peut etre te tourner vers les methodes heuristiques
Il doit exister de bonne heuristique pour ce probleme
a base de: selectionner le noeud de degre max, le prendre
ensuite tu continue en prenant le noeud voisin du plus de sommet non deja distribué. Ca a peut etre meme une performance garantie ca...
Tu peux confirmer l'enoncé formel de ton probleme ?
"Une liste de pannes distinctes peuvent être identifiées en réalisant plusieurs tests : chaque test présente un coût, et permet de dire si une panne a lieu parmi plusieurs.
Le problème est de définir les tests à mener, pour identifier de façon certaine la panne à moindre coût"
Je comprends qu'il y a un test par panne
dans ce cas, tu es morte il faut tout faire.
Mais en suite, le fait de parler de couverture m'indique que ca ne doit pas etre le cas.
Ca doit plutot etre un probleme de couverture qui peut se formaliser comme cela:
k-Couverture:
Instance: un graphe G=(V,E), un entier K
Question: existe t'il A \subset V telque |A| <= K et V = AuN(A)
avec N(A) le voisinage de A
Je ne sais pas si ce probleme est NP-Complet mais etant donné la question, je le suppose. (Ca ressemble un peu a stable max)
On voit bien quel est le PB de maximisation associé:
Couverture Min:
Instance: Un graphe G=(V,E)
Solution: un ensemble A \subset V telque V = AuN(A)
Mesure: |A|
Comment resoudre ca:
bah, en effet par une methode de Branch and Bound.
tu dis qu'une solution c'est un vecteur P de taille |V|
P_i = 1 si i\in A 0 sinon
et tu branche sur toute les combinaisons possible avec une petite fonction d'evaluation, en fait je ne sais pas trop comment.
Mais un PLNE relaxé pourrait faire l'affaire.
eventuelement d'ailleurs tu peux faire une recherche dichotomique
tu cherche une solution de valeur |V|/2
si il y en as tu cherche a 3*|V|/4 sinon a |V|/4 etc...
apres tu peux peut etre te tourner vers les methodes heuristiques
Il doit exister de bonne heuristique pour ce probleme
a base de: selectionner le noeud de degre max, le prendre
ensuite tu continue en prenant le noeud voisin du plus de sommet non deja distribué. Ca a peut etre meme une performance garantie ca...
Tu peux confirmer l'enoncé formel de ton probleme ?
bonjour,
je veux savoir des informations sur l'heuristique NEH et son codage en C++.
quel type de problème d'ordonnancement s'adapte mieux.
Merci
je veux savoir des informations sur l'heuristique NEH et son codage en C++.
quel type de problème d'ordonnancement s'adapte mieux.
Merci
Bonjour,
Quelqu'un peut m'aider à résoudre ce problème svp:
Je dois écrire un programme permettant de créer le programme linéaire du stable pondéré associé à une instance passée en paramètre lors de l'exécution du programme.Résoudre le programme linéaire et afficher la solution optimale du problème,es variables duales ainsi que la base.On nous dit qu'il faut utiliser la librairie Callable de cplex
Puis,en utilisant les outislde cplex liés à la programmation linéaire, implémenter un algorithme de séparation et évaluation pour résoudre de manière exacte le problème du stable pondéré.
Je vous remercie d'avance.
Quelqu'un peut m'aider à résoudre ce problème svp:
Je dois écrire un programme permettant de créer le programme linéaire du stable pondéré associé à une instance passée en paramètre lors de l'exécution du programme.Résoudre le programme linéaire et afficher la solution optimale du problème,es variables duales ainsi que la base.On nous dit qu'il faut utiliser la librairie Callable de cplex
Puis,en utilisant les outislde cplex liés à la programmation linéaire, implémenter un algorithme de séparation et évaluation pour résoudre de manière exacte le problème du stable pondéré.
Je vous remercie d'avance.
