×

zbMATH — the first resource for mathematics

An interval branch and bound algorithm for bound constrained optimization problems. (English) Zbl 0760.90085
Summary: We propose modifications to a prototypical branch-and-bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch-and-bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on selection of problems with different properties.

MSC:
90C30 Nonlinear programming
65G30 Interval and finite arithmetic
65K05 Numerical mathematical programming methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI