Dual Variable Based Fathoming in Dynamic Programs for Column Generation

In column generation schemes, particularly those proposed for set partitioning type problems, dynamic programming algorithms are applied to solve the respective pricing subproblem. In addition to traditional dominance criteria for state space reduction, we develop a simple generic lower bounding criterion based on the dual optimal solution of the restricted master problem. Key words: Dynamic programming; Column generation; Linear programming Column generation is a prominent---and often the solely applicable---method to cope with linear programming problems with a colossal number of variables. In recent years we have been witnessing the optimal solution of truly large problems, but still the need for faster algorithms remains, especially in the various practical application areas. The pricing subproblem usually constitutes the crucial part of a column generation scheme, not uncommonly for the reason of being a hard combinatorial optimization problem by itself. Although a dynamic program..