×

An improved branch and bound algorithm for mixed integer nonlinear programs. (English) Zbl 0797.90069

Summary: This paper describes an improved branch and bound code for zero-one mixed integer nonlinear programs with convex objective functions and constraints. The code uses Lagrangian duality to obtain lower bounds. The code also uses early branching to avoid solving some subproblems to optimality. Computational results show substantial performance improvements on many problems.

MSC:

90C11 Mixed integer programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C25 Convex programming
90C09 Boolean programming

Software:

nag; NAG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hoang, H. H., Topological optimization of networks: a nonlinear mixed integer model employing generalized Benders decomposition, IEEE Trans. Autom. Control, 27, 164-169 (1982) · Zbl 0472.90068
[2] Magnanati, T. L.; Wong, R. T., Network design and transportation planning: models and algorithms, Transport. Sci., 18, 1-55 (1984)
[3] Floudas, C. A.; Aggarwal, A.; Ciric, A. R., Global optimum search for nonconvex NLP and MINLP problems, Comps Chem. Engng, 13, 1117-1132 (1989)
[4] Grossmann, I. E., Mixed-integer programming approach for the synthesis of integrated process flow-sheets, Comps Chem. Engng, 9, 463-482 (1985)
[5] Kocis, Gary R.; Grossmann, Ignacio E., Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis, Ind. Engng Chem. Res., 27, 1407-1421 (1988)
[6] Gavish, B.; Horsky, D.; Srikanth, K., An approach to the optimal positioning of a new product, Mgmt Sci., 29, 1277-1297 (1983) · Zbl 0526.90056
[7] Laughhunn, D. J., Quadratic binary programming with applications to capital-budgeting problems, Ops Res., 18, 454-461 (1970) · Zbl 0193.20209
[8] Mao, J. C.T.; Wallingford, B. A., An extension of Lawler and Bell’s method of discrete optimization with examples from capital budgeting, Mgmt Sci., 15, 51-60 (1968)
[9] Weingartner, H. M., Capital budgeting of interrelated projects, Mgmt Sci., 12, 516-584 (1966)
[10] Gupta, Omprakash K.; Ravindran, A., Nonlinear integer programming algorithms: a survey, OPSEARCH, 20, 189-206 (1983) · Zbl 0602.90102
[11] Hansen, Pierre, Methods of nonlinear 0-1 programming, (Hammer, P. L.; Johnson, E. J.; Korte, B. H., Discrete Optimization II (1979), North Holland: North Holland New York) · Zbl 0426.90063
[12] Gupta, Omprakash K.; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Mgmt Sci., 31, 1533-1546 (1985) · Zbl 0591.90065
[13] Lawler, E. L.; Wood, D. E., Branch and bound methods: a survey, Ops Res., 14, 699-719 (1966) · Zbl 0143.42501
[14] Parker, R. Gary; Rardin, Ronald L., Discrete Optimization (1988), Academic Press: Academic Press Boston · Zbl 0652.90068
[15] Fletcher, R., Practical Methods of Optimization (1987), Wiley: Wiley New York · Zbl 0905.65002
[16] Gill, Philip E.; Murray, Walter; Wright, Margaret, Practical Optimization (1981), Academic Press: Academic Press New York · Zbl 0503.90062
[17] NAG, (FORTRAN Library Manual Mark 13, Vol. 3 (1988), Numerical Analysis Group: Numerical Analysis Group Oxford)
[18] Duran, Marco A.; Grossmann, Ignacio E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathl Program., 36, 307-339 (1986) · Zbl 0619.90052
[19] Paules, Granville E.; Floudas, Christodoulos A., APROS: algorithmic development methodology for discrete-continuous optimization problems, Ops Res., 37, 902-915 (1989) · Zbl 0689.90058
[20] Newspaper Enterprise Association Inc., The World Almanac and Book of Facts (1990), Scripps Howard
[21] Bertsekas, Dimitri; Gallager, Robert, Data Networks (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0734.68006
[22] Boorstyn, Robert R.; Frank, Howard, Large-scale network topological optimization, IEEE Trans. Communs, 25, 29-47 (1977) · Zbl 0361.94044
[23] Gerla, Mario; Kleinrock, Leonard, On the topological design of distributed computer networks, IEEE Trans. Communs, 25, 48-60 (1977)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.