A cutting plane algorithm and a column generation algorithm as dual algorithms

Abstract

Cutting plane and column generation algorithms are known to be dual in a certain sense. In this paper, a general cutting plane algorithm of Kelley type for convex programs and a general column generation algorithm of Dantzig-Wolfe type for Wolfe's generalized program are described. These two algorithms are shown to be dual. An estimation of the optimal value known for Dantzig-Wolfe methods is carried over to cutting plane methods.