Global optimization using special ordered sets

摘要: The task of finding global optima to general classes nonconvex optimization problem is attracting increasing attention. McCormick [4] points out that many such problems can conveniently be expressed in separable form, when they tackled by the special methods Falk and Soland [2] or [6], Special Ordered Sets. Sets, introduced Beale Tomlin [1], have lived up their early promise being useful for a wide range practical problems. Forrest, Hirst [3] show how benefitted from vast improvements branch bound integer programming capabilities over last few years, as result incorporated mathematical system. Nevertheless, Sets original form require any continuous functions arising approximated piecewise linear at start analysis. motivation new work described this paper relaxation requirement allowing automatic interpolation additional relevant course analysis. This similar an scheme used programming, but its incorporation method not entirely straightforward. Two by-products are interest. One improved branching strategy special-ordered-set other minimum function scalar variable finite interval, assuming one calculate values first derivatives, also bounds on second derivatives within subinterval. The describes these methods, implementation UMPIRE system, preliminary computational experience.