Abstract
The task of finding global optima to general classes of nonconvex optimization problem is attracting increasing attention. McCormick [4] points out that many such problems can conveniently be expressed in separable form, when they can be tackled by the special methods of Falk and Soland [2] or Soland [6], or by Special Ordered Sets. Special Ordered Sets, introduced by Beale and Tomlin [1], have lived up to their early promise of being useful for a wide range of practical problems. Forrest, Hirst and Tomlin [3] show how they have benefitted from the vast improvements in branch and bound integer programming capabilities over the last few years, as a result of being incorporated in a general mathematical programming system.
Nevertheless, Special Ordered Sets in their original form require that any continuous functions arising in the problem be approximated by piecewise linear functions at the start of the analysis. The motivation for the new work described in this paper is the relaxation of this requirement by allowing automatic interpolation of additional relevant points in the course of the analysis.
This is similar to an interpolation scheme as used in separable programming, but its incorporation in a branch and bound method for global optimization is not entirely straightforward. Two by-products of the work are of interest. One is an improved branching strategy for general special-ordered-set problems. The other is a method for finding a global minimum of a function of a scalar variable in a finite interval, assuming that one can calculate function values and first derivatives, and also bounds on the second derivatives within any subinterval.
The paper describes these methods, their implementation in the UMPIRE system, and preliminary computational experience.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E.M.L. Beale and J.A. Tomlin, “Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables”, in: J. Lawrence, ed.,Proceedings of the fifth international conference on operational research (Tavistock Publications, London, 1970) pp. 447–454.
J.E. Falk and R.M. Soland, “An algorithm for separable nonconvex programming problems”,Management Science 15 (1969) 550–569.
J.J.H. Forrest, J.P.H. Hirst and J.A. Tomlin, “Practical solution of large and complex integer programming problems with UMPIRE”,Management Science 20 (1974) 736–773.
G.P. McCormick, “Attempts to calculate global solutions of problems that may have local minima”, in: F.A. Lootsma, ed.,Numerical methods for non-linear optimization (Academic Press, New York, 1972) pp. 209–221.
C.E. Miller, “The simplex method for local separable programming”, in: R.L. Graves and P. Wolfe, eds.,Recent advances in mathematical programming (McGraw Hill, New York, 1963) pp. 69–100.
R.M. Soland, “An algorithm for separable nonconvex programming problems II: nonconvex constraints”,Management Science 17 (1971) 759–773.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Beale, E.M.L., Forrest, J.J.H. Global optimization using special ordered sets. Mathematical Programming 10, 52–69 (1976). https://doi.org/10.1007/BF01580653
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01580653