An exact method for a discrete multiobjective linear fractional optimization

Chergui, M. E-A and Moulai, M. (2007): An exact method for a discrete multiobjective linear fractional optimization. Published in: Journal of Applied Mathematics and Decision Sciences (17 March 2008)

Abstract

Integer linear fractional programming problem with multiple objective MOILFP is an important field of research and has not received as much attention as did multiple objective linear fractional programming. In this work, we develop a branch and cut algorithm based on continuous fractional optimization, for generating the whole integer efficient solutions of the MOILFP problem. The basic idea of the computation phase of the algorithm is to optimize one of the fractional objective functions, then generate an integer feasible solution. Using the reduced gradients of the objective functions, an efficient cut is built and a part of the feasible domain not containing efficient solutions is truncated by adding this cut. A sample problem is solved using this algorithm, and the main practical advantages of the algorithm are indicated.

• Item Type: MPRA Paper
• Commentary on: Eprints 0 not found.
• Language: English
• Keywords: multiobjective programming, integer programming, linear fractional programming, branch and cut
• Subjects: C - Mathematical and Quantitative Methods > C4 - Econometric and Statistical Methods: Special Topics > C44 - Operations Research ; Statistical Decision Theory; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis

References

S. Schaible, “Fractional programming: applications and algorithms,” European Journal of Operational Research, vol. 7, no. 2, pp. 111–120, 1981.

A. Nagih and G. Plateau, “Problèmes fractionnaires: tour d’horizon sur les applications et méthodes de résolution,” RAIRO Operations Research, vol. 33, no. 4, pp. 383–419, 1999.

B. D. Craven, Fractional Programming, vol. 4 of Sigma Series in AppliedMathematics, Heldermann, Berlin, Germany, 1988.

I. M. Stancu-Minasian, Fractional Programming: Theory, Methods and Applications, vol. 409 of Mathematics and Its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1997.

R. Horst, P. M. Pardalos, and N. V. Thoai, Introduction to Global Optimization, vol. 48 of Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2nd edition, 2000.

J. B. G. Frenk and S. Schaible, “Fractional programming: Introduction and Applications,” in Encyclopedia of Optimization, C. A. Floudas and P. M. Pardalos, Eds., pp. 162–172, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.

I. M. Stancu-Minasian, “A sixth bibliography of fractional programming,” Optimization, vol. 55, no. 4, pp. 405–428, 2006.

I. M. Stancu-Minasian, “A fifth bibliography of fractional programming,” Optimization, vol. 45, no. 1–4, pp. 343–367, 1999.

R. E. Steuer, Multiple Criteria Optimization: Theory, Computation, and Application, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, New York, NY, USA, 1986.

A. Cambini and L. Martein, “Equivalence in linear fractional programming,” Optimization, vol. 23, no. 1, pp. 41–51, 1992.

A. Charnes and W. W. Cooper, “Programming with linear fractional functionals,” Naval Research Logistics Quarterly, vol. 9, no. 3-4, pp. 181–186, 1962.

D. Granot and F. Granot, “On integer and mixed integer fractional programming problems,” in Studies in Integer Programming, vol. 1 of Annals of Discrete Mathematics, pp. 221–231, North-Holland, Amsterdam, The Netherlands, 1977.

B. Martos, Nonlinear Programming: Theory and Method, North-Holland, Amsterdam, The Netherlands, 1975.

C. R. Seshan and V. G. Tikekar, “Algorithms for integer fractional programming,” Journal of the Indian Institute of Science, vol. 62, no. 2, pp. 9–16, 1980.

M. Abbas and M. Moulaï, “Integer linear fractional programming with multiple objective,” Journal of the Italian Operations Research Society, vol. 32, no. 103-104, pp. 15–38, 2002.

R. Caballero and M. Hern´andez, “The controlled estimation method in the multiobjective linear fractional problem,” Computers & Operations Research, vol. 31, no. 11, pp. 1821–1832, 2004.

A. Cambini, L. Martein, and I. M. Stancu-Minasian, “A survey of bicriteria fractional problems,” Advanced Modeling and Optimization, vol. 1, no. 1, pp. 9–46, 1999.

M. Chakraborty and S. Gupta, “Fuzzy mathematical programming formulti objective linear fractional programming problem,” Fuzzy Sets and Systems, vol. 125, no. 3, pp. 335–342, 2002.

J. P. Costa, “Computing non-dominated solutions in MOLFP,” European Journal of Operational Research, vol. 181, no. 3, pp. 1464–1475, 2007.

J. S. H. Kornbluth and R. E. Steuer, “Multiple objective linear fractional programming,” Management Science, vol. 27, no. 9, pp. 1024–1039, 1981.

B. Metev and D. Gueorguieva, “A simple method for obtaining weakly efficient points in multiobjective linear fractional programming problems,” European Journal of Operational Research, vol. 126, no. 2, pp. 386–390, 2000.

O. M. Saad and J. B. Hughes, “Bicriterion integer linear fractional programs with parameters in the objective functions,” Journal of Information & Optimization Sciences, vol. 19, no. 1, pp. 97–108, 1998.

M. Ehrgott and X. Gandibleux, “An annotated bibliography of multiobjective combinatorial optimization,” Report in Wissenschaftmathematik no. 62, Fachbereich Mathematik, Universitat Kaiserslautern, Kaiserslautern, Germany, 2000.

G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, New York, NY, USA, 1986.