Dantzig-Wolfe reformulation solved by Column Generation is an approach to obtain improved bounds for Mixed Integer Programs. A downside of this approach is that the Column Generation process can be very time consuming due to degeneracy of the master problem and the tailing-off effect. To counter this problem in the Column Generation process, we also perform a number of Lagrangean Relaxation iterations to generate new columns after each time that we solve the master problem. This potentially reduces the number of times we have to solve the master problem. We explore this combination of Column Generation and Lagrangean Relaxation for the Job Grouping Problem. In our test set, we observe that the time spent to solve the master problem is decreased by a factor 4, while the total time spent on solving the subproblems remains approximately equal.
Published April 2013 , 13 pages