1
$\begingroup$

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.)

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

I assume you want to solve a batch of problem with the same parameter settings, e.g. TimeLimits and MIPGap.

You can use the callback function. Each time an integer feasible solution is found, check whether the runtime is too long (e.g. 3600 s), if no, do nothing; else check whether the MIP gap is small enough to determine whether terminate.

Pyomo callback document: https://pyomo.readthedocs.io/en/stable/library_reference/solvers/gurobi_persistent.html#pyomo.solvers.plugins.solvers.gurobi_persistent.GurobiPersistent.set_callback

Gurobi callback document: https://www.gurobi.com/documentation/9.5/refman/py_cb_s.html

$\endgroup$
5
  • $\begingroup$ Thank you so far, one open question remains - how do I determine a suitable MIPGap. When is a MIPGap small enough. (I've read the documentation of MIPGap and AbsMIPGap but still can't say I understand what a suitable MIPGap for a particular problem. E.g. a graph with 200 nodes or a graph with 10 nodes is for a particular partitioning problem. $\endgroup$
    – baxbear
    Apr 22, 2022 at 9:50
  • $\begingroup$ Determine MIPGap is equivalent to define what is a "good enough" solution for you. For example, if your objective is roughly \$1000, you think \$10 makes no difference for you, then you can set MIPGap = 0.01. $\endgroup$ Apr 22, 2022 at 15:09
  • $\begingroup$ Thanks so far, wasn't sure that it works that simple - I don't know what I thought - felt like I missed something. Still I have another question that just came up: Assume, the solver finds a solution that is 5% better than the last solution with an selected MIPGap of 1% and the solution is optimal. Now the solver takes forever to proof that solution?!?! Does that thought make sense because than I assume that is what is happening (as far as I guess playing around with MIPGap values). $\endgroup$
    – baxbear
    Apr 22, 2022 at 16:18
  • $\begingroup$ Bonus: If my assumption is correct: Can I retrieve the wallclock time the computation needed to get to the result? Assuming my problem has a time limit and after a while the time limit hits but no better result has been found and therefore the MIPGap wasn't triggered. Can I still pinpoint the moment the solution has been found in the first place and retrieve the time from the result? $\endgroup$
    – baxbear
    Apr 22, 2022 at 16:31
  • 1
    $\begingroup$ It is possible to retrieve the incumbent solution (as well as runtime) that can not be improved within a certain time (assume the incumbent is optimized). This also requires implementation for a callback. $\endgroup$ Apr 22, 2022 at 16:54

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.