Well, we may drop unnecessary rows and what we get is a very strong lower bound for the problem. Unfortunately, the problem is highly degenerate and we also face the problem of branching versus column generation. This can be solved by exploiting a special technique where dynamic programming does not provide just one solution but the first k solutions.