Le 22/08/2011 par mathro :

salut,
je suis entrain de rédiger un mémoire licence RO ,je me suis arrivé aux méthodologies de résolution des problème en nombre entier ,j'ai adapté pour les méthodes exact B&B et pour approcher heuristique je veux ajouter d'autre méthodes exact ,en fait j'ai chercher d'autre méthodes mais c'était pas clair pour moi c'est pour cette raison que je cherche une aide pour me donner des méthodes exact pour la résolution des problème en nombre entiers(entier et binaire en mem temp).
j'ai rencontré encore un autre problème lors de la résolution d'un problème par B&B contenant des variables binaires ,quand on fait la relaxation les variables binaire vont appartenir à l'intervalle [0,1] alors comment on cherche la borne inférieurs de la fonction objecti vu qu'on ne peut pas utuliser l'algo de simplexe (en fait on peut ajouter des contraintes >=0 et <=1 mais faire ça pour chaque variables c'est beaucoup) surtout puisque je doit programmer cette méthode alors je vous serais très très reconnaissant de m'éclairer sur ça!!!!!
merci d'avance,

Le 26/08/2011 par moeini :

Ben c'est le défaut de la méthode B&B, la taille de l'arbre croit de façon exponentielle

Le 27/08/2011 par mathro :

oui en fait c'est ça le problème des méthodes exact sinon on passe pas aux méthodes approché mais le problème réside dans la résolution des problème en nombre entier par B&B je sais pas comment faire pour déterminet le borne inférieur de la fonction objectif lors de la relaxation vu que les variables binaires serons bornés et l'utilisation de simplexe sera inutile en rajoutant tout les contraintes afin d'avoire les bornes alors comment faire et merci

Le 01/09/2011 par athrus :

Typiquement pour l'approche standart dans l'algorithme B&B c'est d'obtenir à la fois une borne inf et une borne supp.
Dans le cas d'une minimisation,
le plus souvent la borne inf est obtenue par relaxation continue: on prends le programme linéaire et on dis que les variables bouléen sont des réels dans l'intervalle [0,1].
On peut aussi obtenir des bornes des meilleures qualité en utilisant des techniques dérivé de la relaxation lagrangienne: par exemple la décomposition de Dantzig Wolfe.
On a aussi la possibilité d'ajouter des inégalitées valides, c'est un peu compliquer à expliquer en quelques lignes, l'idée c'est resserer le polyèdre de la relaxation continue, autour de l'envelloppe convexe de l'ensemble admissible entier. Notez bien qu'aujourd'hui cette technique est la réference, elle est utilisé dans quasiment tout les solver B&B. Le Branch&Bound avec inégalité valide est appellé Branch&Cut. Les coupes les plus simples à comprendres sont les coupes de Gomory.
La borne supp quand à elle est obtenue générallement par des heuristiques, l'heuristique de base est d'arrondir la solution de la relaxation continue et de voir si la solution est admissible. Si la solution est admissible alors on a une borne supp. Il existe énormément d'approche spécifique.
Toujours basé sur la programmation linéaire il y'a la décomposition de Benders (je suis pas totalement certain) qui est utilisé pour résoudre les problème de facon exacte, notament ceux qui ont une nature décomposable. Cette techniques à néanmoin une complexité pire cas exponentielle.
Il y'a aussi le shéma de programmation dynamique, qui peuvent fonctionner sur certains problèmes, notament le problème du sac à dos si je me souviens bien.
Toutes les techniques d'optimisation combinatoire doivent etre adapté au problème que l'on veu résoudre, il n'existe pas de recette miracle. Pour résoudre un problème NP-difficile (et meme certain probleme de P), il faut une compéhension parfaite du problème, un recul, de l'imagination.

Pour répondre ce que je te conseille:
si tu fait une minimisation:
la borne Inf : simplexe, si t'est conrageux coupe de gomory
la borne Supp: initialisé à l'infini, chaque solution donnée par la simplexe tu arrondi à l'entier, si la solution est admissible et qu'elle est inférieur à l'ancienne borne supp utilise cette solution comme borne supp.

J'espere t'avoir aidé.

Le 06/09/2011 par mathro :

merci athrus ,
ok je vais essayer avec coupe de gomory peut etre ça va m'aider puisque j'ai jamais entendu parler de cette méthode .

Le 19/10/2011 par assia :

essaye de voir la programmation dynamique c'est une méthode exacte

Le 19/10/2011 par assia :

essaye de voir la programmation dynamique c'est une méthode exacte

Le 03/04/2012 par faraoula :

Bonjour je cherche des articles sur le problème du sac à dos, Pouvez vous m'aider à en trouver.