no. 2
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.

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.

DOI : 10.1051/ro:2006013
Mots clés : optimisation combinatoire fractionnaire, somme de ratios hyperboliques, programmation linéaire en variables mixtes, branch-and-bound, expérimentation 
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro:2006013/

[1] S.R. Arora, K. Swarup and M.C. Puri, The set covering problem with linear fractional functional. Indian J. Pure Appl. Math. 8 (1977) 578-588. | Zbl

[2] A. Billionnet, Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem. Inform. Syst. Oper. Res. 40 (2002) 97-110.

[3] K. Djebali, 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] J.E. Falk and S.W. Paloscay, Optimising the sum of linear fractional functions. Adv. Global Optim. (1992) 221-258.

[5] R.W. Freund and F. Jarre, Solving the sum-of-ratios problem by an interior-point method. J. Global Optim. 19 (2001) 83-102.

[6] P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem. Oper. Res. 11 (1963) 52-53. | Zbl

[7] P. Hansen, M.V. Poggi De Aragao and C.C. Ribeiro, Boolean query optimization and the 0-1 hyperbolic sum problem. Ann. Math. Artif. Intell. 1 (1990) 97-109. | Zbl

[8] P. Hansen, M.V. Poggi De Aragao and C.C. Ribeiro, 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] J.R. Isbell and W.H. Marlow, Attribution games. Naval Res. Logistics Quart. 3 (1956) 71-94. | Zbl

[11] H. Li, A Global approach for general fractional programming. Eur. J. Oper. Res. 73 (1994) 590-596. | Zbl

[12] A. Nagih and G. Plateau, A partition algoritm for 0-1 hyperbolic programming problems. Investigacion Operativa 9 (1999) 167-178.

[13] A. Nagih and G. Plateau, Problèmes fractionnaires : applications et méthodes de résolution. RAIRO Oper. Res. 33 (1999) 383-419. | Numdam | MR | Zbl

[14] T. Radzik, Fractional combinatorial optimization, in Handb. Combin. Optim., edited by Z.-Z. Du and P. Paradaloas Kluwer Academic Publishers (1998) 429-478. | Zbl

[15] A.L. Saipe, Solving a 0-1 hyperbolic program by branch-and-bound. Naval Res. Logist. Quart. 22 (1975) 397-416. | Zbl

[16] S. Schaible and T. Ibaraki, Fractional programming. Eur. J. Oper. Res. 12 (1983) 325-338. | Zbl

[17] S. Schaible, Fractional programming, in Handb global Optim., edited by R. Horst and P. Paradalos. Kluwer Academic Publishers (1995) 495-608. | Zbl

[18] L. Scharge, LINDO USER'S MANUAL : Release 5.0, The Scientific Press, San Francisco (1991).

[19] I.M. Stancu-Minasian, Fractional Programming. Kluwer Academic Publishers (1997). | MR | Zbl

[20] T. Wu, A note on a global approach for general 0-1 fractional programming. Eur. J. Oper. Res. 101 (1997) 229-223. | Zbl

Cité par Sources :