Dantzig-Wolfe decomposition is a well-known classical method for solving huge linear optimization problems with a block-angular structure. The most computationally expensive process in the method is pricing: solving block subproblems for a dual variable to produce new columns. Therefore, when we want to solve a slightly perturbated problem in which the block-angular structure is preserved by warm-start Dantzig-Wolfe decomposition, the method’s speed highly depends on whether we must generate new columns or not. Nevertheless, theoretical analysis from this point of view has yet to be investigated.
We consider two types of perturbations in this paper and give their sensitivity analysis. First, we propose the range of the right-hand side parameters where no new column generation is necessary. Second, we consider adding a new block to the original problem or removing an existing one. We demonstrate that we do not have to generate any new columns for existing blocks if our proposed condition, a small-sized linear equation has a positive solution, is satisfied under a mild assumption.