Questions regarding partition heuristic, branching priorities & DistributedMIPJobs

Answered

Thomas Leveringhaus

• July 31, 2020 08:06

Hi everybody,

I'd appreciate it if you'd answer my questions regarding branching priorities, the partition heuristic, their interactions and the operating principle of DistributedMIPJobs. I have tried to find answers in the documentation, but I have not found this specific information.

Regarding branching priorities in general:
# Are variables allowed to be assigned the same branching priorities, so that, for example, a group of variables has the same branching priority 1, and other groups of variables have the same branching priorities 2, 3, 4, ...?
## So how does Gurobi decide the order in which variables with the same branching priority are to be branched?
# Does it make a difference if I assign branching priorities with consecutive numbers (e.g.: 1, 2, 3, 4, ...) or with different weights (e.g.: 1, 2, 5, 10, 100, 1000, ...)?

Regarding the interaction of branching priorities and the partition heuristic:
# How are branching priorities and partition heuristic interacting? When I give Gurobi information on both, are the branching priorities evaluated only subordinately within each partition or do the branching priorities "overwrite" the partition heuristic? Can I use the parameter PartitionPlace to influence the behaviour?

Regarding the DistributedMIPJobs:
# If I enable the DistributedMIPJobs parameter, can I influence how MIPJobs are distributed to the workers?
# Can the partition heuristic be combined with the DistributedMIPJobs parameter and would the partitions then be distributed to the workers? What happens if I have more partitions than workers (or vice versa)?

Thank you very much for your assistance

Thomas Leveringhaus

0

• 

  Sonja Mars

  Gurobi Staff

  • August 03, 2020 08:03

  Hi Thomas,

  Branching priority:

  1. Yes, variables are allowed to have the same branching priority.
  2. Gurobi picks the order of the variables to branch on with an internal not public algorithm. 
  3. Gurobi will pick the variables with the highest priorities first, no matter if 5 is the highest number or 50 000. 

  Partition heuristic:

  Branching priorities are used throughout the whole search tree and the whole branch-and-bound search. The partition heuristic is a special improvement heuristic that only runs in a few different places (depending on your choice). The branching priorities don't overwrite the partition heuristic. If you specified a partition and a place where you want it to run, this heuristic on the partitions you used will run and try to find a better feasible solution. 

  DistributedMIPJobs:

  1. No, it is more or less the same as on a single machine. Gurobi will determine which nodes are solved on which worker (or on which thread in the non-distributed case). 
  2. Yes, you can combine those, but I don't think we do it in the way you are looking for. It depends a bit on when you want to call the partition heuristic. For example the root node is not solved in a distributed way, if you run DistributedMIP. We start DistributedMIP with a ramp-up phase. This is a concurrent approach to find a good starting point for the rest of the search. The partition heuristic will be integrated into this approach. 

  Best,

    Sonja

  0
• 

  Thomas Leveringhaus

  • August 04, 2020 20:06

  

  

  

  Hi Sonja,

  
  Thank you very much for your answer.

  It will take me some time to evaluate all the options, but now I know that I can move in that direction.

  
  Best regards

  
  Thomas

  0

Please sign in to leave a comment.