Méthodes intérieures en programmation linéaire : élaboration et mise en œuvre de procédures de projection exacte et approchée
Institution:
Paris 9Disciplines:
Directors:
Abstract EN:
The thesis addresses the problem of the efficiency improvement of Karmarkar's algorithm. Different methods of both exact and approximate projections for solving the multicommodity network flow problems have been proposed. Other already existing methods have also been analyzed. Although the convergence analysis of the original algorithm has been established only in a zero optimum case, we propose several methods for more general case. Heuristical algorithm has been suggested that ensures fast convergence under the supplementary condition imposed on the step selection. Additionally, the method of Todd and Burrell has been implemented. Two approximate projection methods have been proposed to reduce the average time per iteration. The first one has been based on the observation that the angle of the objective gradient and its projection must always be acute. It has been implemented in two ways: the one exploiting the problem sparsity and the other being a variant of conjugate gradient method with a specific termination condition. Numerical results especially for the first phase are encouraging. In the second method of approximate projection, the basis of the null space of the linear operator is represented explicitly. Computational results proved that the last method outperformed other implementations of the Karmarkar's algorithm.
Abstract FR:
Nous avons, au cours de cette thèse, travaillé à l'amélioration des performances de l'algorithme de Karmarkar et avons élaboré et mis en œuvre des procédures de projection exacte et approchée pour la résolution de problème de multi flot compatible de coût minimum. Un travail de synthèse des méthodes existantes a été, par ailleurs, réalisé. La convergence théorique de l'algorithme n'étant assurée que lorsque le programme linéaire vérifie l'hypothèse de nullité de l'optimum, nous avons expérimenté différentes techniques élargissant le domaine d'application de cette méthode. Nous avons ainsi défini une heuristique qui, associée à une stratégie particulière de choix de pas de déplacement, permet une bonne convergence de l'algorithme. Nous avons, par ailleurs, implémenté la méthode de Todd et Burrell. Pour réduire considérablement le temps d'exécution de chaque itération, nous avons défini deux projections approchées. La première est née de la propriété d7auite de l'angle entre le gradient de la fonction objectif et le vecteur projeté. Pour la calculer, nous avons implémenté deux méthodes, l'une mettant en œuvre des techniques évoluées d'exploitation de creux des matrices, l'autre associant un test d'arrêt optimal à l'algorithme du gradient conjugué. Les résultats obtenus ont été très encourageants en première phase. La deuxième procédure utilise une méthode vectorielle. Son expérimentation a révélé le caractère compétitif de cette variante avec des logiciels dérivés de l'algorithme de Karmarkar.