Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T11:01:20.895Z Has data issue: false hasContentIssue false
  • English
  • Français

Solution of a fractional combinatorial optimization problem by mixed integer programming

Published online by Cambridge University Press:  12 October 2006

Alain Billionnet  and
Karima Djebali
Alain Billionnet
Affiliation:
CEDRIC-IIE, 18 allée Jean Rostand, 91025 Evry Cedex, France;
Karima Djebali
Affiliation:
CEDRIC-IIE, 18 allée Jean Rostand, 91025 Evry Cedex, France;
Get access

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

Keywords

Optimisation combinatoire fractionnairesomme de ratios hyperboliquesprogrammation linéaire en variables mixtesbranch-and-boundexpérimentation.
Type
Research Article
Information
RAIRO - Operations Research , Volume 40 , Issue 2: ROADEF 03 , April 2006 , pp. 97 - 111
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arora, S.R., Swarup, K. and Puri, M.C., The set covering problem with linear fractional functional. Indian J. Pure Appl. Math. 8 (1977) 578–588.
Billionnet, A., Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem. Inform. Syst. Oper. Res. 40 (2002) 97–110. CrossRef
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.
Freund, R.W. and Jarre, F., Solving the sum-of-ratios problem by an interior-point method. J. Global Optim. 19 (2001) 83–102. CrossRef
Gilmore, P.C. and Gomory, R.E., A linear programming approach to the cutting stock problem. Oper. Res. 11 (1963) 52–53. CrossRef
Hansen, P., Poggi De, M.V. Aragao and C.C. Ribeiro, Boolean query optimization and the 0-1 hyperbolic sum problem. Ann. Math. Artif. Intell. 1 (1990) 97–109. CrossRef
P. Hansen, M.V. Poggi De Aragao and C.C. Ribeiro, Hyperbolic 0-1 programming and information retrieval. Math. Program. 52 (1991) 255–263.
Ilog, Inc., Cplex Division, Using the cplex callable Library. Version 6.0 (1998).
Isbell, J.R. and Marlow, W.H., Attribution games. Naval Res. Logistics Quart. 3 (1956) 71–94. CrossRef
Li, H., Global, A approach for general fractional programming. Eur. J. Oper. Res. 73 (1994) 590–596. CrossRef
Nagih, A. and Plateau, G., A partition algoritm for 0-1 hyperbolic programming problems. Investigacion Operativa 9 (1999) 167–178.
Nagih, A. and Plateau, G., Problèmes fractionnaires : applications et méthodes de résolution. RAIRO Oper. Res. 33 (1999) 383-419. CrossRef
T. Radzik, Fractional combinatorial optimization, in Handb. Combin. Optim., edited by Z.-Z. Du and P. Paradaloas Kluwer Academic Publishers (1998) 429–478.
Saipe, A.L., Solving a 0-1 hyperbolic program by branch-and-bound. Naval Res. Logist. Quart. 22 (1975) 397–416. CrossRef
Schaible, S. and Ibaraki, T., Fractional programming. Eur. J. Oper. Res. 12 (1983) 325–338. CrossRef
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).
Wu, T., A note on a global approach for general 0-1 fractional programming. Eur. J. Oper. Res. 101 (1997) 229–223. CrossRef