Problème d'optimisation

[mathibert]

Bonjour à tous,

je suis occupé à effectuer un travail sur les problèmes d'optimisation et j'aimerai lister les différents types de problèmes d'optimisation qui existe (le plus courants).

J'ai commencé à me documenter et est trouvé ceux-ci :

- problème combinatoire
- problème multiobjectifs
- problème dynamique
- Méthodes déterministes ou exactes
* Local ou global

- Méthodes stochastiques (méta-heuristique, etc)

Le problème c'est qu'il y a tellement que je ne suis pas certains d'effectuer un "bon" classement et surtout s'il est complet et logique...

Je supose que je ne dois pas mettre sur le même pied d'égalité combinatoire et multiobject? Puisqu'un problème combinatoire peut être multi ou mono non?

J'ai également rencontrés quelques difficultés pour comprendre la définition d'un problème combinatoire. En lisant, j'ai l'impression que les définitions sont trop souvent générales et que je peux donc englober la plupart des problèmes dans cette catégorie. Par exemple la programmation linéaire peut elle être englobé dans combinatoire?

Merci d'avance pour votre aide

[fatal_error]

yo,

dans un multiobjectifs, comme son nom le dit, tu cherches a optimiser plusieurs criteres en même temps.

par exemple, tu vends des voitures, tu veux en vendre le plus possible et les vendre le plus cher possible.

dans un combinatoire pas forcément, ex : plus court chemin dans un graphe.

pour les problemes dynamiques je sais pas ce que t'entends. Si c'est les problemes qui se resolvent bien par programmation dynamique, alors ca reste qd même différent de la combinatoire. Ex : calculer suite de fibonacci.

enfin pour le probleme multiobjectif, ou on peut etre amené à manipuler des grandeurs continues (ex : le prix de vente), on peut toujours se ramener à des grandeurs discrètes ce qui au final nous ramène à un problème de combinatoire :D(vu qu'on manipule des grandeurs discrètes), mais bon le sens est pas trop le même.

edit : les problemes de combinatoire, à mes yeux c'est tous les problemes dont les valeurs manipulées sont des valeurs discrètes et bornées, telles qu'avec un certain temps, on trouve la solution.
Une programmation linéaire, à valeurs réelles ben c'est niqué. Après, tout comme le multiobj, on peut très bien passer les valeurs réelles en valeurs discrètes pour traiter ca de manière combinatoire, mais quitte à manipuler des grandeurs, généralement le continu c'est plus agréable.

[mathibert]

Avant tout merci pour ta réponse.

Je comprends mieux maintenant la notion de combinatoire...ça reprend tous les problèmes dont les variables prennent leur valeur dans un ensemble fini ou un ensemble dénombrable.

Par dynamique j'entendais les problèmes pour lesquels l'objectif peut changer au cours du temps.

En ce qui concerne mon objectif de créer une liste des différents types de problèmes, je partirais plus alors vers les caractéristiques des problèmes d'optimisation qui fonctionne souvent par pair comme :

-problème discret-continu
-problème mono-multiobjectif
-méthode exacte - approchés
- statique - dynamique
- ??

Existe-t-il d'autres caractéristiques sur les problèmes d'optimisation?

C'est plus approprié non? Car apparemment il n'y a pas vraiment de hiérarchie.

Et alors chacune de ces caractéristique peut se combiner avec d'autre c'est bien ça?
Comme pour l'exemple que tu me cite avec la programmation linéaire... On peut avoir un problème linéaire discret ou continu...

[fatal_error]

les optimisations exactes, approchées c'est du lourd.
Vu que forcément tu vas tomber dedans autant faire deux grosses parties et présenter dans les exactes quels types de problemes sont solvables de manière efficaces, et dans les approchées ceux qu'on solve de manière approchées.

Tu peux looker au niveau de la complexité des problèmes. Par exemple un probleme NP se fera plus de manière approchée que exacte.

Apres par exemple, la combinatoire ca va souvent se résoudre de manière approchée parce qu'on peut pas explorer toutes les solutions, et même si on résoud avec des contraintes et tout, ca prend qd même du temps. Alors qu'avec une heuristique bien placée ca va considérablement plus vite, mais on sait pas si on trouve LA meilleure solution.

[Sylviel]

Après il y a tout un tas de propriétés de ta fonction objectif :
- déterministe / stochastique
- convexe
- différentiable
- linéaire (ou quadratique)

Attention à ne pas mélanger les propriétés du problèmes, et celles des méthodes de résolution envisagées.

Oui différentes caractéristiques peuvent se combiner. Attention la programmation linéaire 'discrète' c'est souvent de la programmation linéaire en nombre entier, et nettement plus complexe que la programmation linéaire 'continue'...

[Sylviel]

@ fatal error : Je reviens sur les problèmes combinatoire --> même s'ils sont compliqués tu peux les résoudre de manière exacte (plus facilement que les problèmes continus puisque la solution sera presque toujours numérique). En fait on utilise un certain nombre de méthodes pour éliminer bon nombre de cas... Enfin ces mêmes méthodes et d'autres peuvent te donner une borne inf à la valeur optimale, et tu peux ainsi assurer que tu es à moins de 5% par exemple de l'optimum avec ton heuristique.

[fatal_error]

salut sylviel,

ben comme ca :
voyageur du commerce
jeux style echecs, go

ils se resolvent pas de maniere exacte. Enfin pas pour nous. Pour les maouss clusters de Gpu ok, mais pour le péon lambda ben ca se résumera à des éliminations et une heuristique.

pour la borne inf, ui mais avoir une méthode proche de l'optimal c'est pas l'optimal.
En revanche, je veux bien savoir si tu as des méthodes pour calculer une borne inf.
Genre typiquement pour le voyageur, à partir d'un algo, il existe une boite noire qui permet de calculer la borne inf? ou faut foutre la main dans le camboui?

[mathibert]

Oui effectivement je faisais un mélange entre les propriétés du problèmes et celles des méthodes de résolution envisagées.

Le sujet me semble maintenant plus clair. Je vais me lancer dans mon travail...

Si j'ai d'autres questions je reviendrais vers vous.

Un grand merci à vous deux pour votre aide