An Algorithm for Locating Approximate Global Solutions of Nonconvex, Separable Problems

摘要

A commonly employed method for locating solutions of separable programming problems involves a modification of the simplex method applied to a piecewise linear approximation of the original problem. This technique locates only local solutions of the approximate problem. The author presents here the details of a method designed to locate global solutions of the same problem. The method is based on the branch and bound procedure and sets up a finite sequence of linear programming subproblems of a special structure whose solutions ultimately yield the desired global solution. An example is given, and some computational aspects are discussed. (Author)