Regional division and reduction algorithm for minimizing the sum of linear fractional functions
Tóm tắt
This paper presents a practicable regional division and cut algorithm for minimizing the sum of linear fractional functions over a polyhedron. In the algorithm, by using an equivalent problem (P) of the original problem, the proposed division operation generalizes the usual standard bisection, and the deleting and reduction operations can cut away a large part of the current investigated region in which the global optimal solution of (P) does not exist. The main computation involves solving a sequence of univariate equations with strict monotonicity. The proposed algorithm is convergent to the global minimum through the successive refinement of the solutions of a series of univariate equations. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.
Tài liệu tham khảo
Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)
Matsui, T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9, 113–119 (1996)
Jiao, H.W., Liu, S.Y.: A practicable branch and bound algorithm for sum of linear ratios problem. Eur. J. Oper. Res. 243, 723–730 (2015)
Wang, C., Shen, P.: A global optimization algorithm for linear fractional programming. Appl. Math. Comput. 204(1), 281–287 (2008)
Shen, P., Wang, C.: Global optimization for sum of linear ratios problem. Appl. Math. Comput. 176, 219–229 (2006)
Lim, S., Zhu, J.: Integrated data envelopment analysis: global vs. local optimum. Eur. J. Oper. Res. 229, 276–278 (2013)
Rao, M.R.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66, 622–626 (1971)
Drezner, Z., Manes, R.P., Whinston, A.: Queueing-location problems on the plane. Nav. Res. Logist. 37, 929–935 (1990)
Benson, H.: A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem. Eur. J. Oper. Res. 182, 597–611 (2007)
Carlsson, J.G., Shi, J.: A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension. Oper. Res. Lett. 41(4), 381–389 (2013)
Depetrini, D., Locatelli, M.: Approximation of linear fractional-multiplicative problems. Math. Program. 128, 437–443 (2011)
Shen, P., Li, W., Liang, Y.: Branch-reduction-bound algorithm for linear sum-of-ratios fractional programs. Pac. J. Optim. 11(1), 79–99 (2015)
Konno, H., Yajima, Y., Matsui, T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1, 65–81 (1991)
Konno, H., Yamashita, H.: Minimization of the sum and the product of several linear fractional functions. Nav. Res. Logist. 46, 583–596 (1999)
Muu, L.D., Tam, B.T., Schaible, S.: Efficient algorithms for solving certain nonconvex programs dealing with the product of two affine fractional functions. J. Glob. Optim. 6, 179–191 (1995)
Ji, Y., Zhang, K., Qu, S.: A deterministic global optimization algorithm. Appl. Math. Comput. 185, 382–387 (2007)
Jiao, H., Liu, S.: A practicable branch and bound algorithm for sum of linear ratios problem. Eur. J. Oper. Res. 243, 723–730 (2015)
Jiao, H., Wang, Z., Chen, Y.: Global optimization algorithm for sum of generalized polynomial ratios problem. Appl. Math. Model. 37, 187–197 (2013)
Tuy, H.: Convex Analysis and Global Optimization. Kluwer, Dordrecht (1978)
Majhi, J., Janardan, R., Schwerdt, J., Smid, M., Gupta, P.: Minimizing support structures and trapped area in two-dimensional layered manufacturing. Comput. Geom. Theory Appl. 12, 241–267 (1999)
Chen, D., Daescu, O., Hu, X., Wu, X., Xu, J.: Determining an optimal penetration among weighted regions in two and three dimensions. J. Comb. Optim. 5, 59–79 (2001)
Chen, D., Daescu, O., Dai, Y., Katoh, N., Wu, X., Xu, J.: Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications. J. Comb. Optim. 9, 69–90 (2005)
Pei, Y., Zhu, D.: Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region. J. Appl. Math. Comput. 41, 153–169 (2013)