Cônes de matrices et programmation mathématique : quelques applications
Institution:
NiceDisciplines:
Directors:
Abstract EN:
All along this dissertation we present our work related to the scope of integer linear programming. This works come from those done by L. Lovasz and A. Scrijver in [L. Lovasz and A. Scrijver : Cones of matrices , set functions and 0-1 optimizations, SIAM 1991]. In a first time we present extensively their works in order to make them easier to understand. Thus we show clearly the relations between integer programming and positive semi-definite programming. Then we derive from the Lovasz Schrijver a cutting plane algorithm solving linear integer programs. In a second time we present the most famous applications of positive semi-definite devoted pendant set and those of M. Goemans and D. Williamson to the maximum cut. Then we explain an application to the minimum cost flow subjected to end to end delay constraint. Latter we look for embeddings of lattices in convex cones and more precisely in the cones defined by L. Lovasz and A. Schrijver. We show that the two cones handled in the first part of the dissertation share the same unique Hilbert basis. At last we show that the latter cones can be viewed as subset of a cone of metrics, as an application we modelize the problem of the 2-connected subgraphs n this cone of metrics and define a positive semi-definite relaxation of this problem. In the annexes we explain a work done together with A. Jarry related to the minimum number of edges of a 2-connected r=graph with diameter constraints. A work done together with S. Bertrand and P. Mahey is also explained, it concerns the minimum cost flow in the special behavior of non-conservative flows.
Abstract FR:
Au cours de ce mémoire nous présentons nos travaux concernant la programmation linéaire en nombre entiers. Ces travaux sont inspirés de ceux développés par L. Lovasz et A. Schrijver en 1991 dans [L. Lovasz and A. Schrijver : Cones of matrices, set functions and 0-1 optimization, SIAM 1991]. Nous reprenons leurs travaux en les détaillant de sorte à les rendre plus facilement abordables. Nous mettons ainsi clairement en valeur les connexions qui existent entre la programmation linéaire en variables bivalentes et la programmation semi-définie positive. Nous dérivons de la construction de Lovasz et Schrijver un algorithme de coupes polyédrales pour résoudre les problèmes de programmation en nombres entiers. Dans un premier temps nous présentons les applications les plus importantes de la programmation semi-définie positive à la résolution de problèmes d’optimisation combinatoire : le travail de Lovasz concernant le problème de stable de poids maximum, et celui de M. Goemans et D. Williamson relatif au problème de la coupe de poids maximum. Puis nous présentons une application de la programmation semi-définie positive au problème du flot du coût minimum avec contrainte de longueur sur les chemins support de flot. Enfin nous nous intéressons au plongement de treillis dans les cônes convexes en recherchant les bases de Hilbert de ces cônes et lus précisément des cônes définis par Lovasz et Schrijver. Nous montrons notamment que ces deux cônes partagent une unique base de Hilbert après avoir vu que les matrices qu’ils contiennent peuvent s’obtenir comme mineurs des matrices semi-définies positives représentant les fonctions fortement décroissantes sur les treillis. En guise de conclusion, nous exposons un travail sur deux cônes de métriques, travail dans lequel nous définissons une relaxation semi-définie positive du problème du graphe partiel k-arrête connexe de poids minimum. En annexe nous présentons un travail effectué avec A. Jarry dans lequel une conjecture de Bollobas sur le nombre minimum d’arrêtes d’un graphe 2-connexe et de diamètre d et démontré. Nous présentons aussi un travail mené avec S. Bertrand et P. Mahey relatif au problème de routage de flux non-conservatif.