Recursively Solving for N Solutions in Pool with Overlap Parameter

Ongoing

Kat K

March 16, 2022 16:50 Edited

• 
• 
• 

Hello! I'm using Gurobi in R to develop a solution set of size n with a maximum overlap parameter k (i.e., no solutions share more than k variables in common with another solution - the format of my solution is a bunch of binary variables indicating whether objects should be selected or not). I'm currently using PoolSearchMode = 2 and PoolSolutions =  a much larger number than n so I can use a different function after solving to filter my solution set down based on overlap.

Is there a way to recursively solve one at a time, and only add solutions to my solution pool if they don't overlap more than k times with other solutions? And then stop when I get to a solution pool size of n? 

I'm new to using Gurobi so any help with coding/pseudocode would be much appreciated!

0

• 

  Jaromił Najman

  • Gurobi Staff

  March 16, 2022 08:34

  Hi Kat,

  Is there a way to recursively solve one at a time, and only add solutions to my solution pool if they don't overlap more than k times with other solutions? And then stop when I get to a solution pool size of n? 

  It is possible. However, it requires quite some work, because you have to make sure that previous solutions are excluded from the feasible space. This would most likely result is some form of B&B algorithm. I think that is it way more convenient to use your approach, i.e., use PoolSearchMode and PoolSolutions to generate many solution point and then check those for overlapping.

  I am not familiar with R so unfortunately I cannot really help with a pseudo code.

  Best regards, 
  Jaromił

  0
• 

  Kat K

  March 16, 2022 16:50

  • 
  • 
  • 

  Hi Jaromił,

  Thanks for the reply. Unfortunately I'm finding my run time is extremely long if I keep PoolSearchMode and PoolSolutions - I've seen a similar question where the person recursively re-solved with additional constraints here:

  https://support.gurobi.com/hc/en-us/community/posts/360043374531-Solve-time-issues-with-solution-overlap-parameter

  This is what I'm trying to accomplish, but don't know how to set that up. Thanks!

  0

Please sign in to leave a comment.