A Generalized Approach To Dantzig-Wolfe Decomposition For Concave Programs

The Dantzig-Wolfe decomposition procedure for concave programs can be viewed as inner linearization followed by restriction. In this paper an approach which allows selective inner linearization of functions and utilizes a generalized pricing problem is presented. The approach allows considerable flexibility in choice of functions to be approximated using inner linearization. Use of the generalized pricing problem guarantees that strict improvement in the value of the objective function is achieved at each iteration and provides a termination criterion which is both necessary and sufficient for optimality. A specialization of this procedure results in an algorithm which is a direct extension of the Dantzig-Wolfe decomposition algorithm.