Finding all feasible solutions

Answered

Akram Kh

• August 11, 2021 04:23

I need to find all feasible solutions of my milp model no matter if they are optimal or not. I have used the poolsolutions for this with the parameter "PoolSolutions =  2000000000" (max possible value). However, when I try this model with PoolSearchMode=2, I get different number of solutions in comparison with optimizing the same model with PoolSearchMode=1.

I suppose that solving a model with PoolSearchMode=2 should return the same number of solutions as solving the model with PoolSearchMode=1, as far as PoolGap equals infinity (its default value as in my case). Am I correct? If yes, what is the reason of the above observation?

I do appreciate any guidance in advance!

1

• 

  Tobias Achterberg

  Gurobi Staff

  • August 11, 2021 13:01
  • Edited

  No, you need to use PoolSearchMode=2 to really find all feasible solutions. With PoolSearchMode=1 there is no guarantee of exhaustiveness. For example, PoolSearchMode=1 would not disable dual presolve reductions. Those reductions allow to discard optimal solutions if one can prove that at least one optimal solution remains feasible in the presolved model.

  I agree, however, that our documentation of the PoolSearchMode parameter is not 100% clear on this.

  You could check whether

   PoolSearchMode=2

  is equivalent to

  PoolSearchMode=1 DualReductions=0.

  From source code inspection, I think that disabling dual reductions is really the only relevant difference.

  Regards,

  Tobias

   

  1
• 

  Akram Kh

  • August 12, 2021 07:11

  

  

  

  Dear Tobias,

  Thanks for your reply. That was a great help for me.

  Regards,

  Akram

  0

Please sign in to leave a comment.