Need help understanding the output of Gurobi for an IP problem
Answered
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
-
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 -
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, beginh[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,
Christos0 -
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 -
Hello and thank you for your response,
I will try study and try to replicate the example in JuMP.
Kind regards,
Christos0 -
Alright it works! I must have made a mistake before to get the same result always.
Thank you so much for your help,
Christos0
Please sign in to leave a comment.
Comments
5 comments