Is optimality guaranteed when using the Partition heuristic

Ongoing

Martin Koreček

• October 25, 2023 09:34
• Edited

Hello,

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

... sub-MIP 1 would fix variables 0-99 and 300-399 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

Related to

• Performance
• Heuristics

0

• 

  David Torres Sanchez

  Gurobi Staff

  • October 25, 2023 11:16
  • Edited

  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, 
  David

  1
• 

  Martin Koreček

  • October 25, 2023 11:21

  

  

  Thanks for the quick answer!

  0
• 

  Martin Koreček

  • October 27, 2023 14:44

  

  

  Hi David,

  follow-up 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
• 

  David Torres Sanchez

  Gurobi Staff

  • October 27, 2023 15:25

  Hi Martin,

  Indeed, you can control this with the PartitionPlace parameter.

  Cheers, 
  David

  1
• 

  Martin Koreček

  • November 07, 2023 10:16

  

  

  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.