Documentation problem of paramerter InfUnbdInfo
AnsweredI got a problem that a model was reported as "infeasible or unbounded" when InfUnbdInfo=0 but "optimal" when InfUnbdInfo=1. I fixed a numerical problem in my model and got optimal results in both settings of InfUnbdInfo. But I think I was misled by the documentation of parameter InfUnbdInfo and maybe the documentation could be refined to improve clarity.
In the GUROBI OPTIMIZER REFERENCE MANUAL, InfUnbdInfo is depicted as
"Determines whether simplex (and crossover) will compute additional information when a model is determined
to be infeasible or unbounded. Set this parameter if you want to query the unbounded ray for unbounded models (through the UnbdRay attribute), or the infeasibility proof for infeasible models (through the FarkasDual and
FarkasProof attributes)."
My understanding from these words is that InfUnbdInfo will only take effects after finding the model is infeasible or unbounded,and only provide more information rather than change the result. I turned to a professional for help. He told me that setting InfUnbdInfo or not will change whether gurobi will adopt DualReduction and thus affects the solution accuracy. But I think this is not consistent with the current documentation, because the solver behavior before finding the model is infeasible or unbounded is also changed.
If this is only a problem of my understanding, just ignore it. Thanks.
-
Hi Shouyuan,
Thank you for sharing your feedback. we will take it into consideration. In the meantime, please note we opt to keep the doc short, and sometimes may be oversimplified.
What you have encountered is indeed a corner case that seems to arise due to the poor numeric.
0 -
Dear Shouyuan,
What Jue wrote is correct. Yet, we would be interested in reproducing the issue whereby setting the InfUnbdInfo parameter already changes the path for the first solve. Could you please upload that model (and the logs you obtained with and without the parameter set) to some sharing service such as Filemail, Dropbox, Box, Google Drive, or OneDrive?
We would like to make sure that we didn't miss something...
Thanks.
0 -
Thank you for your reply, Xavier. There is some inconvenience for me to upload my original model, but I have constructed a simple model that can reproduce the issue. Hope this will help.
Python code to reproduce the issue, tested on Windows 11 and Ubuntu 22.04.
import gurobipy as gp
from gurobipy import GRB
m = gp.Model()
N = 10000
x = [None] * N
y = [None] * N
z = [None] * N
for i in range(N):
x[i] = m.addVar(vtype=GRB.CONTINUOUS, name=f"x{i}", ub=1)
y[i] = m.addVar(vtype=GRB.CONTINUOUS, name=f"y{i}")
z[i] = m.addVar(vtype=GRB.CONTINUOUS, name=f"z{i}")
for i in range(1, N):
m.addConstr(x[i] == x[0] * 1.01**i, f'cx{i}')
m.addConstr(x[i] == x[i - 1] + z[i], f'cxz{i}')
m.addConstr(y[i] == y[i - 1] * 1.01, f'cy{i}')
m.addConstr(x[i] == y[i], f'cxy{i}')
m.setObjective(x[-1], GRB.MAXIMIZE)
m.setParam('InfUnbdInfo', 1) # without this, the model will be reported as infeasible.
m.optimize()Output with InfUnbdInfo=0
Set parameter Username
Academic license - for non-commercial use only - expires 2023-11-05
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 39996 rows, 30000 columns and 89991 nonzeros
Model fingerprint: 0xa2c0006e
Coefficient statistics:
Matrix range [1e+00, 2e+43]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [0e+00, 0e+00]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve time: 0.03s
Presolved: 39995 rows, 19999 columns, 79990 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Ordering time: 0.01s
Barrier statistics:
Dense cols : 1
AA' NZ : 9.998e+04
Factor NZ : 5.399e+05 (roughly 30 MB of memory)
Factor Ops : 8.618e+06 (less than 1 second per iteration)
Threads : 4
Barrier performed 0 iterations in 0.10 seconds (0.04 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with primal simplex
Solved in 1 iterations and 0.13 seconds (0.06 work units)
Infeasible modelOutput with InfUnbdInfo=1
Set parameter Username
Academic license - for non-commercial use only - expires 2023-11-05
Set parameter InfUnbdInfo to value 1
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 39996 rows, 30000 columns and 89991 nonzeros
Model fingerprint: 0xa2c0006e
Coefficient statistics:
Matrix range [1e+00, 2e+43]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [0e+00, 0e+00]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve time: 0.03s
Presolved: 39995 rows, 19999 columns, 79990 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Ordering time: 0.01s
Barrier statistics:
Dense cols : 1
AA' NZ : 9.998e+04
Factor NZ : 5.399e+05 (roughly 30 MB of memory)
Factor Ops : 8.618e+06 (less than 1 second per iteration)
Threads : 4
Barrier performed 0 iterations in 0.10 seconds (0.04 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with primal simplex
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Ordering time: 0.01s
Barrier statistics:
Dense cols : 1
AA' NZ : 9.999e+04
Factor NZ : 5.399e+05 (roughly 30 MB of memory)
Factor Ops : 8.618e+06 (less than 1 second per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.09715200e+16 2.47149889e+34 1.00e+10 1.29e+03 7.80e+14 0s
1 2.09715200e+16 2.47149889e+34 1.00e+10 1.29e+03 7.80e+14 0s
Barrier performed 1 iterations in 0.33 seconds (0.10 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 1389 iterations and 0.34 seconds (0.35 work units)
Optimal objective 1.000000000e+000 -
Thanks for the model. I was able to reproduce the issue, and we're looking into this.
0 -
Your understanding that "InfUnbdInfo will only take effects after finding the model is infeasible or unbounded" is correct. And you can see that the logs with both InfUnbdInfo values are similar until
Solved with primal simplex
After that, the parameter kicks in: as the presolved model was solved to infeasibility, the solver continues and tries to solve the unpresolved model to check this infeasibility, and it happens that dual solves this unpresolved model. The fact that the results differ is not that surprising, considering the highly problematic numerical properties of this model.
In summary, this is not a matter of differing paths, but of path extension.
0
Please sign in to leave a comment.
Comments
5 comments