Forschungsleitung (Direction de recherche) : 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.

Publikationen 2003-2012