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 solution to produce new columns. Hence, when solving a slightly perturbated problem in which the block-angular structure is preserved, the method’s speed highly depends on whether we must generate new columns or not. Therefore, we provide a theoretical analysis for warm-starting Dantzig–Wolfe decomposition.
We consider two types of perturbations in this paper and give their sensitivity analysis. First, we consider 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.