Skip to main content
SpringerLink
Log in

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Frenk, J.B.G., Scheible, S.: Fractional programming. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, vol. II, pp. 162–172. Kluwer, Dordrecht (2001)

    Google Scholar 

  2. Rao, M.R.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66, 622–626 (1971)

    Article  MATH  Google Scholar 

  3. Almogy, Y., Levin, O.: Parametric analysis of a multi-stage stochastic shipping problem. In: Proceedings of the 5th IFORS Conference (IFORS), pp. 359–370 (1964)

  4. Colantoni, C.S., Manes, R.P., Whinston, A.: Programming, profit rates, and pricing decisions. Account. Rev. 44, 467–481 (1969)

    Google Scholar 

  5. Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1989)

    MATH  MathSciNet  Google Scholar 

  6. Cambini, A., Martein, L., Schaible, S.: On maximizing a sum of ratios. J. Inf. Optim. Sci. 10, 65–79 (1989)

    MATH  MathSciNet  Google Scholar 

  7. 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)

    Article  MATH  MathSciNet  Google Scholar 

  8. Falk, J.E., Palocsay, S.W.: Image space analysis of generalized fractional programs. J. Glob. Optim. 4, 63–88 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  9. Konno, H., Fukaishi, K.: A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems. J. Glob. Optim. 18, 283–299 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  10. Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Konno, H., Yamashita, H.: Minimizing sums and products of linear fractional functions over a polytope. Nav. Res. Logist. 46, 583–596 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  12. Phuong, N.T.H., Tuy, H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259 (2003)

    Article  MATH  Google Scholar 

  13. Konno, H., Kuno, T., Yajima, Y.: Global minimization of a generalized convex multiplicative function. J. Glob. Optim. 4, 47–62 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  14. Benson, H.P.: Global optimization of nonlinear sums of ratios. J. Math. Anal. Appl. 263, 301–315 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  15. Benson, H.P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theory Appl. 112, 1–29 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problem. J. Glob. Optim. 22, 343–364 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  17. Dur, M., Horst, R., Thoai, N.V.: Solving sum-of-ratios fractional programs using efficient points. Optimization 49, 447–466 (2001)

    Article  MathSciNet  Google Scholar 

  18. Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  19. Schaible, S.: Fractional programming. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 495–608. Kluwer, Dordrecht (1995)

    Google Scholar 

  20. Schaible, S.: Fractional programming with sums of ratios. In: Castagnoli, E., Giorgi, G. (eds.) Scalar and Vector Optimization in Economic and Financial Problems, Proceedings of the Workshop in Milan, 1995, pp. 163–175. Elioprint, Modena (1995)

    Google Scholar 

  21. Benson, H.P.: On the global optimization of sums of linear fractional functions over a convex set. J. Optim. Theory Appl. 121, 19–39 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  22. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993)

    Google Scholar 

  23. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I—convex underestimating problems Math. Program. 10, 147–175 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  24. Veinott, A.F.: The supporting hyperplane method for unimodal programming. Oper. Res. 15, 147–152 (1967)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Systems and Operations Management, University of Florida, Gainesville, FL, 32611, USA

    H. P. Benson

Authors
  1. H. P. Benson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H. P. Benson.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Benson, H.P. Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs. J Optim Theory Appl 146, 1–18 (2010). https://doi.org/10.1007/s10957-010-9647-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-010-9647-8

Keywords

Search

Navigation