Lower Bound stays at 0
Answered
I have a MIP model, when I try to solve, the best Bound never exeeds 0.
mdl = Model("BOBS")
x = mdl.addVars(A, vtype=GRB.BINARY)
y = mdl.addVars(OI, vtype=GRB.BINARY)
c = mdl.addVars(I0n, vtype=GRB.CONTINUOUS)
t = mdl.addVars(SI, vtype=GRB.CONTINUOUS)
mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(quicksum(quicksum(y[o,i]*c[i] for i in I) for o in O))
# Nebenbedingungen
mdl.addConstrs(quicksum(x[i, j] for i in I0 if j != i) == 1 for j in In)
mdl.addConstrs(quicksum(x[i, j] for j in In if j != i) == 1 for i in I0)
mdl.addConstrs((x[i, j] == 1) >> (c[i] == c[j]-p[j]) for i in I0 for j in In if i != j)
mdl.addConstrs(quicksum(y[o, i] for i in I ) == 1 for o in O)
mdl.addConstrs((x[i, j] == 1) >> (t[s,j] == t[s,i] + bins[j][s] - quicksum(y[o,j]*orders[o][s] for o in O)) for i in I0notN for j in I if i != j for s in S)
mdl.addConstrs(t[s,0] == 0 for s in S)
mdl.addConstrs(t[s,i] >= 0 for s in S for i in I0)
mdl.addConstr(c[0]==0)
#mdl.setParam(GRB.Param.TimeLimit, 600)
mdl.optimize()
What can I adjust in this model so Gurobi finds better Bounds?
-
Hi Xaver,
Can you post a log file?
- Riley
0 -
Gurobi 10.0.3 (win64) logging started Mon Jul 22 08:19:07 2024
Set parameter LogFile to value "Log"
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)
CPU model: AMD Ryzen 7 3700X 8-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 323 rows, 1165 columns and 1751 nonzeros
Model fingerprint: 0x5bc37c40
Model has 288 quadratic objective terms
Model has 6361 general constraints
Variable types: 276 continuous, 889 integer (889 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [0e+00, 0e+00]
QObjective range [2e+00, 2e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
GenCon rhs range [1e+00, 5e+01]
GenCon coe range [1e+00, 8e+01]
Presolve added 6075 rows and 6325 columns
Presolve time: 0.07s
Presolved: 6974 rows, 8354 columns, 36698 nonzeros
Presolved model has 6937 SOS constraint(s)
Variable types: 7177 continuous, 1177 integer (1177 binary)
Root relaxation: objective 0.000000e+00, 1754 iterations, 0.01 seconds (0.01 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 0 0.00000 0 65 - 0.00000 - - 0s
0 2 0.00000 0 65 - 0.00000 - - 0s
H 2684 2532 510.0000000 0.00000 100% 3.2 2s
H 2722 2806 508.0000000 0.00000 100% 3.2 2s
H 2866 2806 507.0000000 0.00000 100% 3.1 2s
H 2902 2806 505.0000000 0.00000 100% 3.1 2s
H 3011 3144 499.0000000 0.00000 100% 3.1 3s
* 3036 3138 208 482.0000000 0.00000 100% 3.1 3s
* 3038 3138 209 479.0000000 0.00000 100% 3.1 3s
* 3039 3138 209 474.0000000 0.00000 100% 3.1 3s
H 3399 3600 472.0000000 0.00000 100% 3.0 3s
H 3542 3600 471.0000000 0.00000 100% 3.0 3s
H 4003 4056 465.0000000 0.00000 100% 2.9 3s
H 4096 4056 464.0000000 0.00000 100% 2.9 3s
H 4165 4052 445.0000000 0.00000 100% 2.9 3s
H 4471 3851 442.0000000 0.00000 100% 2.8 4s
H 4522 3697 439.0000000 0.00000 100% 3.2 4s
4622 3797 0.00000 22 68 439.00000 0.00000 100% 3.3 5s
...0 -
Hi Xaver,
What you're observing is the result of a weak linear relaxation. You may find the following webinar useful: Tech Talk – Converting Weak to Strong MIP Formulations
Presolved model has 6937 SOS constraint(s)
Your general constraints get converted to SOS constraints, and then presolve potentially converts these SOS constraints to linear constraints. From the docs linked above:
It is often more efficient to capture SOS structure using linear constraints rather than SOS constraints. The optimizer will often perform this reformulation automatically. .... The reformulation adds constraints of the form x <= Mb. where x is the variable that participates in the SOS constraint, b is a binary variable, and M is an upper bound on the value of variable x. Large values of M can lead to numerical issues.
If a SOS constraint is not translated to a linear constraint then this represents a part of the linear relaxation which is missing. In an extreme case, where every constraint is a SOS there is no linear relaxation at all.
To give yourself the best chance of SOS constraints being translated it is important to set the best bounds on variables you can - this will feed into the calculation of the "M" values. Bounds on variables are particularly important when those variables are involved in quadratic terms.
You do have some control over the translation of SOS constraints to linear constraints, via the parameters PreSOS1BigM and PreSOS2BigM. The larger the value set for this parameter the more likely you are to suffer the consequences of numerical issues, and trickle flow (which you can attempt to mitigate by setting IntegralityFocus=1 - this will slow down the solve though).
- Riley
0
Please sign in to leave a comment.
Comments
3 comments