Hi, i am currently working on a machine scheduling problem formulated as MILP and trying to solve it with Column Generation. Since I do not use Branch-n-Price, but only Column Generation as heuristic, it can happen that the heuristic solves the model globally optimal, but often not. How can I determine whether the model has been solved optimally without having to solve the entire model to optimality? And how do I then calculate the optimality gap in Julia?
Hi!
If I’m not mistaken, column generation solves the linear relaxation of your problem at optimality.
Then, as an heuristic, you can use the final columns at the end of the column generation to solve the original integer problem restricted to these columns. Is it this heuristic that you are using?
If the objective value of the heuristic is the same as the one of the column generation, then the heuristic gave you an optimal solution. If not, then you cannot determine if the heuristic solution is optimal, but you can compute a gap with respect to the continuous solution of the column generation.