Skip to main content
SpringerLink
Log in

Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic

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

Abstract

Multiplicative programming problems are difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, finance, economics, and other fields. This article has two purposes. The first is to present an analysis that shows several relationships between concave multiplicative programs and concave minimization problems, and between concave multiplicative programs and certain multiple-objective mathematical programs. The second purpose is to propose and report computational results for a heuristic efficient-point search algorithm that we have designed for use on linear multiplicative programming problems. To our knowledge, this is the first heuristic algorithm of its type. The theoretical and algorithmic results given in the article offer some potentially important new avenues for analyzing and solving multiplicative programming problems of various types.

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. KONNO, H., and KUNO, T., Generalized Linear Multiplicative and Fractional Programming, Annals of Operations Research, Vol. 25, pp. 147–161, 1990.

    Google Scholar 

  2. THOAI, N. V., A Global Optimization Approach for Solving the Convex Multiplicative Programming Problem, Journal of Global Optimization, Vol. 1, pp. 341–357, 1991.

    Google Scholar 

  3. KONNO, H., KUNO, T., and YAJIMA, Y., Parametric Simplex Algorithms for a Class of NP-Complete Problems Whose Average Number of Steps Is Polynomial, Computational Optimization and Applications, Vol. 1, pp. 227–239, 1992.

    Google Scholar 

  4. MATSUI, T., NP-Hardness of Linear Multiplicative Programming and Related Problems, Journal of Global Optimization, Vol. 9, pp. 113–119, 1996.

    Google Scholar 

  5. HORST, R., and TUY, H., Global Optimization: Deterministic Approaches, 2nd Edition, Springer Verlag, Berlin, Germany, 1993.

    Google Scholar 

  6. KONNO, H., and INORI, M., Bond Portfolio Optimization by Bilinear Fractional Programming, Journal of the Operations Research Society of Japan, Vol. 32, pp. 143–158, 1988.

    Google Scholar 

  7. HENDERSON, J. M., and QUANDT, R. E., Microeconomic Theory, McGraw-Hill, New York, New York, 1971.

    Google Scholar 

  8. MALING, K., MUELLER, S. H., and HELLER, W. R., On Finding Most Optimal Rectangular Package Plans, Proceedings of the 19th Design Automation Conference, pp. 663–670, 1982.

  9. KONNO, H., and KUNO, T., Linear Multiplicative Programming, Mathematical Programming, Vol. 56, pp. 51–64, 1992.

    Google Scholar 

  10. KONNO, H., and KUNO, T., Multiplicative Programming Problems, Handbook of Global Optimization, Edited by R. Horst and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands, pp. 369–405, 1995.

    Google Scholar 

  11. KONNO, H., YAJIMA, Y., and MATSUI, T., Parametric Simplex Algorithms for Solving a Special Class of Nonconvex Minimization Problems, Journal of Global Optimization, Vol. 1, pp. 65–81, 1991.

    Google Scholar 

  12. SCHAIBLE, S., and SODINI, C., Finite Algorithm for Generalized Linear Multiplicative Programming, Journal of Optimization Theory and Applications, Vol. 87, pp. 441–455, 1995.

    Google Scholar 

  13. ANEJA, Y. P., AGGARWAL, V., and NAIR, K. P. K., On a Class of Quadratic Programs, European Journal of Operational Research, Vol. 18, pp. 62–70, 1984.

    Google Scholar 

  14. TUY, H., and TAM, B. T., An Efficient Solution Method for Rank-Two Quasiconcave Minimization Problems, Optimization, Vol. 24, pp. 43–56, 1992.

    Google Scholar 

  15. KUNO, T., A Practical Algorithm for Minimizing a Rank-Two Saddle Function on a Polytope, Journal of the Operations Research Society of Japan, Vol. 39, pp. 63–76, 1996.

    Google Scholar 

  16. KUNO, T., and KONNO, H., A Parametric Successive Underestimation Method for Convex Multiplicative Programming Problems, Journal of Global Optimization, Vol. 1, pp. 267–285, 1991.

    Google Scholar 

  17. KUNO, T., YAJIMA, Y., and KONNO, H., An Outer Approximation Method for Minimizing the Product of Several Convex Functions on a Convex Set, Journal of Global Optimization, Vol. 3, pp. 325–335, 1993.

    Google Scholar 

  18. RYOO, H. S., and SAHINIDIS, N. V., A Branch-and-Reduce Approach to Global Optimization, Journal of Global Optimization, Vol. 8, pp. 107–138, 1996.

    Google Scholar 

  19. TUY, H., Polyhedral Annexation, Dualization, and Dimension Reduction Technique in Global Optimization, Journal of Global Optimization, Vol. 1, pp. 229–244, 1991.

    Google Scholar 

  20. BENSON, H. P., Concave Minimization: Theory, Applications, and Algorithms, Handbook of Global Optimization, Edited by R. Horst and P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, Netherlands, pp. 43–148, 1995.

    Google Scholar 

  21. BENSON, H. P., Deterministic Algorithms for Constrained Concave Minimization: A Unified Critical Survey, Naval Research Logistics, Vol. 43, pp. 765–795, 1996.

    Google Scholar 

  22. PARDALOS, P. M., and ROSEN, J. B., Constrained Global Optimization: Algorithms and Applications, Springer Verlag, Berlin, Germany, 1987.

    Google Scholar 

  23. ROCKAFELLAR, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

    Google Scholar 

  24. BAZARAA, M. S., SHERALI, H. D., and SHETTY, C. M., Nonlinear Programming: Theory and Algorithms, 2nd Edition, John Wiley and Sons, New York, New York, 1993.

    Google Scholar 

  25. AVRIEL, M., DIEWERT, W. E., SCHAIBLE, S., and ZANG, I., Generalized Concavity, Plenum Press, New York, New York, 1988.

    Google Scholar 

  26. COHON, J. L., Multiobjective Programming and Planning, Academic Press, New York, New York, 1978.

    Google Scholar 

  27. EVANS, G. W., An Overview of Techniques for Solving Multiobjective Mathematical Programs, Management Science, Vol. 30, pp. 1268–1282, 1984.

    Google Scholar 

  28. LUC, D. T., Theory of Vector Optimization, Springer Verlag, Berlin, Germany, 1989.

    Google Scholar 

  29. SAWARAGI, Y., NAKAYAMA, H., and TANINO, T., Theory of Multiobjective Optimization, Academic Press, Orlando, Florida, 1985.

    Google Scholar 

  30. STADLER, W., A Survey of Multicriteria Optimization or the Vector Maximum Problem, Part 1: 1776–1960, Journal of Optimization Theory and Applications, Vol. 29, pp. 1–52, 1979.

    Google Scholar 

  31. STEUER, R. E., Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, New York, New York, 1986.

    Google Scholar 

  32. YU, P. L., Multiple-Criteria Decision Making, Plenum, New York, New York, 1985.

    Google Scholar 

  33. ZELENY, M., Multiple-Criteria Decision Making, McGraw-Hill, New York, New York, 1982.

    Google Scholar 

  34. SNIEDOVICH, M., and FINDLAY, S., Solving a Class of Multiplicative Programming Problems via C-Programming, Journal of Global Optimization, Vol. 6, pp. 313–319, 1995.

    Google Scholar 

  35. STEUER, R. E., Operating Manual for the ADBASE Multiple-Objective Linear Programming Package, College of Business Administration, University of Georgia, Athens, Georgia, 1989.

    Google Scholar 

  36. PHILIP, J., Algorithms for the Vector Maximization Problem, Mathematical Programming, Vol. 2, pp. 207–229, 1972.

    Google Scholar 

  37. BENSON, H. P., Existence of Efficient Solutions for Vector Maximization Problems, Journal of Optimization Theory and Applications, Vol. 26, pp. 569–580, 1978.

    Google Scholar 

  38. MURTY, K. G., Linear Programming, John Wiley and Sons, New York, New York, 1983.

    Google Scholar 

  39. INTERNATIONAL BUSINESS MACHINES, Optimization Subroutine Library Guide and Reference, International Business Machines, Mechanicsburg, Pennsylvania, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Business Administration, University of Florida, Gainesville, Florida

    H. P. Benson (Professor)

  2. College of Business Administration, University of Florida, Gainesville, Florida

    G. M. Boger (Graduate Student)

Authors
  1. H. P. Benson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. M. Boger
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Benson, H.P., Boger, G.M. Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic. Journal of Optimization Theory and Applications 94, 487–510 (1997). https://doi.org/10.1023/A:1022600232285

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022600232285

Search

Navigation