Classification des problèmes d'optimisation

Face à la résolution d'un problème d'optimisation, il est important de bien identifier à quelle catégorie ce problème appartient. En effet, les algorithmes développés sont conçus pour résoudre un type de problème donné et sont peu efficaces pour un type différent. La classification des problèmes d'optimisation change d'un auteur à l'autre. Par exemple, on distingue :

Les problèmes d'optimisation continue versus les problèmes d'optimisation discrète

Dans certains cas, les variables de décision sont discrètes, le plus souvent sous la forme d'entiers ou de binaires. Le problème d'optimisation est dit discret. Au contraire, dans les problèmes d'optimisation continue, les variables peuvent prendre n'importe quelle valeur, ce sont des réels. Les problèmes d'optimisation continue sont généralement plus simples à résoudre. Un problème d'optimisation mêlant variables continues et variables discrètes est dit mixte.

Les problèmes d'optimisation avec et sans contrainte

Il est important de bien distinguer les problèmes où des contraintes existent sur les variables de décision. Ces contraintes peuvent être simplement des bornes et aller jusqu'à un ensemble d'équations de type égalité et de type inégalité. Il est parfois possible d'éliminer une contrainte égalité par substitution dans la fonction objectif. Naturellement, les problèmes avec contraintes sont plus compliqués à résoudre et utilisent des algorithmes dédiés.

Les problèmes d'optimisation mono-objectif ou multi-objectif

Les problèmes mono-objectif sont définis par une unique fonction objectif. Les problèmes multi-objectifs existent quand un compromis est à rechercher entre plusieurs objectifs contradictoires. Il est éventuellement possible (mais pas nécessairement efficace) de reformuler un problème multi-objectif avec une seule fonction objectif sous forme d'une combinaison des différents objectifs ou en transformant des objectifs sous forme de contraintes.

Les problèmes d'optimisation déterministe ou stochastique

Les problèmes d'optimisation déterministe considèrent que les données sont connues parfaitement, alors que dans les problèmes d'optimisation stochastique, ce n'est pas le cas ; par exemple une approche stochastique peut être pertinente dans le cas où les variables d'un problème sont les ventes futures d'un produit. Dans ce cas, l'incertitude peut être introduite dans le modèle.

Dans cette introduction à l'optimisation numérique, on se limitera au problème d'optimisation mono-objectif à variables continues avec et sans contrainte selon une approche déterministe.