Skip to main content

How to make Gurobi avoid giving non integral solutions.

Awaiting user input
Prasanna Kumar Reddy Sabbella
Gurobi-versary
First Comment
First Question

Hi,

Kindly read this till the end to understand it correctly. I'm facing a problem with duplicate feasible solutions when trying to solve a integer LP.

Let's say X1 = 0.999 and X2 = 0 is a solution, then Gurobi gives out another solution with X1 = 1.0003 and X2 = -0.0001 which is basically the same as before. So, how would I avoid this? 

 

 

I have tried using "m.setParam('IntegralityFocus',1)" but it did not work. I have also looked into other documentations shown below, but nothing really helped.

 

And the other thing that it does when I try to find maximum possible feasible solutions is that it not only gives out duplicate set of solutions (not a problem cause I could somehow eliminate dupes after it gives them out) but it misses some feasible solutions. So how do I make Gurobi not to give out duplicates and at the same time not to miss out few possible feasible solutions?

0

Comments

3 comments

Date Votes
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Prasanna, 

    Let's say X1 = 0.999 and X2 = 0 is a solution, then Gurobi gives out another solution with X1 = 1.0003 and X2 = -0.0001 which is basically the same as before. So, how would I avoid this? 

    I am not sure what you mean by how you can avoid this. This is an unfortunate reality in a MIP solver. Tolerances such as IntFeasTol are used to address the inevitable round-off errors in floating-point arithmetic. 

    It seems to me that you would like to find as many distinct feasible solutions as possible. Have you considered using non-default values of PoolSearchMode such as 1 and 2? Setting this parameter to a non-default value forces the Gurobi Optimizer to continue the search after proving optimality to find \(n\) solutions with \(n\) being equal to the parameter PoolSolutions. 

    It is also worth mentioning that the Gurobi Optimizer discards a solution if it is equivalent to another solution already in the pool. Two solutions are considered equivalent if they take the same values on all integer values and on all continuous variables in the SOS constraints. In a binary optimization problem, if \(x_1\) and \(x_2\) are two feasible solutions, they are considered equivalent if \(\lfloor{x_1^j + 0.5\rfloor}\) equals \(\lfloor{x_2^j + 0.5\rfloor}\) for all \(j\). 

    Best regards,

    Maliheh

    0
  • Prasanna Kumar Reddy Sabbella
    • Edited
    Gurobi-versary
    First Comment
    First Question

    Thank you for the reply Maliheh. Have you considered using non-default values of PoolSearchMode such as 1 and 2?

    Yes I did. I have printed out 18192 solutions. What I found was that there are many duplicate solutions, which does not bother me because I can simply delete the duplicates later, but however, what I'm worried about is that I'm aware of a feasible solution that Gurobi did not produce and there might be many such solutions that might be missing, I just found one. Sorry, if it still confuses you, I'm not a good writer.

     

     

    Please do note that my objective function is just a dummy. m.setObjective(0, GRB.MAXIMIZE). I'm trying to find all possible combination of feasible integral values to my variables just based on the constraints.

    My params are as follows:

    m.setParam('PoolSolutions',20,000) # 20000 is just a random number on my head.
    m.setParam('PoolSearchMode',1)

    It gave out 18192 solutions. Though there are duplicate solutions in this list of 18192, I thought it contained all possible feasible solutions because it stopped exactly at 18192 even when asked for 20,000 of them. (But I was wrong: I know a feasible solution is definitely missing among the 18192).

    Now I have forced it to give 20,000 of them by setting ('PoolSearchMode',2). It did give out 20,000 of them and indeed there are duplicate solutions, yet not every possible feasible solution.

    My question: How do I make Gurobi avoid giving out duplicate solutions but more importantly not to miss even a single possible feasible solution.

    Could you please suggest how exactly do I use IntFeasTol in my code? I'm using Python and I have about close to 170 binary integer variables. Should I set this IntFeasTol to a low value for every one of the variables?

     

    Thank you so much for the patience.

     

    0
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Prasanna,

    What I found was that there are many duplicate solutions, which does not bother me because I can simply delete the duplicates later,

    The solutions added to the pool should be distinct. Does your model include any SOS constraints or bilinear constraints involving continuous variables? If you only have binary variables in your model, for each pair of solutions \(x_1\) and \(x_2\) in the pool, there should be at least one binary variable \(i\) where \(\lfloor{x^i_1 + 0.5}\rfloor\) should not be equal to \(\lfloor{x^i_2 + 0.5}\rfloor\). Does this hold true for solutions you see?

    It gave out 18192 solutions. Though there are duplicate solutions in this list of 18192, I thought it contained all possible feasible solutions because it stopped exactly at 18192 even when asked for 20,000 of them. 

    Have you set any other termination criterion such as TimeLimit? If the model terminates with an OPTIMAL status and the solution pool includes only 18192 solutions while you have asked for 20000 solutions, this implies that Gurobi has proven that there is no other feasible solution. 

    My question: How do I make Gurobi avoid giving out duplicate solutions but more importantly not to miss even a single possible feasible solution.

    As already discussed, if you set the parameter PoolSearchMode to a non-default value, do not set any other termination criterion, the Gurobi Optimizer will continue the search until finding \(n\) feasible solutions with \(n\) being equal to the PoolSolutions value. If the solver returns an OPTIMAL status and there are less than \(n\) solutions in the pool, this means that the solver has found all feasible solutions.

    Gurobi will not find more feasible solutions than the value of the PoolSolutions parameter. Do you know how many feasible solutions exist in your model? This number can be exponentially large for some models and sometimes hard to know in advance.

    Please do note that my objective function is just a dummy. m.setObjective(0, GRB.MAXIMIZE).

    Since all solutions have the same quality, there is no difference between using PoolSearchMode 1 or 2. 

    (But I was wrong: I know a feasible solution is definitely missing among the 18192).

    How do you know that this is a feasible solution? What happens if you fix the model variables to the values in this solution? Does Gurobi declare feasibility?

    The points you mentioned are contradictory to what we expect to see. If you have a simple example where you can show that Gurobi terminates with an OPTIMAL status, returns less feasible solutions than the value specified by the PoolSolutions parameter, and it misses one known feasible solution, please share it with us. We can then try to understand what might be the issue.

    Could you please suggest how exactly do I use IntFeasTol in my code? I'm using Python and I have about close to 170 binary integer variables. Should I set this IntFeasTol to a low value for every one of the variables?

    This is a parameter and not an attribute. You can set it on your model object like \(\texttt{model.params.IntFeasTol}\)\(=1e^{-6}\), for example.

    Best regards,

    Maliheh

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post