Is optimality guaranteed when using the Partition heuristic
OngoingHello,
I've been unable to find sufficient information on the Partition heuristic. Our team is trying to improve the solution speed for our model and dividing our variables into partitions seems like it could help, but we are not sure what it does: our intuitive view was that we can divide variables into partitions such that the values of two variables from different partitions are more or less independent. That is, we thought that the heuristic is there only to improve solution speeds, not the solution itself.
However, here in the docs, it says that
... subMIP 1 would fix variables 099 and 300399 to their values in the incumbent ...
This sounds like the model might not arrive at the global optimum of our model. Is the heuristic only there to improve speeds, or does it change optimization overall, then?
More specifically for our use case: we optimize shift scheduling (for several days), and were thinking of
 either having one partition for each day, so that the partition would consist of variables representing shifts in the same day,
 or maybe partitioning by employee: putting variables representing shifts of one person to one partition.
Are we thinking of the heuristic the right way? If yes, which of the two would you say is better? Even though the variables of one day interact mostly with one another, they are not completely independent on other days (because of laws, employee preferences, etc...) and we don't want to lose optimality.
Thank you in advance, best regards.
Martin

Hi Martin,
Is the heuristic only there to improve speeds, or does it change optimization overall, then?
Indeed, the partition heuristic is just there to improve incumbent solutions and performance. It will not affect proving optimality (which also involves closing the dual bound which has nothing to do with the incumbent but more with cuts etc).
Initially, I would suggest trying the variations you suggest to see if the partition heuristic helps, if not, you can try e.g. NoRel. And if that is not enough please open a ticket, we can of course also help!
Cheers,
David1 
Thanks for the quick answer!
0 
Hi David,
followup question: how often is this heuristic run? Every time we get a new incumbent? Or only at the root?
Is there a way to control this?
Cheers,
Martin
0 
Hi Martin,
Indeed, you can control this with the PartitionPlace parameter.
Cheers,
David1 
Hello again, David,
I finally got to trying the two ways of splitting the variables into partitions, as mentioned in my original Q (as a sanity check, this splits the variables roughly uniformly).
Surprisingly though, this lead to no change. All three options (no Partition set, Partition for each day, Partition for each employee) seem to reach almost the same gaps in the same amount of time. So much so that I'm thinking whether the partition heuristic is even run. Is it correct that it should be computed once at least one variable has the Partition attribute set? Is there a way to make Gurobi print some info whenever it computes the heuristic, so that I can see that it does?
Cheers,
Martin
0
Please sign in to leave a comment.
Comments
5 comments