Voir la notice de l'article provenant de la source Numdam
Les programmes mathématiques fractionnaires apparaissent dans de nombreux domaines de la recherche opérationnelle, de l'inform-atique 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.
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.
@article{RO_2006__40_2_97_0,
author = {Billionnet, Alain and Djebali, Karima},
title = {R\'esolution d'un probl\`eme combinatoire fractionnaire par la programmation lin\'eaire mixte},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {97--111},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ro:2006013},
zbl = {1137.90017},
language = {fr},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2006013/}
}
TY - JOUR AU - Billionnet, Alain AU - Djebali, Karima TI - Résolution d'un problème combinatoire fractionnaire par la programmation linéaire mixte JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 97 EP - 111 VL - 40 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2006013/ DO - 10.1051/ro:2006013 LA - fr ID - RO_2006__40_2_97_0 ER -
%0 Journal Article %A Billionnet, Alain %A Djebali, Karima %T Résolution d'un problème combinatoire fractionnaire par la programmation linéaire mixte %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 97-111 %V 40 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2006013/ %R 10.1051/ro:2006013 %G fr %F RO_2006__40_2_97_0
Billionnet, Alain; Djebali, Karima. Résolution d'un problème combinatoire fractionnaire par la programmation linéaire mixte. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 97-111. doi: 10.1051/ro:2006013
Cité par Sources :