I am trying to solve a graph partitioning problem for a large number of structurally similar random graphs with an 0-1 LP.
Most of these problems are solved within 0.x seconds. Some graphs take the complete offered time slice of 40 min and abort. The solution is mostly seemingly optimal. Therefore I guess that the problem is not to find the optimal solution but to proof its optimality.
but I am not sure about feasible values. (I am no expert in linear optimisation.) I've tried 1% and 0.5% but the problem remained. I also experimented with MIPFocus, but since I am able to assume, based on the results I receive when the problem aborts that the solution is optimal or almost optimal I would prefer to stop the optimisation before the time limit hits. Furthermore, I would like to ensure that the optimal solutions that are solved within this small amount of times are still solved with optimal solutions while the MIPGap only applies to those slow problems.
How do I determine a suitable MIPGap for my problem?
(What I can't do and don't have are assumptions towards the precise reason and the properties of the graphs that cause to hit the time limit.)