A Hybrid Direction Method for Linear Fractional Programming
Keywords:
Linear Fractional Programming, Simplex Method, Adaptive Method, Hybrid Direction, Bounded Variables, Numerical Experiments
Abstract
In this article, we propose a new method for solving Linear Fractional Programming (LFP) problems with bounded variables. The proposed algorithm passes from a support feasible solution to a better one following the feasible direction proposed in [K. Djeloud, M. Bentobache and M. O. Bibi, A new method with hybrid direction for linear programming, Concurrency and Computation, Practice and Experience 33 (1), 2021]. Optimality and suboptimality criteria which allow to stop the algorithm when an optimal or suboptimal solution is achieved were stated and proved. Then, a new method called a Hybrid Direction Method (HDM) is described and a numerical example is given for illustration purpose. In order to compare our method to the classical approaches, we develop an implementation with the Matlab programming language. The obtained numerical results on solving 120 randomly generated LFP test problems show that HDM with long step rule is competitive with the primal simplex method and the interior-points method implemented in Matlab.References
1. A. Andjouh, and M. O. Bibi, Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems,
J Optim Theory Appl, vol. 192, no. 1, pp. 360–378, 2022.
2. M. Azi, and M. O. Bibi, Optimal control of a dynamical system with intermediate phase constraints and applications in cash
management, Numerical Algebra, Control and Optimization, vol. 12, no. 2, pp. 279–291, 2022.
3. E. B. Bajalinov, On the economic sense of dual Variables in linear-Fractional Programming, Ekonomika i matematicheskie metody,
vol. 24, pp. 558–561, 1988 (in Russian).
4. E. B. Bajalinov, On concordance of the economic interests, Izvestia Akademii Nauk Kirgizskoi SSR, vol. 3, pp. 558–561, 1990 (in
Russian).
5. J. Awerjcewicz, Linear-Fractional Programming: Theory, Methods, Applications and Software, Applied optimization, Springer,
University of Florida, USA, 2003.
6. M. Bentobache, and M. O. Bibi, A two-phase support method for solving linear programs: Numerical experiments, Mathematical
Problems in Engineering, 28 pages, Article ID 482193, doi:10.1155/2012/482193, 2012.
7. M. Bentobache, On mathematical methods of linear and quadratic probgramming, PhD Dissertation, University of Bejaia, Bejaia,
Algeria, 2013 (in French).
8. M. Bentobache, and M. O. Bibi, A hybrid direction algorithm with long step rule for linear programming: Numerical experiments,
In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management
Sciences. Advances in Intelligent Systems and Computing, Springer, Cham, vol. 359, pp. 333–344, 2015.
9. M. Bentobache, and M. O. Bibi, Methodes Num ´ eriques de la Programmation Lin ´ eaire et Quadratique: Th ´ eorie et Algorithmes ´ ,
Presses Academiques Francophones, Allemagne, 2016. ´
10. M. O. Bibi, Optimization of a linear dynamic system with double terminal constraints on the trajectories, Optimization, vol. 30, no.
4, pp. 359–366, 1994.
11. M. O. Bibi, Support method for solving a linear-quadratic problem with polyhedral constraints on control, Optimization, vol. 37,
no. 2, pp. 139–147, 1996.
12. M. O. Bibi, and M. Bentobache, A hybrid direction algorithm for solving linear programs, International Journal of Computer
Mathematics, vol. 92, no. 2, pp. 200–216, 2015.
13. M. O. Bibi, N. Ikheneche, and M. Bentobache, A hybrid direction algorithm for solving a convex quadratic problem, International
Journal of Mathematics in Operational Research, vol. 16, no. 2, pp. 159–178, 2020.
Stat., Optim. Inf. Comput. Vol. x, Month 202xM. A. HAKMI, M. BENTOBACHE AND M. O. BIBI 25
14. M. O. Bibi, H. Boussouira, and A. Laouar, Solution of an integer linear programming problem via a primal dual method combined
with a heuristic, International Journal of Mathematical Modelling and Numerical Optimisation, vol. 12, no. 1, pp. 69–87, 2022.
15. B. Brahmi, and M. O. Bibi, Dual support method for solving convex quadratic programs, Optimization, vol. 59, no. 6, pp. 851–872,
2010.
16. A. Charnes, and W. W. Cooper, Programming with Linear Fractional Functionals, Naval Res. Logistics Quart, vol. 9, no. 3-4, pp.
l81–186, 1962.
17. G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963.
18. K. Djeloud, M. Bentobache, and M. O. Bibi, A new method with hybrid direction for linear programming, Concurrency and
Computation, Practice and Experience, vol. 33, no. 1, pp. doi: 10.1002/cpe.5836, 2021.
19. W. Dinkelbach, Die maximierung eines quotienten zweier linearer funklionen unter linearen nebenbedingungen,
Wahrscheinlichkeitstheorie, vol. 1, no. 2, pp. 141–145, 1962.
20. L. F. Dezhurko, and F. T. Long, On the methods of the resolution of the general problem of LFP, Doklady AN BSSR,vol. 27, pp.
595–598, 1983 (in Russian).
21. R. Gabasov, and F. M. Kirillova, Methods of linear programming, Vol. 1, 2 and 3, Edition of the Minsk University, 1977, 1978, 1980
(in Russian).
22. R. Gabasov, and L. F. Dezhurko, An adaptive method of solution of the general fractional-linear programming problem, Doklady
AN BSSR, vol. 29, no. 8, pp. 685–687, 1985 (in Russian).
23. R. Gabasov, F. M. Kirillova, and O. I. Kostyukova, Solution of linear quadratic extremal problems, Soviet Mathematics Doklady,
vol. 31, pp. 99–103, 1985.
24. R. Gabasov, F. M. Kirillova, and S. V. Prischepova, Optimal Feedback Control, Springer-Verlag, London, 1995.
25. F. Ghellab, and M. O. Bibi, Optimality and suboptimality criteria in a quadratic problem of optimal control with a piecewise linear
entry, International Journal of Mathematics in Operational Research, vol. 19, no. 1, pp. 1–18, 2021.
26. R. Guerbane, and M. O. Bibi, Primal-dual method for a linear program with hybrid direction, International Journal of Mathematics
in Operational Research, vol. 23, no. 3, pp. 316–343, 2022.
27. M. A. Hakmi, Methode de support pour la résolution des problèmes d’optimisation fractionnaire linéaire, Memoire de Magistere
en Mathematiques, Ecole Normale Supérieure de Laghouat, 2017.
28. T. Illes, A. Szirmai, and T. Terlaky, ´ The finite criss-cross method for hyperbolic programming, European Journal of Operational
Research, vol. 114, no. 1, pp. 198–214, 1999.
29. N. Khimoum, and M. O. Bibi, Primal-dual method for solving a linear-quadratic multi-input optimal control problem, Optimization
Letters, vol. 14, no. 3, pp. 653–669, 2020.
30. E. A. Kostina, and O. I. Kostyukova, An algorithm for solving quadratic programming problems with linear equality and inequality
constraints, Computational Mathematics and Mathematical Physics, vol. 41, no. 7, pp. 960–973, 2001.
31. E.A. Kostina, The long step ru le in the bounded-variable dual simplex method: Numerical experiments, Mathematical Methods of
Operations Research, vol. 55, no. 3, pp. 413–429, 2002.
32. B. Martos, Hyperbolic programming, Publ. Math. Inst., Hungarian Academy of Sciences, vol. 5, pp. 386–406, 1960.
33. B. Martos, Hyperbolic programming, Naval Research Logistics Quarterly, vol. 11, pp. 135–155, 1964.
34. A. Nagih, and G. Plateau, Problemes fractionnaires: Tour d’horizon sur les applications et méthodes de résolution ´ , RAIRO Oper.
Res., vol. 33, no. 4, pp. 383–419, 1999.
35. A.S. Nemirovski, The long-step method of analytical centers for fractional problems, Mathematical Programming, vol. 77, no. 2,
pp. l91–224, 1997.
36. P. Pandian, and M. Jayalakshmi, On solving linear fractional programming problems, Modern Applied Science, vol. 7, no. 6, pp.
90–100, 2013.
37. S. Radjef, and M. O. Bibi, An effective generalization of the direct support method in quadratic convex programming, Applied
Mathematical Sciences, vol. 6, no. 31, pp. 1525–1540, 2012.
38. S. Radjef, and M. O. Bibi, A new algorithm for linear multiobjective programming problems with bounded variables, Arabian
Journal of Mathematics, vol. 3, no. 1, pp. 79–92, 2014.
39. S. Saha, M. Hossain, M. Uddin, and R. Mondal, A new approach of solving linear fractional programming problem (LFP) by using
computer algorithm, Open Journal of Optimization, vol. 4, pp. 74–86, 2015.
40. S. Schaible, Fractional programming : applications and algorithms, European Journal of Operational Research, vol. 7, no. 2, pp.
111–120, 1981.
41. I. M. Stancu-Minasian, Fractional Programming : Theory, Methods and Applications, Kluwer Academic Publishers, 1997.
42. S. F. Tantawy, A new procedure for solving linear fractional programming problems, Mathematical and Computer Modelling, vol.
48, no. 5-6, pp. 969–973, 2008.
43. T. Terlaky, Interior Point Methods in Mathematical Programming, Kluwer academic publichers, Boston-London-Dordrecht, Delft,
The Netherlands, 1996.
44. M. A. Zaitri, M. O. Bibi, and M. Bentobache, A hybrid direction algorithm for solving optimal control problems, Cogent
Mathematics & Statistics, vol. 6, no. 1, Article ID 1612614, doi: 10.1080/25742558.2019.1612614, 2019
J Optim Theory Appl, vol. 192, no. 1, pp. 360–378, 2022.
2. M. Azi, and M. O. Bibi, Optimal control of a dynamical system with intermediate phase constraints and applications in cash
management, Numerical Algebra, Control and Optimization, vol. 12, no. 2, pp. 279–291, 2022.
3. E. B. Bajalinov, On the economic sense of dual Variables in linear-Fractional Programming, Ekonomika i matematicheskie metody,
vol. 24, pp. 558–561, 1988 (in Russian).
4. E. B. Bajalinov, On concordance of the economic interests, Izvestia Akademii Nauk Kirgizskoi SSR, vol. 3, pp. 558–561, 1990 (in
Russian).
5. J. Awerjcewicz, Linear-Fractional Programming: Theory, Methods, Applications and Software, Applied optimization, Springer,
University of Florida, USA, 2003.
6. M. Bentobache, and M. O. Bibi, A two-phase support method for solving linear programs: Numerical experiments, Mathematical
Problems in Engineering, 28 pages, Article ID 482193, doi:10.1155/2012/482193, 2012.
7. M. Bentobache, On mathematical methods of linear and quadratic probgramming, PhD Dissertation, University of Bejaia, Bejaia,
Algeria, 2013 (in French).
8. M. Bentobache, and M. O. Bibi, A hybrid direction algorithm with long step rule for linear programming: Numerical experiments,
In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management
Sciences. Advances in Intelligent Systems and Computing, Springer, Cham, vol. 359, pp. 333–344, 2015.
9. M. Bentobache, and M. O. Bibi, Methodes Num ´ eriques de la Programmation Lin ´ eaire et Quadratique: Th ´ eorie et Algorithmes ´ ,
Presses Academiques Francophones, Allemagne, 2016. ´
10. M. O. Bibi, Optimization of a linear dynamic system with double terminal constraints on the trajectories, Optimization, vol. 30, no.
4, pp. 359–366, 1994.
11. M. O. Bibi, Support method for solving a linear-quadratic problem with polyhedral constraints on control, Optimization, vol. 37,
no. 2, pp. 139–147, 1996.
12. M. O. Bibi, and M. Bentobache, A hybrid direction algorithm for solving linear programs, International Journal of Computer
Mathematics, vol. 92, no. 2, pp. 200–216, 2015.
13. M. O. Bibi, N. Ikheneche, and M. Bentobache, A hybrid direction algorithm for solving a convex quadratic problem, International
Journal of Mathematics in Operational Research, vol. 16, no. 2, pp. 159–178, 2020.
Stat., Optim. Inf. Comput. Vol. x, Month 202xM. A. HAKMI, M. BENTOBACHE AND M. O. BIBI 25
14. M. O. Bibi, H. Boussouira, and A. Laouar, Solution of an integer linear programming problem via a primal dual method combined
with a heuristic, International Journal of Mathematical Modelling and Numerical Optimisation, vol. 12, no. 1, pp. 69–87, 2022.
15. B. Brahmi, and M. O. Bibi, Dual support method for solving convex quadratic programs, Optimization, vol. 59, no. 6, pp. 851–872,
2010.
16. A. Charnes, and W. W. Cooper, Programming with Linear Fractional Functionals, Naval Res. Logistics Quart, vol. 9, no. 3-4, pp.
l81–186, 1962.
17. G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963.
18. K. Djeloud, M. Bentobache, and M. O. Bibi, A new method with hybrid direction for linear programming, Concurrency and
Computation, Practice and Experience, vol. 33, no. 1, pp. doi: 10.1002/cpe.5836, 2021.
19. W. Dinkelbach, Die maximierung eines quotienten zweier linearer funklionen unter linearen nebenbedingungen,
Wahrscheinlichkeitstheorie, vol. 1, no. 2, pp. 141–145, 1962.
20. L. F. Dezhurko, and F. T. Long, On the methods of the resolution of the general problem of LFP, Doklady AN BSSR,vol. 27, pp.
595–598, 1983 (in Russian).
21. R. Gabasov, and F. M. Kirillova, Methods of linear programming, Vol. 1, 2 and 3, Edition of the Minsk University, 1977, 1978, 1980
(in Russian).
22. R. Gabasov, and L. F. Dezhurko, An adaptive method of solution of the general fractional-linear programming problem, Doklady
AN BSSR, vol. 29, no. 8, pp. 685–687, 1985 (in Russian).
23. R. Gabasov, F. M. Kirillova, and O. I. Kostyukova, Solution of linear quadratic extremal problems, Soviet Mathematics Doklady,
vol. 31, pp. 99–103, 1985.
24. R. Gabasov, F. M. Kirillova, and S. V. Prischepova, Optimal Feedback Control, Springer-Verlag, London, 1995.
25. F. Ghellab, and M. O. Bibi, Optimality and suboptimality criteria in a quadratic problem of optimal control with a piecewise linear
entry, International Journal of Mathematics in Operational Research, vol. 19, no. 1, pp. 1–18, 2021.
26. R. Guerbane, and M. O. Bibi, Primal-dual method for a linear program with hybrid direction, International Journal of Mathematics
in Operational Research, vol. 23, no. 3, pp. 316–343, 2022.
27. M. A. Hakmi, Methode de support pour la résolution des problèmes d’optimisation fractionnaire linéaire, Memoire de Magistere
en Mathematiques, Ecole Normale Supérieure de Laghouat, 2017.
28. T. Illes, A. Szirmai, and T. Terlaky, ´ The finite criss-cross method for hyperbolic programming, European Journal of Operational
Research, vol. 114, no. 1, pp. 198–214, 1999.
29. N. Khimoum, and M. O. Bibi, Primal-dual method for solving a linear-quadratic multi-input optimal control problem, Optimization
Letters, vol. 14, no. 3, pp. 653–669, 2020.
30. E. A. Kostina, and O. I. Kostyukova, An algorithm for solving quadratic programming problems with linear equality and inequality
constraints, Computational Mathematics and Mathematical Physics, vol. 41, no. 7, pp. 960–973, 2001.
31. E.A. Kostina, The long step ru le in the bounded-variable dual simplex method: Numerical experiments, Mathematical Methods of
Operations Research, vol. 55, no. 3, pp. 413–429, 2002.
32. B. Martos, Hyperbolic programming, Publ. Math. Inst., Hungarian Academy of Sciences, vol. 5, pp. 386–406, 1960.
33. B. Martos, Hyperbolic programming, Naval Research Logistics Quarterly, vol. 11, pp. 135–155, 1964.
34. A. Nagih, and G. Plateau, Problemes fractionnaires: Tour d’horizon sur les applications et méthodes de résolution ´ , RAIRO Oper.
Res., vol. 33, no. 4, pp. 383–419, 1999.
35. A.S. Nemirovski, The long-step method of analytical centers for fractional problems, Mathematical Programming, vol. 77, no. 2,
pp. l91–224, 1997.
36. P. Pandian, and M. Jayalakshmi, On solving linear fractional programming problems, Modern Applied Science, vol. 7, no. 6, pp.
90–100, 2013.
37. S. Radjef, and M. O. Bibi, An effective generalization of the direct support method in quadratic convex programming, Applied
Mathematical Sciences, vol. 6, no. 31, pp. 1525–1540, 2012.
38. S. Radjef, and M. O. Bibi, A new algorithm for linear multiobjective programming problems with bounded variables, Arabian
Journal of Mathematics, vol. 3, no. 1, pp. 79–92, 2014.
39. S. Saha, M. Hossain, M. Uddin, and R. Mondal, A new approach of solving linear fractional programming problem (LFP) by using
computer algorithm, Open Journal of Optimization, vol. 4, pp. 74–86, 2015.
40. S. Schaible, Fractional programming : applications and algorithms, European Journal of Operational Research, vol. 7, no. 2, pp.
111–120, 1981.
41. I. M. Stancu-Minasian, Fractional Programming : Theory, Methods and Applications, Kluwer Academic Publishers, 1997.
42. S. F. Tantawy, A new procedure for solving linear fractional programming problems, Mathematical and Computer Modelling, vol.
48, no. 5-6, pp. 969–973, 2008.
43. T. Terlaky, Interior Point Methods in Mathematical Programming, Kluwer academic publichers, Boston-London-Dordrecht, Delft,
The Netherlands, 1996.
44. M. A. Zaitri, M. O. Bibi, and M. Bentobache, A hybrid direction algorithm for solving optimal control problems, Cogent
Mathematics & Statistics, vol. 6, no. 1, Article ID 1612614, doi: 10.1080/25742558.2019.1612614, 2019
Published
2025-01-02
How to Cite
Hakmi, M. A., Bentobache, M., & Bibi, M. O. (2025). A Hybrid Direction Method for Linear Fractional Programming. Statistics, Optimization & Information Computing. https://doi.org/10.19139/soic-2310-5070-2245
Issue
Section
Research Articles
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
