×

Outcome-space cutting-plane algorithm for linear multiplicative programming. (English) Zbl 0962.90024

Summary: This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Konno, H., and Kuno, T., Generalized Linear Multiplicative and Fractional Programming, Annals of Operations Research, Vol. 25, pp. 147–161, 1990. · Zbl 0725.90082
[2] Matsui, T., NP-Hardness of Linear Multiplicative Programming and Related Problems, Journal of Global Optimization, Vol. 9, pp. 113–119, 1996. · Zbl 0868.90111
[3] Horst, R. and Tuy, H., Global Optimization: Deterministic Approaches, 2nd Edition, Springer Verlag, Berlin, Germany, 1993. · Zbl 0867.90105
[4] 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. · Zbl 0675.90011
[5] Henderson, J. M., and Quandt, R. E., Microeconomic Theory, McGraw-Hill, New York, NY, 1971.
[6] 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.
[7] 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. · Zbl 0832.90105
[8] Konno, H., and Kuno, T., Linear Multiplicative Programming, Mathematical Programming, Vol. 56, pp. 51–64, 1992. · Zbl 0761.90080
[9] 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. · Zbl 0746.90056
[10] Schaible, S., and Sodini, C., Finite Algorithm for Generalized Linear Multipli-cative Programming, Journal of Optimization Theory and Applications, Vol. 87, pp. 441–455, 1995. · Zbl 0839.90113
[11] 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. · Zbl 0851.90117
[12] Muu, L. D., and Tam, B. T., Minimizing the Sum of a Convex Function and the Product of Two Affine Functions over a Convex Set, Optimization, Vol. 24, pp. 57–62, 1992. · Zbl 0817.90113
[13] Pardalos, P. M., Polynomial Time Algorithms for Some Classes of Constrained Nonconvex Quadratic Problems, Optimization, Vol. 21, pp. 843–853, 1990. · Zbl 0714.90082
[14] Tuy, H., and Tam, B.T., An Efficient Solution Method for Rank-Two Quasicon-cave Minimization Problems, Optimization, Vol. 24, pp. 43–56, 1992. · Zbl 0817.90079
[15] 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. · Zbl 0856.90103
[16] TUY, H., Polyhedral Annexation, Dualization, and Dimension Reduction Tech-nique in Global Optimization, Journal of Global Optimization, Vol. 1, pp. 229–244, 1991. · Zbl 0752.90077
[17] Falk, J. E., and Palocsay, S.W., Image Space Analysis of Generalized Fractional Programs, Journal of Global Optimization, Vol. 4, pp. 63–88, 1994. · Zbl 0809.90121
[18] Thoai, N. V., A Global Optimization Approach for Solving the Convex Multi-plicative Programming Problem, Journal of Global Optimization, Vol. 1, pp. 341–357, 1991. · Zbl 0752.90056
[19] Benson, H. P., and Boger, G. M., Analysis of an Outcome Space Formulation of the Multiplicative Programming Problem, Working Paper, Warrington College of Business Adminstration, University of Florida, Gainesville, Florida, 1998.
[20] Bazaraa, M. S., Sherali, H. D., and Shetty, C.M., Nonlinear Program-ming: Theory and Algorithms, 2nd Edition, John Wiley and Sons, New York, NY, 1993. · Zbl 0774.90075
[21] Benson, H. P., and Boger, G. M., Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic, Journal of Optimization Theory and Applications, Vol. 94, pp. 487–510, 1997. · Zbl 0889.90128
[22] Benson, H. P., and Sun, E., Pivoting in an Outcome Polyhedron, Part II: Executing the Pivot Process, Working Paper, Warrington College of Business Administration, University of Florida, Gainesville, Florida, 1998.
[23] Murty, K. G., Linear Programming, John Wiley and Sons, New York, NY, 1983.
[24] Carvajal-Moreno, R., Minimization of Concave Functions Subject to Linear Constraints, Operations Research Center Report ORC 72-3, University of Cali-fornia, Berkeley, California, 1972.
[25] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[26] Benson, H. P., A Generalized {\(\gamma\)}-Valid Cut Procedure, Working Paper, Warrington College of Business Administration, University of Florida, Gainesville, Florida, 1998.
[27] Benson, H.P., Pivoting in an Outcome Polyhedron, Part 1: Motivation and Initialization, Working Paper, Warrington College of Business Administration, University of Florida, Gainesville, Florida, 1998.
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.