Optimisation des systèmes complexes
Objectifs
Pour exploiter des systèmes complexes du monde réel, des problèmes d'optimisation complexes et à grande échelle doivent être résolus.
Dans ce cours, nous appliquons un type majeur de modèle (en termes de programmes linéaires en nombres entiers) pour résoudre différents problèmes d'optimisation.
Plan du cours
Dans ce cours, nous présentons un tel modèle pour plusieurs problèmes d'optimisation comme la recherche
- d'un flux maximal
- d'un couplage ou d'un ensemble stable maximal
- de colorations minimales
- de tours minimaux à travers les nœuds d'un graphe
Nous discutons de concepts avancés et de techniques de résolution qui aident à résoudre des instances à grande échelle de ces problèmes :
- formulations idéales
- méthodes de plan de coupe et technique de branchement et de limite
- méthode de génération de colonnes
- relaxations lagrangiennes
Chacun des problèmes discutés a une caractéristique particulière. Par exemple,
- pour un flux maximal, la matrice de contraintes est totalement unimodulaire ce qui donne une formulation idéale pour que le problème puisse être résolu efficacement avec des techniques de programmation linéaire
- pour des couplages maximales, nous montrons comment des contraintes supplémentaires peuvent être générées dans les méthodes de plan de coupe
- pour des colorations minimales, l'encodage nécessite trop de variables pour que la génération de colonnes soit nécessaire
- pour des circuits minimaux à travers les nœuds d'un graphe, l'encodage nécessite trop de contraintes pour que des relaxations Lagrangiennes soient appliquées
Description des TP
aucun TP
Connaissances requises
Comment modéliser un problème sous forme de programme linéaire en nombres entiers et quelle méthode doit être appliquée pour le résoudre