RESOLUTION D'UN PROBLEME COMBINATOIRE FRACTIONNAIRE PAR LA PROGRAMMATION LINEAIRE MIXTE

摘要

Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0-1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work in the literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer programming solver. The second one is based on a specialized branch and bound algorithm that reformulates more precisely the problem at every node of search tree. We also propose a heuristic method and we exploit the obtained solution in order to improve the first strategy. We present computational experiments that allow to compare the different approaches.%Les programmes mathématiques fractionnaires apparaissent dans de nombreux domaines de la recherche opérationnelle, de l'informatique et de l'économie. Nous considérons dans ce papier le problème de la maximisation de la somme de plusieurs ratios hyperboliques en variables 0-1 (SRH). Contrairement à la maximisation d'un seul ratio, très peu d'auteurs se sont intéressés à ce problème. Nous proposons deux formulations de SRH par des programmes linéaires en variables mixtes et deux stratégies différentes pour résoudre ces programmes. La première consiste à appliquer directement un outil général de programmation linéaire en variables mixtes et la deuxième est fondée sur un algorithme de branch and bound spécifique qui utilise une réécriture plus précise des programmes en chaque noud de l'arbre de recherche. Nous proposons également une résolution de SRH par une méthode heiristique et nous exploitons la solution ainsi obtenue pour améliorer la première stratégie. Nous présentons des résultats expérimentaux permettant de comparer les différentes approches.