2
$\begingroup$

I have a binary linear program, where all my variables are binary. So, I have implemented the problem on python with Gurobi solver. I have implemented also a heuristic to find a near-optimal solution.

1- if I give the solution returned by my heuristic, can improve the performance of the Gurobi solver in terms of time complexity?

2- How I can introduce the solution returned by my heuristic to the API of Gurobi solver using python? I Can't find the right instructions to do. If there is a complete example that will be very helpful.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

1- It is likely that the performance will be improved, but it is not guaranteed. In general I would always recommend to provide a start solution.

2- You can use the Start attribute. An example would look something like this:

model = gp.Model()
x = model.addVar()
x.Start = 5  # This is the start solution
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you bro that's work good. I tested to give the optimal solution as a start solution but the solver still working, I think to prove the optimality of the solution, but that affects the time resolution. there are some think to do about that? $\endgroup$
    – MAJID majid
    Commented Dec 2, 2021 at 8:35
  • $\begingroup$ This can depend on a ton of different things. Do you need to prove optimality though? If not, then just terminate the solve. If you do, maybe try setting MIPFocus=2 and see whether this helps. $\endgroup$
    – Richard
    Commented Dec 2, 2021 at 13:59
  • $\begingroup$ I tested and doesn't help. Please, the initial solution can increase the running time of the solver? $\endgroup$
    – MAJID majid
    Commented Dec 2, 2021 at 14:26
  • $\begingroup$ It can happen, although rarely, you should test whether it does. $\endgroup$
    – Richard
    Commented Dec 3, 2021 at 8:49
3
$\begingroup$

You can try the VarHintVal or Start variable attributes. Make sure you check the solver logs to see if your heuristic provides a feasible solution.

If the solution takes longer it may be the case that your initial solution was infeasible or your heuristic is worse than those implemented in Gurobi (they have some pretty good heuristics). In both cases the solver has to determine whether the solution is feasible or not (which takes some time), and then run mostly as usual. If either your solution is infeasible or their heuristic is better, your solution will be discarded, leading to longer times than no warm-start.

Improve this answer
$\endgroup$
4
  • $\begingroup$ nice to see you around here :) $\endgroup$
    – Kuifje
    Commented Dec 3, 2021 at 15:47
  • $\begingroup$ My initial solution is feasible and it is better( in terms of objective function value) than the heuristic used by gurobi. but for both cases, the solver can find the optimal solution in the early iteration but to prove it optimality gurobi takes a long time. So, i think in my problem there is no need to give an initial solution. What do you think about? $\endgroup$
    – MAJID majid
    Commented Dec 3, 2021 at 19:31
  • $\begingroup$ @MAJIDmajid In that case, you have to explore other ways of dealing with the problem: try another solver, find stronger formulations, or cuts... If you only want a fast solution, try Gurobi Tuning tool, which basically tries to find the best parameter settings for your problem (in terms of speed if you only feed it a single problem). You can ask a separate question, I'm sure you'll get some some good answers $\endgroup$
    – David Torres
    Commented Dec 6, 2021 at 10:54
  • $\begingroup$ @Kuifje same :) $\endgroup$
    – David Torres
    Commented Dec 6, 2021 at 10:54
0
$\begingroup$

So here is my experience (and also some wisdom of other ppl i read) with setting lower bounds for minimization problems: Depending on the complexity of the model or your strategy for cutting invalid solutions of (tightness of the cuts) it might indeed be worse to set a lower bound, because it messes with the internal pricing gurobi uses. All the nodes that are still to be visited, get truncated to the same obj-value and there is no way to prioritize the more promising nodes, which mostly leads to vising random nodes, which then in turn also branch with the same obj-value and before you can derive any reasonable cuts you end up with a much bigger tree.

Now back to your issue when setting a good starting solution (or an upper bound in general): It is possible that setting such good starting solution (or even an optimal one) cuts off branches of the tree, which would otherwise be examinated and might produce better cuts or direction for moving that upper bound further up or something of this sorts. But in contrary to setting lower bounds, which seems to generally perform worse, this is more of an accident. In general it should be a good idea to set better initial solutions - it might just be worse in your specific case (problem instance)

Improve this answer
$\endgroup$

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.