Geoffrion' generalized the Benders' decomposition approach' to a general class of 'complicated' nonlinear optimization programs. The theoretical significance of the work in Reference 6 is significant, but its computational usefulness is rather limited, due to some serious computational difficulties inherent in the master problem. In this paper, we report on a simple technique to overcome and eliminate these difficulties.
1. Introduction
Geoffriod generalized the Benders' decomposition method' to the following class of general nonlinear optimization programs P:
where X R"', Y C R"', f is a real-valued function and C an m-vector of constraint functions defined on X x Y. f and each component of G are assumed to be concave (but not necessarily differentiable!) in (x,y) for x β¬ X , yEYo, where X and Yo C Y are nonempty, bounded and closed convex sets. Y is an arbitrary set, and y E Y is considered a vector of 'complicating' variables, in the sense that P is a hard (untractable and/or unmanageable) optimization program in (x,y)-space, but for each fixed yEY, the subproblem P(y): {maxf(x,y), x : G(x,y) 2 0, x E X } in x-space is much simpler to solve. The theoretical contribution of Geoffrion's work is very significant. However, the computational usefulness of the generalized algorithm in Reference 6 is rather limited because of serious computational difficulties implicit in Geoffrion's relaxed master problem (which is one of the two programs that need to be solved at each iteration). This problem includes two types of constraints: 8 I L * ( y ; d ) , j=1, . . ., k , and L,(y;Ai) 2 O , j = l , . . ., t , where d L 0 is an optimal dual multipliers vector of subproblem P v ' ) (if, for y = y"EY, P v ' ) has a finite optimal solution); A' L 0 is a vector satisfying supxEx{ AC(x,y')} < 0 (if P v -) is not feasible); and:
The computational difficulties inherent in the master problem, are two. First, the constraints 8 5 L * ( y ; d ) and L,(y;Ai) 2 0 are nonlinear in the 'complicating' variables y . To illustrate this difficulty, consider the case that P is a mixed-integer nonlinear program: then, the master problem will have constraints that are nonlinear in the integer variables y, and the availability of algorithms for solving it is in question. Secondly, the functions L* and L , are given in suprema1 value rpnresentation, rather than in explicit form. As noted by Geoffrion, additional restrictive assumptions onfand G (e.g. thatfand G be separable in x and y ) are required in order to obtain L* and L , in explicit form.
The purpose of this paper is to develop a technique that overcomes the above computational difficulties, without imposing new assumptions on f and G.