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

Abstract

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

How to cite

top

Billionnet, 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
  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.  
  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.  
  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.  
  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.  
  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.  
  11. H. Li, A Global approach for general fractional programming. Eur. J. Oper. Res.73 (1994) 590–596.  
  12. A. Nagih and G. Plateau, A partition algoritm for 0-1 hyperbolic programming problems. Investigacion Operativa9 (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.  
  14. T. Radzik, Fractional combinatorial optimization, in Handb. Combin. Optim., edited by Z.-Z. Du and P. Paradaloas Kluwer Academic Publishers (1998) 429–478.  
  15. A.L. Saipe, Solving a 0-1 hyperbolic program by branch-and-bound. Naval Res. Logist. Quart.22 (1975) 397–416.  
  16. S. Schaible and T. Ibaraki, Fractional programming. Eur. J. Oper. Res.12 (1983) 325–338.  
  17. S. Schaible, Fractional programming, in Handb global Optim., edited by R. Horst and P. Paradalos. Kluwer Academic Publishers (1995) 495–608.  
  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).  
  20. T. Wu, A note on a global approach for general 0-1 fractional programming. Eur. J. Oper. Res.101 (1997) 229–223.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.