Programmation Mathématique Avancée (PMA)
- Titre :
- Programmation Mathématique Avancée (PMA)
- Section :
- Optionnel
- État pour cette année :
- OPEN
- Mots clés :
- programmation quadratique en nombres entiers; programmation non-linéaire en nombres entiers; méthodes exactes; optimisation globale; application du monde réel; langages de modélisation; solveurs d'optimisation
- Ects :
- 2
- Responsable :
- Claudia D'Ambrosio (Polytechnique/LIX)
- Intervenants :
-
Claudia D'Ambrosio (Polytechnique/LIX)
- Prérequis :
cours de programmation mathématique
- Objectif :
Les objectifs de ce cours sont d'apprendre les techniques de résolution d'applications réelles ayant des non-linéarités:
-
Modéliser un problème réel par un problème d'optimisation non-linéaire
-
Étudier les méthodes exactes pour résoudre des :
- problèmes de programmation quadratique, non-convexe avec variables entières
- problèmes de programmation non-linéaire, convexe
- problèmes de programmation non-linéaire, non-convexe en nombres entiers
-
Apprendre un langage de modélisation
-
Coder les méthodes pour résoudre les problèmes étudiés
Les séances théoriques seront alternées avec des séances pratiques. Pendant les séances pratiques, des applications réelles dans le domaine de l'énergie ou de la science des données seront présentées.
-
- Contenu / Plan :
-
Introduction aux MIQPs (A. Lambert)
Nous introduisons les problèmes quadratiques en variables mixtes (MIQP) et étudions leurs propriétés. Nous proposons ensuite des applications réelles qui peuvent se modéliser par un MIQP. Enfin, après avoir introduit les bases des langages de modélisation, nous implémentons les modèles introduits et résolvons des petites instances. -
Algorithmes exacts pour la résolution des MIQPs -- basés sur les relaxations SDP (A. Lambert)
Nous introduisons les concepts de base de l'optimisation semi-définie (SDP), et montrons comment utiliser les relaxations SDP dans des algorithmes de résolution exacts de MIQPs non-convexes. Nous montrons également comment utiliser, en pratique, les solveurs d'optimisation semi-définie. -
Algorithmes exacts pour la résolution des MIQPs -- basés sur les relaxations quadratiques convexes (A. Lambert)
Nous introduisons les concepts de base de la construction de relaxations quadratiques convexes basées sur les relaxations SDP. Nous montrons ensuite comment ces relaxations peuvent être utilisées dans un algorithme de résolution global. Enfin, nous implémentons cette approche combinant l'utilisation des langages de modélisation et des solveurs d'optimisation SDP. -
Introduction aux problèmes de programmation non-linéaire, convexes en nombres entiers et motivations (C. D'Ambrosio).
Exemple de problèmes PNLNE dans différents domaines comme la finance et la production d'énergie. Introduction de l'extension des méthodes issues de la PLNE aux problèmes PNLNE convexes, en particulier : branch-and-bound, outer-approximation, et méthodes hybrides. Nous allons analyser les spécificités des problèmes PNLNE convexes et les défis qu'ils représentent. La session pratique consistera en la modélisation d'applications par un PNLNE convexe et en sa résolution avec un langage de modélisation. -
Introduction aux problèmes de programmation non-linéaire, non-convexes en nombres entiers et motivations (C. D'Ambrosio)
Pourquoi les méthodes exactes pour les problèmes PNLNE convexes s'avèrent inexactes pour les problèmes non-convexes ? En particulier : Optimalité globale vs. locale ; les coupes de outer-approximation ne sont pas valides pour les PNLNE non-convexes. Nous allons introduire et analyser des algorithmes exacts pour les problèmes PNLNE (relaxation de Mc Cormick, branch-and-bound spatial). Dans la session pratique, nous allons modéliser des applications par un PNLNE non-convexe et le résoudre avec un langage de modélisation. -
examen
-
- Bibliographie :
-
-
P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, A. Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, volume 22, pages 1--131. , 2013.
-
P. Belotti, P. Bonami, M. Fischetti, A. Lodi, M. Monaci, A. Nogales-Gómez, D. Salvagnin. On Handling Indicator Constraints. Computational Optimization and Applications, volume 65, pages 545--566, 2016.
-
S.Benítez-Peña, R. Blanquero, E.Carrizosa, P. Ramírez-Cobo. Cost-sensitive Feature Selection for Support Vector Machines. Computers and Operations Research, volume 106, pages 169--178, 2018.
-
D. Bienstock, M. Escobar-Santoro, C. Gentile, L. Liberti, Mathematical Programming formulations for the Alternating Current Optimal Power Flow problem, 4OR, volume 18, pages 249--292, 2020.
-
Y. Liu, S. Canu, P. Honeine, S. Ruan. Mixed Integer Programming for Sparse Coding: Application to Image Denoising. IEEE Transactions on Computational Imaging, volume 5, pages 354--365, 2019.
-
- Liens :
- (aucun)
- Compétences visées :
-
Modéliser un problème issu d'une application réelle comme un programme non-linéaire en nombres entiers (PNLNE)
-
Connaître les méthodes exactes pour les différentes classes de problèmes
-
Identifier la méthode de résolution la plus appropriée pour résoudre une application réelle
-
Implémenter des formulations d'applications réelles grâce aux langages de modélisation
-
Combiner les résultats des solveurs disponibles pour résoudre des applications réelles
-
- Modalités de contrôle :
Examen écrit