Soutenance mémoire
Méthodes globales
En dépit de l’apport des méthodes locales par rapport à l’efficacité du temps d’exécution, les méthodes globales demeurent infaillible par rapport à l’optimalité de la solution calculée si elle existe.
Dans cette section, nous présenterons des approches globales ; à savoir : la Programmation Linéaire en Nombres Entiers et la Programmation Par Contraintes.
Programmation linéaire en nombres entiers (PLNE)
La programmation linéaire (PL) est un outil de base en recherche opérationnelle.
Elle comprend des techniques puissantes qui permettent de modéliser et de résoudre une multitude de problèmes d’optimisation. Résoudre les problèmes d’optimisation avec la PL consiste à chercher le minimum (resp. le maximum) d’une fonction f, tout en assurant la satisfaction d’un système d’équations et d’inéquations linéaires.
La difficulté de la résolution réside dans deux points :
1. déterminer l’ensemble des points qui satisfont les contraintes, puis
2. trouver leur minimum.
On distingue dans la programmation linéaire, la programmation linéaire en nombres réels (où les variables sont continues) et la programmation linéaire en nombres entiers.
La programmation linéaire en nombres entiers (PLNE) 2 (Wolsey, 1998; Winston, 2004) fournit des méthodes efficaces les plus exploitées pour le traitement des problèmes d’optimisation, notamment en raison de ses possibilités riches en modélisation.
Un programme PLNE est un programme linéaire (PL) où certaines variables doivent être entières, voire même restreintes au domaine booléen f0; 1g. Ces variables sont dites soumises à des contraintes d’intégrité 3. En général, un modèle PLNE implique :
– Un ensemble de variables mathématiques de décision ;
– Un ensemble de contraintes linéaires, où chacune exige qu’une expression linéaire des variables de décision est soit égale à, inférieure à, ou supérieure à une valeur réelle ;
En anglais, Mixed-Integer Linear Programming (MILP, MIP).
Un problème de programmation linéaire classique (PL) sera dit en variables continues.
– Une fonction objectif linéaire qui évalue le coût de la solution. Résoudre un problème PLNE consiste à chercher dans l’espace des points satisfaisant toutes les contraintes, celui qui donne la plus petite valeur à la fonction objectif à minimiser. En général, un problème PLNE prend la forme :
Définition consistance des domaines
La consistance des domaines est liée à la notion de faisabilité d’une solution partielle. Une valeur v appartenant au domaine d’une variable xi vérifie la consistance des domaines, si et seulement si pour toute contrainte cj impliquant la variable xi, il existe une instanciation des variables appartenant à vars(c) telle que c soit vérifiée.
L’algorithme de filtrage consiste à réduire les domaines des variables, en supprimant les valeurs qui n’appartiendront à aucune solution (i.e., en vérifiant la consistance des domaines).
Définition Algorithme de filtrage
Un algorithme de filtrage est un algorithme de réduction associé à une contrainte cj . Son rôle est de supprimer les valeurs non consistantes 4 des domaines de définition des variables dans vars(cj). Suite à la réduction du domaine d’une variable, d’autres variables apparaissant dans d’autres contraintes peuvent devenir inconsistantes. D’où l’intérêt de faire appel à un mécanisme de propagation pour tenter toutes les réductions possibles suite au retrait des valeurs contenues dans les domaines des variables.
Méthodes de résolutions des CSP
Une méthode de résolution de CSP doit identifier une affectation des valeurs aux variables de telle sorte que toutes les contraintes soient satisfaites (i.e., une affectation totale et consistante). La démarche générale consiste à explorer l’espace de recherche défini par le produit cartésien des domaines, et se termine quand une affectation consistante est trouvée, ou bien quand l’inexistence d’une telle affectation est prouvée (CSP inconsistant).
La méthode la plus simple pour chercher une solution d’un CSP consiste à générer toutes les affectations « complètes » des variables, et à vérifier ensuite, si chacune des instanciations candidates générées est une solution valide du problème. Cette stratégie « generate and test » est très coûteuse. D’où l’intérêt de faire appel à des schémas élaborés plus sophistiqués pour résoudre d’une manière plus efficace le problème en question.
Le premier schéma adopté est celui du « retour arrière » qui consiste à générer une affectation partielle consistante ; puis à étendre cette affectation partielle avec l’instanciation d’une nouvelle variable. En d’autres termes, les variables du CSP sont instanciées jusqu’à ce que :
– Au moins une contrainte est violée. L’algorithme revient sur la dernière instanciation, et teste une autre valeur sur la variable la plus récente.
– Si toutes les valeurs de cette variable ont été testées, sans succès, l’algorithme fait un retour arrière (back-track en anglais) sur la variable qui précède la variable la plus récente.
– Ce processus s’arrête une fois qu’une solution est trouvée, ou bien le retour arrière atteint la racine de l’arbre de recherche sans qu’une solution ne soit trouvée.
Le schéma de résolution par « retour arrière » peut être mis en oeuvre dans deux directions :
1. Stratégie prospective : Elle consiste à tirer profit des algorithmes de filtrage (voir la sous-section précédente) avant chaque instanciation d’une variable, afin d’éliminer celles qui ne pourront pas mener à une solution.
2. Stratégie Rétrospective : En cas d’échec sur une variable, au lieu de revenir sur la variable précédente, on analyse les causes de l’échec pour faire un retour arrière vers la variable qui est à l’origine de l’échec. Parmi les méthodes rétrospectives les plus élaborées, on cite la méthode de dynamic-backtracking (Ginsberg, 1993).
Ces deux dernières stratégies sont les plus couramment utilisées dans les solveurs de contraintes, et tout particulièrement le recours intensif aux algorithmes de filtrage permettant de réduire d’une façon drastique l’espace de recherche.
Problème symétrique
La symétrie est l’un des sujets critiques en PPC et en recherche opérationnelle, devenant un domaine de recherche à part entière. L’origine du traitement des symétries, plus spécialement en PPC, est dû au fait que le processus de la recherche des solutions peut revisiter de nombreuses fois des états équivalents, voire même un nombre exponentiel de fois. Ces états équivalents sont dits symétriques. L’élimination des symétries permet de réduire l’arbre de recherche manipulé par l’algorithme de résolution. Par conséquent, les techniques d’élimination des symétries peut booster sérieusement le processus de résolution sur les problèmes symétriques. Dans notre travail, nous nous intéressons aux symétries des solutions définies sur des matrices de variables.
Exemple 2.4.1 (Les symétries dans un échiquier) (Rossi et al., 2006) Considérons un échiquier 3 3, dont nous marquons les 9 cases avec les nombres de 1 à 9. Nous supposons que le problème admet une solution désigné par la matrice sol ci-dessous :
Élimination des symétries
L’élimination des symétries est un principe qui permet d’accélérer le mécanisme de résolution. Une étape primordiale à réaliser avant l’élimination des symétries, est l’étape de détection des symétries du problème à traiter.
On distingue deux types de symétries (Benhamou et Saïdi, 2007b) :
– Les symétries globales : sont les symétries détectées sur le problème à l’origine.
– Les symétries locales : sont les symétries détectées sur le problème à chaque noeud de résolution au niveau de l’arbre de recherche.
En d’autres termes, les symétries globales sont les symétries détectées au niveau de la racine de l’arbre de recherche et qui peuvent ne pas être vérifiées au niveau des autres noeuds.
Élimination statique de symétries
Une élimination de symétrie statique est une approche basée sur l’addition de nouvelles contraintes au CSP initial, afin d’éliminer toutes les solutions symétriques.
En d’autres termes, ces contraintes permettent de éliminer les symétries détectées et mènent vers un nouveau CSP sans symétries.
Les symétries les plus traitées par l’approche statique, sont les symétries ligne et colonne (Flener et al., 2002, 2003; Kiziltan, 2004). Afin d’éliminer toutes les symétries ligne ou colonne, on peut ordonner les lignes (ou les colonnes) dans un ordre lexicographique. Les lignes (ou les colonnes) d’une matrice 2-d, sont ordonnées dans un ordre lexicographique. Si une ligne (resp. une colonne) est, de point de vue lexicographique, plus petite que la suivante, et on note 6lex. Dans le cas d’ordre anti-lexicographique, chaque ligne (resp. une colonne) est plus grande que la ligne suivante, si elle est plus grande de point de vue lexicographique. L’exemple ci-dessous illustre un cas de matrice représentant des symétries ligne et colonne.
Élimination dynamique des symétries globales
Une élimination dynamique de symétries (Puget, 2006) contrairement à l’élimination statique, est basée sur deux points :
1. l’addition de nouvelles contraintes après chaque exploration d’un nouveau noeud de l’arbre de recherche. Ces contraintes, appelées contraintes conditionnelles, vont nous permettre d’éliminer les variantes symétriques de l’affectation (ou l’instanciaton) partielle en cours.
2. l’utilisation de chaque sous-arbre exploré sans succès comme un no-good pour éviter une exploration répétée de la variante symétrique.
|
Table des matières
I Etat de l’art
1 Ingénierie des finances et la problématique de conception des portefeuilles
1.1 Introduction
1.2 Terminologie financière de base
1.3 Risque financier
1.4 Obligations adossées à des actifs (CDO)
1.4.1 CDO2
1.4.2 Optimisation d’un portefeuille financier et le CDO2
1.5 Modèles ensemblistes de conception des portefeuilles
1.5.1 Modèle d’optimisation des portefeuilles (OPD)
1.5.2 Modèle de conception des portefeuilles (PD)
1.5.3 Résolution du problème (PD)
1.6 Conclusion
2 Méthodes de résolution
2.1 Introduction
2.2 Méthodes locales
2.2.1 Méthodes de recherche locale simple
2.2.1.1 Recuit simulé
2.2.1.2 Méthode IDWalk
2.2.1.3 Recherche Tabou
2.2.2 Méthode de recherche locale à voisinage variable (VNS)
2.2.2.1 Méthode Skewed Varibale Neighbourhood Search (SVNS)
2.2.3 Méthode de recherche locale à population GWW
2.2.4 Étude des paysages
2.3 Méthodes globales
2.3.1 Programmation linéaire en nombres entiers (PLNE)
2.3.2 Programmation par contraintes (PPC)
2.4 Problème symétrique
2.4.1 Symétrie sémantique
2.4.2 Symétrie syntaxique
2.5 Élimination des symétries
2.5.1 Élimination statique de symétries .
2.5.2 Élimination dynamique des symétries globales
2.6 Conclusion
II Contribution
3 Méthodes approchées pour le problème de conception de portefeuilles
3.1 Introduction
3.2 Modèle matriciel
3.3 Exemple de motivation
3.4 Composants de base des recherches locales
3.4.1 Fonction coût
3.4.2 Fonctions de voisinage
3.4.2.1 Fonction de voisinage flip
3.4.2.2 Fonction de voisinage swap
3.5 Algorithme glouton pour calculer la solution initiale
3.6 Méthodes de recherche locale simple
3.7 Méthodes de recherche locale à voisinage variable (VNS)
3.7.1 Recherche locale à voisinage variable biaisée (skewed VNS)
3.8 Méthode de recherche locale à population GWW
3.9 Etude expérimentale
3.9.1 Mise en oeuvre des algorithmes sous INCOP
3.9.2 Protocole expérimental
3.9.3 Résultats expérimentaux
3.9.3.1 Expérimentation de l’algorithme glouton
3.9.3.2 Recherches locales simples
3.9.3.3 Étude du paysage de résolution avec recherche locale simple
3.9.3.4 Recherche locale avec voisinage variable
3.9.3.5 Méthode à population GWW
3.9.4 Étude des profiles de performance
3.10 Conclusion
4 Méthodes exactes pour le problème de conception de portefeuilles 83
4.1 Introduction
4.2 Exemple de motivation
4.3 Approche basée sur la Programmation en Nombres Entiers (PLNE)
4.3.1 Linéarisation du modèle (PD)
4.3.2 Élimination des symétries sur le modèle linéaire
4.4 Approche PPC
4.4.1 Modélisation du problème (PD) en PPC
4.4.2 Symétries dans le problème (PD)
4.5 Etude expérimentale
4.5.1 Approche PLNE
4.5.1.1 L’environnement SCIP
4.5.1.2 Résultats expérimentaux
4.5.2 Approche PPC
4.5.2.1 Environnement GECODE
4.5.2.2 Résultats expérimentaux
4.5.3 Synthèse des résultats
4.6 Conclusion
Télécharger le rapport complet
