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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro:2006013/
[1] , and, The set covering problem with linear fractional functional. Indian J. Pure Appl. Math. 8 (1977) 578-588. | Zbl
[2] , Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem. Inform. Syst. Oper. Res. 40 (2002) 97-110.
[3] , Modélisation et résolution de problèmes d'optimisation combinatoire par la programmation linéaire en variables mixtes. rapport de Thèse, CNAM, Paris (2003).
[4] and, Optimising the sum of linear fractional functions. Adv. Global Optim. (1992) 221-258.
[5] and, Solving the sum-of-ratios problem by an interior-point method. J. Global Optim. 19 (2001) 83-102.
[6] and, A linear programming approach to the cutting stock problem. Oper. Res. 11 (1963) 52-53. | Zbl
[7] , and, Boolean query optimization and the 0-1 hyperbolic sum problem. Ann. Math. Artif. Intell. 1 (1990) 97-109. | Zbl
[8] , and, Hyperbolic 0-1 programming and information retrieval. Math. Program. 52 (1991) 255-263. | Zbl
[9] Ilog, Inc., Cplex Division, Using the cplex callable Library. Version 6.0 (1998).
[10] and, Attribution games. Naval Res. Logistics Quart. 3 (1956) 71-94. | Zbl
[11] , A Global approach for general fractional programming. Eur. J. Oper. Res. 73 (1994) 590-596. | Zbl
[12] and, A partition algoritm for 0-1 hyperbolic programming problems. Investigacion Operativa 9 (1999) 167-178.
[13] and, Problèmes fractionnaires : applications et méthodes de résolution. RAIRO Oper. Res. 33 (1999) 383-419. | Numdam | MR | Zbl
[14] , Fractional combinatorial optimization, in Handb. Combin. Optim., edited by Z.-Z. Du and P. Paradaloas Kluwer Academic Publishers (1998) 429-478. | Zbl
[15] , Solving a 0-1 hyperbolic program by branch-and-bound. Naval Res. Logist. Quart. 22 (1975) 397-416. | Zbl
[16] and, Fractional programming. Eur. J. Oper. Res. 12 (1983) 325-338. | Zbl
[17] , Fractional programming, in Handb global Optim., edited by R. Horst and P. Paradalos. Kluwer Academic Publishers (1995) 495-608. | Zbl
[18] , LINDO USER'S MANUAL : Release 5.0, The Scientific Press, San Francisco (1991).
[19] , Fractional Programming. Kluwer Academic Publishers (1997). | MR | Zbl
[20] , A note on a global approach for general 0-1 fractional programming. Eur. J. Oper. Res. 101 (1997) 229-223. | Zbl
Cité par Sources :
