# Solution of a fractional combinatorial optimization problem by mixed integer programming

Alain Billionnet; Karima Djebali

RAIRO - Operations Research (2006)

- Volume: 40, Issue: 2, page 97-111
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBillionnet, Alain, and Djebali, Karima. "Solution of a fractional combinatorial optimization problem by mixed integer programming." RAIRO - Operations Research 40.2 (2006): 97-111. <http://eudml.org/doc/249752>.

@article{Billionnet2006,

abstract = {
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.
},

author = {Billionnet, Alain, Djebali, Karima},

journal = {RAIRO - Operations Research},

keywords = {Optimisation combinatoire fractionnaire; somme de ratios hyperboliques; programmation linéaire en variables mixtes; branch-and-bound; expérimentation.},

language = {eng},

month = {10},

number = {2},

pages = {97-111},

publisher = {EDP Sciences},

title = {Solution of a fractional combinatorial optimization problem by mixed integer programming},

url = {http://eudml.org/doc/249752},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Billionnet, Alain

AU - Djebali, Karima

TI - Solution of a fractional combinatorial optimization problem by mixed integer programming

JO - RAIRO - Operations Research

DA - 2006/10//

PB - EDP Sciences

VL - 40

IS - 2

SP - 97

EP - 111

AB -
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.

LA - eng

KW - Optimisation combinatoire fractionnaire; somme de ratios hyperboliques; programmation linéaire en variables mixtes; branch-and-bound; expérimentation.

UR - http://eudml.org/doc/249752

ER -

## References

top- 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. Zbl0434.90093
- A. Billionnet, Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem. Inform. Syst. Oper. Res.40 (2002) 97–110.
- 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).
- J.E. Falk and S.W. Paloscay, Optimising the sum of linear fractional functions. Adv. Global Optim. (1992) 221–258.
- R.W. Freund and F. Jarre, Solving the sum-of-ratios problem by an interior-point method. J. Global Optim.19 (2001) 83–102. Zbl1168.90644
- P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem. Oper. Res.11 (1963) 52–53. Zbl0124.36307
- 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. Zbl0870.68048
- P. Hansen, M.V. Poggi De Aragao and C.C. Ribeiro, Hyperbolic 0-1 programming and information retrieval. Math. Program. 52 (1991) 255–263. Zbl0737.90044
- Ilog, Inc., Cplex Division, Using the cplex callable Library. Version 6.0 (1998).
- J.R. Isbell and W.H. Marlow, Attribution games. Naval Res. Logistics Quart.3 (1956) 71–94.
- H. Li, A Global approach for general fractional programming. Eur. J. Oper. Res.73 (1994) 590–596. Zbl0806.90119
- A. Nagih and G. Plateau, A partition algoritm for 0-1 hyperbolic programming problems. Investigacion Operativa9 (1999) 167–178.
- A. Nagih and G. Plateau, Problèmes fractionnaires : applications et méthodes de résolution. RAIRO Oper. Res.33 (1999) 383-419.
- T. Radzik, Fractional combinatorial optimization, in Handb. Combin. Optim., edited by Z.-Z. Du and P. Paradaloas Kluwer Academic Publishers (1998) 429–478. Zbl0934.90065
- A.L. Saipe, Solving a 0-1 hyperbolic program by branch-and-bound. Naval Res. Logist. Quart.22 (1975) 397–416.
- S. Schaible and T. Ibaraki, Fractional programming. Eur. J. Oper. Res.12 (1983) 325–338. Zbl0529.90088
- S. Schaible, Fractional programming, in Handb global Optim., edited by R. Horst and P. Paradalos. Kluwer Academic Publishers (1995) 495–608.
- L. Scharge, LINDO USER'S MANUAL: Release 5.0, The Scientific Press, San Francisco (1991).
- I.M. Stancu-Minasian, Fractional Programming. Kluwer Academic Publishers (1997).
- T. Wu, A note on a global approach for general 0-1 fractional programming. Eur. J. Oper. Res.101 (1997) 229–223. Zbl0916.90252

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.