Xu, Liding
[VerfasserIn]
;
Institut polytechnique de Paris
[MitwirkendeR];
Liberti, Leo
[MitwirkendeR];
D'ambrosio, Claudia
[MitwirkendeR]
Relaxation methods for mixed-integer nonlinear programming ; Méthodes de relaxation pour la programmation non linéaire en nombres entiers mixtesRelaxation methods for mixed-integer nonlinear programming
Titel:
Relaxation methods for mixed-integer nonlinear programming ; Méthodes de relaxation pour la programmation non linéaire en nombres entiers mixtesRelaxation methods for mixed-integer nonlinear programming
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Cette thèse se concentre sur la programmation non linéaire à variables mixtes (MINLP), une classe de problèmes d'optimisation mathématique, et les algorithmes associés pour les résoudre. L'algorithme central utilisé dans de nombreux solveurs d'optimisation globale pour les problèmes MINLP est l'algorithme de séparation et évaluation. La clé du succès de l'algorithme de séparation et évaluation réside dans l'utilisation de relaxations des problèmes d'optimisation, qui sont essentielles pour obtenir des bornes duales efficaces.Cependant, la construction de relaxations efficaces dépend des structures spécifiques des problèmes d'optimisation. Dans la première partie de cette thèse, nous présentons un aperçu complet des outils de relaxation structurelle adaptés aux problèmes MINLP structurés liés àdifférents domaines d’applications. Ces outils englobent des relaxations à partir de formulations étendues, des relaxations par sous-modularité, des relaxations utilisant une approximation linéaire par morceaux et des renforcements de relaxation via des coupes d'intersection. Nous développons de nouveaux résultats théoriques avancés basés sur ces outils. Dans la deuxième partie, nous utilisons ces techniques de relaxation pour aborder divers problèmes d'optimisation. Nous explorons les plans coupants pour la programmation signoïdale. Nous proposons des coupes d'intersection pour améliorer les relaxations linéaire des problèmes d'optimisation sous-modulaire.Nous étudions les relaxations de Dantzig-Wolfe pour un problème de programmation linéaire à variables mixtes dans le routage de réseaux sans fil et un problème MINLP dans le binpacking sous-modulaire. Enfin, nous étudions la technique de relaxation big-M appliquée aux fonctions linéaires par morceaux dans le problème de couverture continue sur un réseau.Les travaux réalisés durant cette thèse de doctorat contribuent à l’avancement des approches de la programmation non linéaire en nombre entiers et des méthodes d’optimisation connexes.En effet la combinaison des études ...