2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

In any iteration of Column Generation, you can calculate the Lagrangian bound, provided that you solve the pricing problem to optimality (you can easily find on Internet how to calculate such bound). If the maximum value (for a minimization problem) of this Lagrangian bound (over all col.gen. iterations) coincides with the value of your heuristic solution, the latter is optimal. Optimality gap is the difference between the two.

$\endgroup$
12
  • $\begingroup$ Thank you very much. I can then calculate this Lagranigan bound for the final master problem with the columns and the restored integrality, right? Or for all Masterproblems for all iterations? $\endgroup$
    – ORNoob
    Commented Mar 19 at 13:48
  • $\begingroup$ Usually, it suffices to calculate the Lagrangian bound for the last iteration of the column generation (again, provided that you solved the pricing to optimality in this iteration). $\endgroup$ Commented Mar 19 at 15:01
  • $\begingroup$ I see. Thank you. Yes I solve the SPs to optimality. However am I able to compute the Lagranigan Bound even though I don't use anything Lagranigan related in my CG algorithm? Or do you in how to compute it in Gurobi by any chance? $\endgroup$
    – ORNoob
    Commented Mar 20 at 8:53
  • $\begingroup$ If the best reduced cost is zero then the Lagrangian bound is equal to the solution value of the restricted master LP. $\endgroup$ Commented Mar 20 at 14:06
  • $\begingroup$ Well I solve the SPs to optimality and the add columns as long as the RC are <-1-e6. Would that also work? $\endgroup$
    – ORNoob
    Commented Mar 20 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.