A branch-and-reduce approach to global optimization. (English) Zbl 0856.90103

Summary: This paper presents valid inequalities and range contraction techniques that can be used to reduce the size of the search space of global optimization problems. To demonstrate the algorithmic usefulness of these techniques, we incorporate them within the branch-and-bound framework. This results in a branch-and-reduce global optimization algorithm. A detailed discussion of the algorithm components and theoretical properties are provided. Specialized algorithms for polynomial and multiplicative programs are developed. Extensive computational results are presented for engineering design problems, standard global optimization test problems, univariate polynomial programs, linear multiplicative programs, mixed-integer nonlinear programs and concave quadratic programs. For the problems solved, the computer implementation of the proposed algorithm provides very accurate solutions in modest computational time.


90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C11 Mixed integer programming
90C20 Quadratic programming


Full Text: DOI


[1] Albers, S. and K. Brockhoff (1977), ?A Procedure for New Product Positioning in an Attribute Space,? European Journal of Operational Research, 1, 230-238. · Zbl 0366.90038
[2] Al-Khayyal, F. and J. E. Falk (1983) ?Jointly Constrained Biconvex Programming,? Mathematics of Operations Research, 8(2), 273-286. · Zbl 0521.90087
[3] Anagnostou, G., E. M. Ronquist, and A. T. Patera (1991), ?A Computational Procedure for Part Design,? in J. P. Mesirov (ed.), Very Large Scale Computation in the 21 st Century, SIAM, Philadelphia.
[4] Balakrishnan, V. and S. Boyd (1992), Global Optimization in Control System Analysis and Design, in Leondes, C. T. (ed.), Control and Dynamic Systems: Advances in Theory and Applications, vol. 53, Academic Press, New York. · Zbl 0795.93040
[5] Bracken, J. and G. P. McCormick (1968), Selected Applications of Nonlinear Programming, Wiley, New York. · Zbl 0194.20502
[6] Brayton, R. K., G. D. Hachtel, and A. L. Sangiovanni-Vincentelli (1981), ?A Survey of Optimization Techniques for Integrated-Circuit Design,? Proceedings of the IEEE, 69, 1334-1362.
[7] Brooke, A., D. Kendrick, and A. Meeraus (1988), GAMS-A User’s Guide, The Scientific Press, Redwood City.
[8] Colville, A. R. (1968), ?A Comparative Study of Nonlinear Programming Codes?, IBM Scientific Report 320-2940, New York.
[9] Danniger, G. (1992), ?Role of Copositivity in Optimality Criteria for Nonconvex Optimization Problems,? Journal of Optimization Theory and Applications, 75(3), 535-538. · Zbl 0792.90058
[10] Dixon, L. C. W. (1990), ?On Finding the Global Minimum of a Function of One Variable?, SIAM National Meeting, Chicago, IL.
[11] Dixon, L. C. W. and G. P. Szegø (1975), Towards Global Optimization, North Holland, Amsterdam. · Zbl 0309.90052
[12] Durán, M. A. (1984), ?A Mixed-integer Nonlinear Programming Approach for the Systematic Synthesis of Engineering Systems?, Ph.D. Thesis, Department of Chemical Engineering, Carnegie Mellon University.
[13] Durán, M. A. and I. E. Grossmann (1986), ?A Mixed-integer Nonlinear Programming Algorithm for Process Systems Synthesis,? American Institute of Chemical Engineers Journal, 32, 592-606.
[14] Durán, M. A. and I. E. Grossmann (1986), ?An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs,? Mathematical Programming, 36, 307-339. · Zbl 0619.90052
[15] Falk, J. E. (1973), ?Conditions for Global Optimality in Nonlinear Programming,? Operations Research, 21, 337-340. · Zbl 0261.90055
[16] Falk, J. E. and R. M. Soland (1969), ?An Algorithm for Separable Nonconvex Programming Problems,? Management Science, 15, 550-569. · Zbl 0172.43802
[17] Floudas, C. A. and A. R. Ciric (1989), ?Strategies for Overcoming Uncertainties in Heat Exchanger Network Synthesis,? Computers & Chemical Engineering, 13, 1133-1152.
[18] Floudas, C. A. and P. M. Pardalos (1990), A Collection of Test Problems for Constrained Global Optimization Algorithms, Springer-Verlag, Berlin. · Zbl 0718.90054
[19] Goldstein, A. A. and J. F. Price (1971), ?On Descent from Local Minima,? Mathematics of Computation, 25, 569-574. · Zbl 0223.65020
[20] Grossmann, I. E. (1985), ?Mixed-integer Programming Approach for the Synthesis of Integrated Process Flow-sheets,? Computers & Chemical Engineering, 9, 463-482.
[21] Haftka, R. T. and Gurdal, Z. (1992), Elements of Structural Optimization, Kluwer Academic Publishers, Dordrecht.
[22] Hamed, A. S. E. and G. P. McCormick (1993), ?Calculation of Bounds on Variables Satisfying Nonlinear Inequality Constraints,? Journal of Global Optimization, 3(1), 25-47. · Zbl 0845.90105
[23] Hansen, P., B. Jaumard, and S.-H. Lu (1991), ?An Analytical Approach to Global Optimization,? Mathematical Programming, 52(2), 227-254. · Zbl 0747.90091
[24] Hansen, P., B. Jaumard, and J. Xiong (1993), ?Decomposition and Interval Arithmetic Applied to Global Minimization of Polynomial and Rational Functions,? Journal of Global Optimization, 3(4), 421-437. · Zbl 0794.90062
[25] Haverly, C. A. (1978), ?Studies of the Behaviour of Recursion for the Pooling Problem,? SIGMAP Bull., 25, 19.
[26] Hillestad, R. J. and S. E. Jacobsen (1980), ?Reverse Convex Programming,? Applied Mathematics and Optimization, 6, 63-78. · Zbl 0448.90044
[27] Hiriart-Urruty, J.-B. (1986), ?When Is a Point x satisfying ?f(x)=0 a global optimum of f?,? American Mathematics Monthly, 93, 556-558. · Zbl 0603.49015
[28] Horst, R. and H. Tuy (1993), Global Optimization: Deterministic Approaches, Springer-Verlag, 2nd ed., Berlin. · Zbl 0704.90057
[29] Kalantari, B. and J. B. Rosen (1987), ?An Algorithm for Global Minimization of Linearly Constrained Convex Quadratic Functions,? Mathematics of Operations Research, 12(3), 544-561. · Zbl 0638.90081
[30] Kocis, G. R. and I. E. Grossmann (1988), ?Global Optimization of Nonconvex MINLP Problems in Process Synthesis,? Industrial and Engineering Chemistry Research, 27(8), 1407-1421.
[31] Konno, H. and T. Kuno (1990), ?Generalized Linear Multiplicative and Fractional Programming,? Annals of Operations Research, 25, 147-162. · Zbl 0725.90082
[32] Konno, H., T. Kuno, and Y. Yajima (1992), ?Parametric Simplex Algorithms for a Class of NP-Complete Problems Whose Average Number of Steps is Polynomial,? Computational Optimization and Applications, 1, 227-239. · Zbl 0770.90048
[33] Kuno, T. and H. Konno (1991), ?A Parametric Successive Underestimation Method for Convex Multiplicative Programming Problems,? Journal of Global Optimization, 1(3), 267-285. · Zbl 0752.90057
[34] Lamar, B. W. (1993), ?An Improved Branch and Bound Algorithm for Minimum Concave Cost Network Flow Problems,? Journal of Global Optimization, 3(3), 261-287. · Zbl 0781.90035
[35] Liebman, J., N. Khachaturian, and V. Chanaratna (1981), ?Discrete Structural Optimization,? Journal of Structural Division, ASCE, 107, no. ST11, Proceedings paper 16643 (Nov.), 2177-2197.
[36] Liebman, J., L. Lasdon, L. Schrage, and A. Waren (1986), Modeling and Optimization with GINO, The Scientific Press, Palo Alto, CA.
[37] Manousiouthakis, M. and D. Sourlas (1992), ?A Global Optimization Approach to Rationally Constrained Rational Programming,? Chemical Engineering Communications, 115, 127-147.
[38] McCormick, G. P. (1972), ?Converting General Nonlinear Programming Problems to Separable Nonlinear Programming Problems,? Technical Report Serial T-267, The George Washington University, Washington, D.C.
[39] McCormick, G. P. (1976), ?Computability of Global Solutions to Factorable Nonconvex Programs: Part I-Convex Underestimating Problsms,? Mathematical Programming, 10, 147-175. · Zbl 0349.90100
[40] McCormick, G. P. (1983), Nonlinear Programming. Theory, Algorithms, and Applications, Wiley Interscience, New York. · Zbl 0563.90068
[41] Minoux, M. (1986), Mathematical Programming. Theory and Algorithms, Wiley, New York. · Zbl 0602.90090
[42] Moore, R. (1966), Interval Analysis, Prentice Hall, Englewood Cliffs, New Jersey. · Zbl 0176.13301
[43] Murtagh, B. A. and M. A. Saunders (1986), MINOS 5.0 User’s Guide, Technical Report SOL 83-20, Systems Optimization Laboratory, Department of Operations Research, Stanford University, CA.
[44] Murty, K. G. and S. N. Kabadi (1987), ?Some NP-Complete Problems in Quadratic and Nonlinear Programming,? Mathematical Programming, 39, 117-129. · Zbl 0637.90078
[45] Neumaier, A. (1992), ?An Optimal Criterion for Global Quadratic Optimization,? Journal of Global Optimization, 2(2), 201-208. · Zbl 0783.90095
[46] Papalambros, P. Y. and D. J. Wilde (1988), Principles of Optimal Design, Cambridge University Press. · Zbl 0654.90047
[47] Pardalos, P. M. (1990), ?Polynomial Time Algorithms for Some Classes of Constrained Quadratic Problems,? Optimization, 21(6), 843-853. · Zbl 0714.90082
[48] Pardalos, P. M. and R. Horst (1994), Handbook of Global Optimization, Kluwer Academic Publishers, Norwell (Massachusetts). · Zbl 0805.00009
[49] Pardalos, P. M. and G. Schnitger (1988), ?Checking local optimality in constrained quadratic programming is NP-hard,? Operations Research Letters, 7, 33-35. · Zbl 0644.90067
[50] Pardalos, P. M., D. Shalloway, and G. Xue (1994), ?Optimization Methods for Computing Global Minima of Nonconvex Potential Energy Functions,? Journal of Global Optimization, 4(2), 117-133. · Zbl 0797.90115
[51] Phillips, A. T. and J. B. Rosen (1990), ?Guaranteed ?-Approximate Solution for Indefinite Quadratic Global Minimization,? Naval Research Logistics, 37, 499-514. · Zbl 0708.90063
[52] Rozvany, G. I. N. (1989), Structural Design via Optimality Criteria, Kluwer Academic Publishers, Dordrecht. · Zbl 0687.73079
[53] Ryoo, H. S. (1994), ?Range Reduction as a Means of Performance Improvement in Global Optimization: A Branch-and-Reduce Global Optimization Algorithm?, Master’s Thesis, University of Illinois at Urbana-Champaign, IL.
[54] Ryoo, H. S. and N. V. Sahinidis (1995), ?Global Optimization of Nonconvex NLPs and MINLPs with Applications in Process Design,? Computer & Chemical Engineering, 19(5), 551-566.
[55] Sahinidis, N. V. and I. E. Grossmann (1991), ?Convergence Properties of Generalized Benders Decomposition,? Computers & Chemical Engineering, 15(7), 481-491.
[56] Schoen, F. (1991), ?Stochastic Techniques for Global Optimization: A Survey of Recent Advances,? Journal of Global Optimization, 1(3), 207-228. · Zbl 0752.90071
[57] Sherali, H. D. and A. Alameddine (1992), ?A new Reformulation-Linearization Technique for Bilinear Programming Problems,? Journal of Global Optimization, 2(4), 379-410. · Zbl 0791.90056
[58] Sherali, H. D. and C. H. Tuncbilek (1994), ?Tight Reformulation-Linearization Technique Representations for Solving Nonconvex Quadratic Programming Problems,? Technical Report, Virginia Polytechnic Institute and State University, Blacksburg, Virginia.
[59] Soland, R. M. (1971), ?An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints,? Management Science, 17(11), 759-773. · Zbl 0226.90038
[60] Stephanopoulos, G. and A. W. Westerberg (1975), ?The Use of Hestenes’ Method of Multipliers to Resolve Dual Gaps in Engineering System Optimization,? Journal of Optimization Theory and Applications, 15(3), 285-309. · Zbl 0278.49040
[61] Stoecker, W.F. (1971), Design of Thermal Systems, McGraw-Hill Book Co., New York.
[62] Swaney, R. E. (1990), ?Global Solution of Algebraic Nonlinear Programs?, AIChE Annual Meeting, Chicago, IL.
[63] Thakur, L. S. (1990), ?Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Function Over a Polyhedron,? Mathematics of Operations Research, 16(2), 390-407. · Zbl 0741.90068
[64] Thoai, N. V. (1991), ?A Global Optimization Approach for Solving the Convex Multiplicative Programming Problem,? Journal of Global Optimization, 1(4), 341-357. · Zbl 0752.90056
[65] Törn, A. and A. Zilinskas (1989), Global Optimization, Lecture Notes in Computer Science, 350, Springer-Verlag, Berlin. · Zbl 0752.90075
[66] Tuy, H. (1964), ?Concave Programming Under Linear Constraints,? Doklady Akademic Nauk, 159, 32-35. Translated Soviet Mathematics, 5, 1437-1440.
[67] Tuy, H. (1987), ?Convex Programs with an additional reverse convex constraint,? Journal of Optimization Theory and Applications, 52, 463-486. · Zbl 0585.90071
[68] Tuy, H. (1991), ?Effect of the Subdivision Strategy on Convergence and Efficiency of Some Global Optimization Algorithms,? Journal of Global Optimization, 1(1), 23-36. · Zbl 0744.90083
[69] Tuy, H. and R. Horst (1988), ?Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization. Application to Concave Minimization and D.C. Optimization Problems,? Mathematical Programming, 41(2), 161-183. · Zbl 0651.90063
[70] Tuy, H., V. Khatchaturov, and S. Utkin (1987), ?A Class of Exhaustive Cone Splitting Procedures in Conical Algorithms for Concave Minimization,? Optimization, 18(6), 791-807. · Zbl 0637.90074
[71] Visweswaran, V. and C. A. Floudas (1990), ?A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs-II. Application of Theory and Test Problems,? Computers & Chemical Engineering, 14(2), 1419-1434.
[72] Westerberg, A. W. and J. V. Shah (1978), ?Assuring a Global Optimum by the Use of an Upper Bound on the Lower (Dual) Bound,? Computers & Chemical Engineering, 2, 83-92.
[73] Wilde, D. J. (1978), Globally Optimal Design, J. Wiley & Sons, New York.
[74] Wilkinson, J. H. (1963), Rounding Errors in Algebraic Processes, Prentice Hall, Englewood Cliffs, New Jersey. · Zbl 1041.65502
[75] Wingo, D. R. (1985), ?Globally Minimizing Polynomials without Evaluating Derivatives,? International Journal of Computer Mathematics, 17, 287-294. · Zbl 0579.65061
[76] Yuan, X., S. Zhang, L. Pibouleau and S. Domenech (1988), ?Une méthode d’optimisation non linéaire en variables mixtes pour la conception de procédés,? Recherche Opérataionnelle/Operations Research, 22(4), 331-346. · Zbl 0656.90071
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.