BONAMI Pierre
Supervision : Michel MINOUX
Algorithmes pour la résolution de programmes linéaires en nombres entiers généraux
Le but de ce travail est d'étudier de proposer et d'expérimenter des méthodes de plans coupants pour des programmes
en nombres entiers généraux prenant mieux en compte les structures des problèmes. Nous traitons du problème de séparation de la meilleure inégalité valide par le critère du ratio, et de différentes méthodes permettant d'approcher celle-ci par l'utilisation d'heuristiques, de relaxations mixtes et d'une nouvelle méthode de lifting relaxé. Nous abordons ensuite les problèmes de séparation au travers de la programmation disjonctive, en proposant notamment un méthode d'optimisation sur la fermeture élémentaire des coupes de ``Lift and Project''. Nous étudions ensuite les relaxations par reformulation linéarisation de type Sherali Adams avec une nouvelle méthode d'optimisation
combinant de façon originale décomposition et relaxation. Nous etudions aussi du point de vue théorique et pratique l'intéret de
la relaxation de Sherali-Adams par rapport à la fermeture élémentaire des coupes de lift and project. Enfin nous proposons et expérimentons plusieurs nouveaux schémas algorithmiques pour l'utilisation de coupes conditionnellement valides.
Defence : 10/21/2003
Jury members :
Cornuéjols Gérard, Université Aix-Marseille, Rapporteur
Gabrel Virginie, Université Paris IX-Dauphine, Examinatrice
Jaffray Jean-Yves, Université Pierre et Marie Curie (UMPC), Examinateur
Maculan Nelson, Université Fédérale de Rio de Janeiro, Rapporteur
Minoux Michel, Université Pierre et Marie Curie (UMPC), Directeur de thèse
2003-2012 Publications
-
2012
- P. Bonami, V. Nguyen, M. Klein, M. Minoux : “On the Solution of a Graph Partitioning Problem under Capacity Constraints”, Proceedings of ISCO 2012, vol. 7422, Lecture Notes in Computer Science, Athens, Greece, pp. 285-296 (2012)
-
2006
- P. Bonami, M. Minoux : “Exact MAX-2SAT solution via lift-and-project closure”, Operations Research Letters, vol. 34 (4), pp. 387-393, (Elsevier) (2006)
- P. Bonami, M. Minoux : “Multicommodity Network Flow Models and Algorithms in Telecommunications”, chapter in Handbook of Optimization in Telecommunications, pp. 163-184, (Kluwer Acad Publ.), (ISBN: 978-0-387-30662-9) (2006)
- M. Minoux, P. Bonami : “Une comparaison de quelques mĂ©thodes de gĂ©nĂ©ration d’inĂ©galitĂ©s valides pour des problèmes entiers 0-1 gĂ©nĂ©raux”, chapitre de Optimisation Combinatoire 3 : applications, (Hermès) (2006)
-
2005
- P. Bonami, M. Minoux : “Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation”, Discrete Optimization, vol. 2 (4), pp. 288-307, (Elsevier) (2005)
-
2003
- P. Bonami : “Algorithmes pour la rĂ©solution de programmes linĂ©aires en nombres entiers gĂ©nĂ©raux”, thesis, defence 10/21/2003, supervision Minoux, Michel (2003)
- P. Bonami, M. Minoux : “Utilisation d’inĂ©galitĂ©s conditionnellement valides en PLNE 0-1”, 5e Congrès de la SociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d'Aide Ă la DĂ©cision (ROADEF 2003), Avignon, France (2003)