Groupe d’études et de recherche en analyse des décisions

Le chemin central tropical

Pascal Benchimol

La programmation linéaire consiste à minimiser une fonction linéaire sous des contraintes linéaires. Les méthodes de points intérieurs permettent de résoudre les problèmes de programmation linéaire. Ce sont des méthodes ayant une bonne complexité théorique tout en étant efficace en pratique. Elles consistent à suivre une courbe, appelée chemin central, menant à un optimum. En mathématiques tropicale, on modifie les opérations élémentaires: l'addition devient le maximum et la multiplication est remplacée par l'addition usuelle. Je m'intéresse à la résolution de la programmation linéaire tropicale: minimiser une fonction linéaire tropicale (linéaire pour les opérations max,+) sous des contraintes linéaires tropicales. Est-il possible de tropicaliser les méthodes de points intérieurs ? Pour répondre à cette question je vais donner un caractérisation du chemin central tropical.