Skip to main content

Gurobi missing optimal solutions?

Answered

Comments

9 comments

  • Ronald van der Velden
    Gurobi Staff Gurobi Staff

    Hi Rui,

    Just to be sure - Unless you're using the solution pool functionality, Gurobi does not necessarily return all optimal solutions.

    In general, if you feel a solution should be returned (and considered feasible) while Gurobi does not generate it, what you should do is fix the variables to exactly that solution. So for each variable, set its LB and UB attributes to the value you have in mind. Then ask Gurobi to solve the model. You should now see one of these cases:

    • Gurobi returns your solution; you should inspect the objective function value. Perhaps it's worse than the solution Gurobi previously found, which could indicate an issue with data or model. Or, it has the same objective function value but Gurobi just ended up returning another, equally optimal solution.
    • Gurobi says the model is infeasible. In this case, you can use functionality like computeIIS and feasRelax to understand why the solution is considered infeasible.

    Kind regards,
    Ronald

    0
  • Gwyneth Butera
    Gurobi Staff Gurobi Staff

    A related article in the Knowledge Base is Why does Gurobi report my model is infeasible when it has a feasible solution?

    0
  • Rui Miguel
    First Comment
    First Question

    Hi! Many thanks for the prompt responses.

    • I am indeed using SolutionPools.
        # Parameters
        m.Params.PoolSearchMode = 2  # Value of 2 means find the n best solutions
        m.Params.PoolSolutions = 10  # Number n of solutions to find
        m.Params.PoolGap = 0.0       # Tolerance gap for optimal value
    • I tried fixing the lower and upper bounds of the variables leading to the other feasible solution. That solution is indeed returned, and the objective function value is the same. The former solution, [1.0, 0.0, 0.0, 1.0, 0.0, 0.0], is no longer returned in this case.
      Solution count 1: 0 
      No other solutions better than 0

      Optimal solution found (tolerance 1.00e-04)
      Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
      [0.0, 1.0, 0.0, 0.0, 1.0, 0.0]
    • I've also tried setting other parameters that have to do with numerical issues (and even tried combinations of each), but to no avail:
        m.Params.IntFeasTol = 1e-1 # Also tried 1e-9
        m.Params.IntegralityFocus = 1
        m.Params.Heuristics = 0
    • If my interpretation of the article is correct, the printed statistics and quality do not seem to hint at any numerical issues:
      Statistics for model mip:
        Linear constraint matrix    : 20 Constrs, 6 Vars, 36 NZs
        Variable types              : 0 Continuous,
      6 Integer (6 Binary)
        Matrix coefficient range    : [ 1, 25000 ]
        Objective coefficient range : [ 0, 0 ]
        Variable bound range        : [ 1, 1 ]
        RHS coefficient range       : [ 1, 60000 ]

      Solution quality statistics for model mip :
        Maximum violation:
          Bound       : 0.00000000e+00
          Constraint  : 0.00000000e+00
        Integrality : 0.00000000e+00

     

    0
  • Rui Miguel
    First Comment
    First Question

    Hello again!

    I found a parameter that worked! m.Params.Presolve = 0 fixed it. Both solutions are now correctly printed:

    Solution count 2: 0 0 
    No other solutions better than 0

    Optimal solution found (tolerance 1.00e-04)
    Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
    [0.0, 1.0, 0.0, 0.0, 1.0, 0.0]
    [1.0, 0.0, 0.0, 1.0, 0.0, 0.0]

    Also tried toying with m.Params.Aggregate = 0 and m.Params.NumericFocus = 3, but these did not change the result.

     

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    Does the latest version of Gurobi (12.0.0) also fail to find one of the optimal solutions when setting PoolSearchMode to 2? If so, can you please write out an MPS model file and post the file contents here?

    m.write("model.mps")
    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    @Eli, here is a MRE on a smaller (but similar) model for v12

    m = gp.Model()
    x = m.addVars(2, vtype="B", name="x")
    y = m.addVars(2, vtype="B", name="y")

    m.setObjective(y[0]*x[1] + y[1]*x[0])

    m.addConstr(x.sum() == 1)
    m.addConstr(y.sum() == 1)

    m.params.PoolSearchMode=2
    m.params.PoolGap=0
    #m.params.Symmetry=0 # uncomment to get both valid solutions
    m.optimize()

    Symmetry seems to be at play.  Adding a continuous variable to the model is also enough to avoid the buggy behavior.

     

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Rui,

    I'll open a support request in our Gurobi Help Center to continue the discussion on this issue.  You will receive an email shortly.

    - Riley

    0
  • Rui Miguel
    First Comment
    First Question

    Greetings once more,

    Thank you for the responses, for setting up the support thread, and for providing the workarounds!

    I deduce it is no longer necessary to test in Gurobi v12.0.0? It doesn't seem to be available for me to install using pip. Is it possible my system is not compatible with the latest version? I'm on Ubuntu 20.04.

    rui@rui-Lenovo-V15-G2-ALC:~$ python3 -m pip install gurobipy --upgrade
    Requirement already up-to-date: gurobipy in ./.local/lib/python3.8/site-packages (11.0.3)
    rui@rui-Lenovo-V15-G2-ALC:~$ python3 -m pip install gurobipy==12.0.0
    ERROR: Could not find a version that satisfies the requirement gurobipy==12.0.0 (from versions: 9.1.0, 9.1.1, 9.1.2, 9.5.0, 9.5.1, 9.5.2b0, 9.5.2, 10.0.0b1, 10.0.0, 10.0.1, 10.0.2, 10.0.3, 11.0.0b1, 11.0.0, 11.0.1, 11.0.2, 11.0.3)
    ERROR: No matching distribution found for gurobipy==12.0.0
    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Rui,

    No need to test V12, we have done this already, thanks.

    You'll need a more recent version of Python to use Gurobi V12.

    See the following article for details
    https://support.gurobi.com/hc/en-us/articles/360013195212-Which-Python-versions-are-supported-by-Gurobi

    - Riley

    0

Please sign in to leave a comment.