Skip to main content

Need help understanding the output of Gurobi for an IP problem

Answered
Christos Kolomvakis
  • Gurobi-versary
  • First Comment
  • First Question

Hello everyone,

I am writing this post to get a deeper understanding over how gurobi solves a specific ip that I am dealing with.

The problem is the following:

min_(h,z)  3 - z_2 - z_4 - z_5 + z_1 + z_3
s.t.            h and z binary {0,1} with 5 elements
                 h_2/5 <= z_1 <= h_2
                 h_2/5 <= z_3 <= h_2          
                 (h_1 + h_3 + h_4)/5 <= z_2 <= h_1 + h_3 + h_4
                 (h_1 + h_3 + h_4)/5 <= z_5 <= h_1 + h_3 + h_4
                 (h_5 + h_3 + h_4)/5 <= z_4 <= h_5 + h_3 + h_4

The solution for z is [0 1 0 1 1]. For h, Gurobi always returns [1 0 0 0 1]. However, [0 0 1 0 0] and [0 0 0 1 0] are also possible solutions but are never returned. So my question is, why does Gurobi always compute [1 0 0 0 1] but never the other two solutions? Is there a way to make it compute the other solutions as well?

I tried increasing the SolutionNumber variable but that did not seem to help. I also tried all possible methods offered by Gurobi (the method variable for the model). Setting PoolSearchMode to 2 also did not help.

If there is a page related to a similar issue, please redirect me there. I am sorry if the answer is obvious and I am missing something.

Thanks in advance,
Christos

0

Comments

5 comments

Date Votes
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Christos,

    Did you increase the number of PoolSolutions? 

    Could you please share the code you used to generate the different solutions?

    Best regards, 
    Jaromił

    0
  • Christos Kolomvakis
    Edited
    • Gurobi-versary
    • First Comment
    • First Question

    Hello,

    my apologies for not posting the code, here it is (in Julia):

    model = Model(() -> Gurobi.Optimizer(env))
    # set_silent(model)
    # set_optimizer_attribute(model, "OutputFlag", 0)
    # set_optimizer_attribute(model, "LogToConsole", 0)
    set_optimizer_attribute(model, "NonConvex", 2)
    @variable(model, y[1:m], Bin)
    @variable(model, h[1:r], Bin)
    @objective(model, Min, 3 - 2*y[2] - 2*y[4] - 2*y[5] + y[1] + y[2] + y[3] + y[4] + y[5])
    @constraints(model, begin
    h[2]/r <= y[1]
    y[1] <= h[2]
    h[2]/r <= y[3]
    y[3] <= h[2]
    (h[1]+h[3]+h[4])/r <= y[2]
    y[2] <= h[1] + h[3] + h[4]
    (h[1]+h[3]+h[4])/r <= y[5]
    y[5] <= h[1] + h[3] + h[4]
    (h[5]+h[3]+h[4])/r <= y[4]
    y[4] <= h[5] + h[3] + h[4]
    end)

    set_time_limit_sec(model,timelimit)
    JuMP.set_optimizer_attribute(model, "PoolSolutions", 20)
    JuMP.optimize!(model)

    println(JuMP.value.(h))
    println(JuMP.value.(y))

    I set the PoolSolutions to 20 but that did not seem to influence the result.

    Thanks for your quick response,
    Christos

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff
    Edited

    Hi Christos,

    I am not a JuMP user so I unfortunately cannot help much with your code. However, I tested your model and the setting in gurobipy. I used the poolsearch.py example to check how the PoolSolutions feature works. I used the below code

    import gurobipy as gp
    from gurobipy import GRB

    m = gp.Model()

    N = [1,2,3,4,5]

    y = m.addVars(N, vtype = GRB.BINARY, name="y")
    h = m.addVars(N, vtype = GRB.BINARY, name="h")

    m.setObjective(3 - 2*y[2] - 2*y[4] - 2*y[5] + y[1] + y[2] + y[3] + y[4] + y[5])

    r = 5

    m.addConstr(h[2] / r <= y[1])
    m.addConstr(y[1] <= h[2])
    m.addConstr(h[2] / r <= y[3])
    m.addConstr(y[3] <= h[2])
    m.addConstr((h[1] + h[3] + h[4])/r <= y[2])
    m.addConstr(y[2] <= h[1] + h[3] + h[4])
    m.addConstr((h[1] + h[3] + h[4])/r <= y[5])
    m.addConstr(y[5] <= h[1] + h[3] + h[4])
    m.addConstr((h[5] + h[3] + h[4])/r <= y[4])
    m.addConstr(y[4] <= h[5] + h[3] + h[4])

    # write a human readable model file to check whether the model is correct
    m.write("myLP.lp")

    # set parameters
    m.setParam("PoolSearchMode",2)
    m.setParam("PoolSolutions", 10)
    m.optimize()

    # get number of solutions
    nSolutions = m.SolCount

    # iterate over all solutions and print the objective
    # and variable values
    for e in range(nSolutions):
        m.setParam("SolutionNumber",e)
        print(f"obj: {m.PoolObjVal}")
        for i in N:
            print(f"{y[i].VarName}: {y[i].Xn}")
        for i in N:
            print(f"{h[i].VarName}: {h[i].Xn}")

        print("================================")

    When I run this code on my personal Mac using Gurobi v11 I get the solutions

    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: 0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: 1.0
    h[2]: 0.0
    h[3]: 1.0
    h[4]: 1.0
    h[5]: 1.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: -0.0
    h[2]: -0.0
    h[3]: -0.0
    h[4]: 1.0
    h[5]: -0.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: 1.0
    h[2]: -0.0
    h[3]: 1.0
    h[4]: -0.0
    h[5]: -0.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: 1.0
    h[2]: -0.0
    h[3]: -0.0
    h[4]: -0.0
    h[5]: 1.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: -0.0
    h[2]: -0.0
    h[3]: 1.0
    h[4]: -0.0
    h[5]: 0.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: -0.0
    h[2]: -0.0
    h[3]: 0.0
    h[4]: 1.0
    h[5]: 1.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: 1.0
    h[2]: -0.0
    h[3]: -0.0
    h[4]: 1.0
    h[5]: 0.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: -0.0
    h[2]: -0.0
    h[3]: 1.0
    h[4]: 1.0
    h[5]: -0.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: -0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: -0.0
    h[2]: -0.0
    h[3]: 1.0
    h[4]: -0.0
    h[5]: 1.0
    ================================
    obj: 0.0
    y[1]: 0.0
    y[2]: 1.0
    y[3]: 0.0
    y[4]: 1.0
    y[5]: 1.0
    h[1]: 1.0
    h[2]: 0.0
    h[3]: 1.0
    h[4]: 1.0
    h[5]: -0.0
    ================================

    You can see that the objective value and y variable values are always the same and the values for h variables change.

    I don't know how to replicate the Python code in JuMP but maybe someone else in the Community might help.

    Best regards, 
    Jaromił

    0
  • Christos Kolomvakis
    • Gurobi-versary
    • First Comment
    • First Question

    Hello and thank you for your response,

    I will try study and try to replicate the example in JuMP.

    Kind regards,
    Christos

    0
  • Christos Kolomvakis
    • Gurobi-versary
    • First Comment
    • First Question

    Alright it works! I must have made a mistake before to get the same result always.

    Thank you so much for your help,
    Christos

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post