Column generation can solve the LP-relaxation of our shift-generation problem to optimality. In particular, given an optimal primal feasible solution to the reduced master problem (RMP), the optimality certificate for this solution is given by the solution to the corresponding pricing problem: If the optimal solution to the pricing problem has positive value (i.e. the length of the shortest path through the tour-graph exceeds a certain value), we know that there exists no tour, that can be added to the RMP in order to improve the objective. We are, however, interested in finding the optimal integer solution and not an optimal fractional solution.
Idea: simply solve the RMP with integrity constraints using a pool of candidate-tours (columns) that contain an optimal fractional solution (e.g. the pool of candidates at the time when the LP-relaxation of the RMP was proved to be optimal by the prizing problem).
Since the trivial set of shifts (the solution with which we jump-started the column generation where each task is on its own shift) is included in the final pool of candidates and since this set of shifts forms an integer feasible solution, we know that we will find an integer feasible solution. However, this approach does not give us any guarantees on the goodness of the solution. This is because the optimality certificate given by the prizing problem does not apply to the integer version of the RMP.
We can continue generating columns until we find an integer solution that is "good enough" or up to some timeout. More concretely, in this approach we solve the LP-relaxation as usual, then we enter a loop where
- We solve the MIP
- We check if the solution is good enough or if a timeout is reached. If yes we return the integer solution and exit
- We create
$n$ more columns by$n$ times solving the RMP and then the prizing problem.
The inherent problem with this approach is that the prizing problem is set up in order to find solutions improving the RMP. In particular
- The dual values indicate which solution to the prizing problem may improve the RMP, but not the integer version of the RMP
- Once the candidate pool contains an optimal LP-solution, the candidates generated by the prizing no longer even improve the RMP.
It is thus unclear if the candidates found in this way are in any way useful for improving the MIP.
The standard approach for solving MIP using column generation is branch-and-price. The idea is to use branch-and-bound and solving each LP-relaxation using column generation.
- The benefit of this approach is that we get optimal solutions
- The downside is that the runtime of branch-and-bound crucially depends on getting good lower bounds on the best objective value.