×

zbMATH — the first resource for mathematics

Extensions of Dinkelbach’s algorithm for solving nonlinear fractional programming problems. (English) Zbl 0932.90043
Summary: Dinkelbach’s algorithm was developed to solve convex fractional programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of nonlinear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach’s algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems.
Dinkelbach’s extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied.
We have proposed two modifications to improve the speed-up of Dinkelbach’s algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications.
Computational experiments in linear fractional programming, integer linear fractional programming and nonlinear fractional programming to evaluate the efficiency of these methods have been carried out.

MSC:
90C32 Fractional programming
90C31 Sensitivity, stability, parametric optimization
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
Software:
MINOS
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arisawa, S., and S. E. Elmaghraby (1972). Optimal Time-Cost Trade-offs in GERT-Networks,Management Science 18589–599 · Zbl 0241.90063
[2] Bazaraa, S., J. J. Jarvis and H. D. Sherali (1990).Linear Programming and Network Flows, (2nd ed.), John Wiley & Sons Inc., New York, New York. · Zbl 0722.90042
[3] Bazaraa, S., H.D. Sherali and C.M. Shetty, (1993).Nonlinear Programming: Theory and Algorithms, (2nd ed.), John Wiley & Sons Inc., New York, New York. · Zbl 0774.90075
[4] Clarke, F. H., (1990), Optimization and Nonsmooth Analysis,SIAM, Philadelphia, Pennsylvania. · Zbl 0696.49002
[5] Chandra, S. and M. Cahndramoham (1980). A note on integer linear fractional programming.Naval Research Logistics Quarterly,27171–174 · Zbl 0437.90091
[6] Charnes, A. and W. Cooper, (1962). Programming with linear fractional.Naval Research Logistics Quarterly.9, 181–186. · Zbl 0127.36901
[7] De La Fuente O’Connor, J.L. (1993),Tecnologías Computacionales para Sistemas de Ecuaciones, Optimización Lineal y Entera, Reverté, Barcelona.
[8] Dinkelbach, W., (1967). On Nonlinear Fractional Programming,Management Science,13, 492–498. · Zbl 0152.18402
[9] Fukushima, M. and H. Mine, (1981). A Generalized Proximal Point Algorithm for certain Nonconvex Minimization Problems,International Journal of Systems Sciences,12, 989–1000. · Zbl 0467.65028
[10] Frank, M., and P. Wolfe, (1956) Algorithm for Quadratic Programming,Naval Research Logistics Quarterly,3 95–110
[11] Gopal, G., Kim C-K, and A. Weinrib, (1991) Algorithms for reconfigurable networks,Teletraffic and Datatraffic,13 341–347
[12] Horst, R., and H. Tuy, (1990),Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin and Heidelberg. · Zbl 0704.90057
[13] Hearn, D. W., S. Lawphongpanich and J.A. Ventura. (1987). Restricted Simplicial Decomposition: Computation and Extensions.Mathematical Programming Study,31 99–118. · Zbl 0636.90027
[14] Hearn, D.W., S. Lawphongpanich and J.A. Ventura and K. C. Yang. (1989). RSDNET-Restricted Simplicial Decomposition Network Code.European Journal of Operational Research,38 121–122.
[15] Householder, A. S., (1970). The numerical treatment of a single nonlinear equation.International series in pure and applied mathematics, Mc Graw-Hill, Inc., New York. · Zbl 0242.65047
[16] Isbell, J.R. and W. H. Marlow, (1956). Attrition Games,Naval Research Logistics Quarterly,3, 71–93. · Zbl 0122.15405
[17] Jagannathan R. (1966). One some properties of Programming Problems in Parametric form Pertaining to Fractional Programming,Management Science,12, 609–615. · Zbl 0143.21602
[18] Klingman, D., A. Napier and J. Stutz (1974). NETGEN-A Program for Generating Large-scale (Un) Capacitated Assignment, Transportation and Minimum Cost Flow Network Problems.Management Science,20 814–821. · Zbl 0303.90042
[19] Mangasarian, O. L. (1969). Nonlinear Fractional Programming.Journal of the Operations Research Society of Japan,12 1–10. · Zbl 0257.90043
[20] Martos, B. (1964). Hyperbolic programming.Naval Res. Logist. Quart. 3, 135–155. · Zbl 0131.18504
[21] Mond, B., (1981). On Algorithmic Equivalence in Linear Fractional Programming.Mathematics of Computation,37 185–187. · Zbl 0472.90065
[22] Murtagh, B. A. and M. A. Saunders, (1987).MINOS 5.1 User’s Guide. Systems Optimization Laboratory, Department of Operations Research, Stanford University.
[23] Pardalos, P.M., and S.A. Vavasis (1991). uadratic Programs with One Negative Eigen-Value is NP-Hard.Journal of Global Optimization,1 15–22. · Zbl 0755.90065
[24] Patrikson, M., (1993). Partial linearization methods in nonlinear programming.Journal of Optimization Theory and Applications,78, 227–246. · Zbl 0796.90058
[25] Rajendra, V., Aneja, Y.P. and K.P.K. Nair, (1990). Optimization of bicriterion quasi-concave function subject to linear constraints.Opsearch 27 73–92. · Zbl 0715.90084
[26] Rajendra, V., (1993). On integer fractional linear programmingOperations Research Society of India,30 174–176.
[27] Rockafellar, R. T., (1970).Convex Analysis, Pricenton University Press, Princeton, New Jersey. · Zbl 0193.18401
[28] Schaible, S. (1982). Bibliography in Fractional Programming.Operations Research,26 211–241. · Zbl 0494.90076
[29] Seshan, CR and V.G. Tibekar, (1980). Algorithms for integer fractional programming.Journal of the Indian Institute of Science Section B-Physical and Chemical Series 62, 9–16. · Zbl 0449.90091
[30] Spiess, H. and M. Florian, (1989). Optimal strategies: a new assignment model for transit networks.Transportation Research,23B 82–102.
[31] Swarup, K., (1965). Programming with Quadratic Fractional Functionals.Opsearch,2 23–30.
[32] Verma, V. and MC. Puri, (1990). On Wolf’s Method for solving linear fractional programming problem.Opsearch,27(3) 176–179. · Zbl 0719.90080
[33] Young, Z.H., Tarjan, R. E., and Orlin, J.B. (1991). Faster parametric shortest paths and minimum-balance algorithms.Networks,21, 205–221. · Zbl 0719.90087
[34] Wolf, H. (1985). A parametric method for solving the linear fractional programming problem.Operations Research,33(4) 835–841. · Zbl 0579.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.