×

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem. (English) Zbl 1121.90102

Summary: In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.

MSC:

90C26 Nonconvex programming, global optimization
90C32 Fractional programming
90C46 Optimality conditions and duality in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almogy, Y.; Levin, O., Parametric analysis of a multi-stage stochastic shipping problem, (Lawrence, J., Operational Research ’69 (1970), Tavistock Publications: Tavistock Publications London), 359-370
[2] Cambini, A.; Martein, L.; Schaible, S., On maximizing a sum of ratios, Journal of Information and Optimization Sciences, 10, 65-79 (1989) · Zbl 0676.90081
[3] Chen, D. Z.; Daescu, O.; Dai, Y.; Katoh, N.; Wu, X.; Xu, J., Optimizing the sum of linear fractional functions and applications, (Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (2000), ACM: ACM New York), 707-716 · Zbl 0955.65044
[4] Colantoni, C. S.; Manes, R. P.; Whinston, A., Programming, profit rates, and pricing decisions, Accounting Review, 44, 467-481 (1969)
[5] Drezner, Z.; Schaible, S.; Simchi-Levi, D., Queueing-location problems on the plane, Naval Research Logistics, 37, 929-935 (1990) · Zbl 0716.90068
[6] Dur, M.; Horst, R., Lagrange-duality and partitioning techniques in convex global optimization, Journal of Optimization Theory and Applications, 95, 347-369 (1997) · Zbl 0892.90162
[7] Dur, M.; Horst, R.; Thoai, N. V., Solving sum-of-ratios fractional programs using efficient points, Optimization, 49, 447-466 (2001) · Zbl 1006.90081
[8] Falk, J. E.; Palocsay, S. W., Image space analysis of generalized fractional programs, Journal of Global Optimization, 4, 63-88 (1994) · Zbl 0809.90121
[9] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1996), Springer: Springer Berlin · Zbl 0867.90105
[10] Konno, H.; Fukaishi, K., A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems, Journal of Global Optimization, 18, 283-299 (2000) · Zbl 0971.90065
[11] Konno, H.; Inori, M., Bond portfolio optimization by bilinear fractional programming, Journal of the Operations Research Society of Japan, 32, 143-158 (1989) · Zbl 0675.90011
[12] Konno, H.; Kuno, T.; Yajima, Y., Global minimization of a generalized convex multiplicative function, Journal of Global Optimization, 4, 47-62 (1994) · Zbl 0791.90045
[13] Konno, H.; Yajima, Y.; Matsui, T., Parametric simplex algorithms for solving a special class of nonconvex minimization problems, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[14] Konno, H.; Yamashita, H., Minimizing sums and products of linear fractional functions over a polytope, Naval Research Logistics, 46, 583-596 (1999) · Zbl 0948.90132
[15] Kuno, T., A branch-and-bound algorithm for maximizing the sum of several linear ratios, Journal of Global Optimization, 22, 155-174 (2002) · Zbl 1045.90071
[16] Kuno, T., A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-ratios problems, Journal of Global Optimization, 33, 215-234 (2005) · Zbl 1093.90087
[17] Matsui, T., NP-hardness of linear multiplicative programming and related problems, Journal of Global Optimization, 9, 113-119 (1996) · Zbl 0868.90111
[18] Phuong, N. T.H.; Tuy, H., A unified monotonic approach to generalized linear fractional programming, Journal of Global Optimization, 26, 229-259 (2003) · Zbl 1039.90079
[19] Quesada, J.; Grossmann, I., A global optimization algorithm for linear fractional and bilinear programs, Journal of Global Optimization, 6, 39-76 (1995) · Zbl 0835.90074
[20] Rao, M. R., Cluster analysis and mathematical programming, Journal of the American Statistical Association, 66, 622-626 (1971) · Zbl 0238.90042
[21] Schaible, S., A note on the sum of a linear and linear-fractional function, Naval Research Logistics Quarterly, 24, 691-693 (1977) · Zbl 0377.90086
[22] Schaible, S.; Shi, J., Fractional programming: The sum-of-ratios case, Optimization Methods and Software, 18, 219-229 (2003) · Zbl 1070.90115
[23] Thoai, N. V., Convergence and application of a decomposition method using duality bounds for nonconvex global optimization, Journal of Optimization Theory and Applications, 113, 165-193 (2002) · Zbl 1009.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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.