Originally posted by: varun7rs

I've been working on a network design problem with huge instances from SNDlib. I developed a heuristic to solve the problem within a shorter span of time (as compared to the MIP) but since I'd like to compute the optimality gap of the solution returned by the heuristic, I need a lower bound in this case. Now, when I solve its MIP counterpart to obtain a valid lower bound, CPLEX returned a solution of 100 % optimality and LB = 0. What can be done in this instance to obtain a valid LB?

Thanks in advance

Why do you think the lower bound of 0 is invalid?

If the dual bound is 0, then CPLEX will always show a gap of 100%, no matter what the best solution is. This is because the regular definition of the gap requires dividing by the lower bound, which cannot be done in case the bound is 0.

Originally posted by: varun7rs

Its a norm to compare the quality of the solutions obtained from different solution methodologies in terms of their optimality gaps. In this case, I really don't have a clue as to how I can compute the optimality gap for a solution obtained from a heuristic with the lower bound of 0. This was my primary concern.

You could use the absolute gap or you could slightly shift the lower bound by some small number.