Hi, I am currently working on a cost minimization model. However, I have the problem when solving with Gurobi (v10) that my best bounds is stuck at 0.0 all the time. As a result, my gap remains constant at 100%. Additionally, due to my constraints, 0.0 is not even a possible solution value at all. Do you have any ideas what I could adjust e.g. in the Gurobi settings?
Can you post the full log file, and a reproducible example if possible?
I increased th solving time and the best bound increased. But it still takes very long to find a low gap:
Model has 61560 quadratic constraints
Variable types: 30780 continuous, 31366 integer (30888 binary)
Coefficient statistics:
Matrix range [4e-02, 2e+03]
QMatrix range [1e+00, 2e+02]
QLMatrix range [1e+00, 2e+00]
Objective range [2e-01, 6e-01]
Bounds range [2e+01, 8e+02]
RHS range [1e+00, 1e+04]
Presolve removed 23198 rows and 45600 columns
Presolve time: 0.18s
Presolved: 61838 rows, 31662 columns, 275538 nonzeros
Variable types: 0 continuous, 31662 integer (8290 binary)
Root relaxation presolve removed 72 rows and 54 columns
Root relaxation presolved: 15363 rows, 8088 columns, 109806 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 2.579441e+04 0.000000e+00 17s
234 0.0000000e+00 0.000000e+00 0.000000e+00 17s
234 0.0000000e+00 0.000000e+00 0.000000e+00 17s
Use crossover to convert LP symmetric solution to basic solution...
Root crossover log...
122 PPushes remaining with PInf 0.0000000e+00 17s
0 PPushes remaining with PInf 0.0000000e+00 17s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 17s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
359 0.0000000e+00 0.000000e+00 0.000000e+00 17s
359 0.0000000e+00 0.000000e+00 0.000000e+00 17s
Root relaxation: objective 0.000000e+00, 359 iterations, 0.23 seconds (0.26 work units)
Total elapsed time = 17.03s (DegenMoves)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 80 - 0.00000 - - 17s
H 0 0 2282.2641111 0.00000 100% - 18s
H 0 0 1807.8457222 0.00000 100% - 18s
H 0 0 937.5238889 0.00000 100% - 18s
H 0 0 667.1665000 0.00000 100% - 18s
0 0 0.00000 0 320 667.16650 0.00000 100% - 19s
0 0 0.00000 0 225 667.16650 0.00000 100% - 19s
H 0 0 623.3211111 0.00000 100% - 20s
H 0 0 622.2406667 0.00000 100% - 21s
H 0 0 578.5859444 0.00000 100% - 21s
0 0 0.00000 0 95 578.58594 0.00000 100% - 21s
0 0 0.00000 0 294 578.58594 0.00000 100% - 22s
0 0 0.00000 0 95 578.58594 0.00000 100% - 25s
H 0 0 550.4546667 0.00000 100% - 25s
0 0 0.00000 0 298 550.45467 0.00000 100% - 25s
0 0 0.00000 0 93 550.45467 0.00000 100% - 28s
0 0 0.00000 0 93 550.45467 0.00000 100% - 28s
0 2 0.00000 0 93 550.45467 0.00000 100% - 30s
80 86 0.00000 19 259 550.45467 0.00000 100% 144 35s
177 205 0.00000 38 176 550.45467 0.00000 100% 115 40s
390 471 0.00000 76 165 550.45467 0.00000 100% 73.9 45s
H 584 664 512.0512222 0.00000 100% 60.1 49s
663 957 0.00000 122 162 512.05122 0.00000 100% 56.5 52s
972 975 0.00000 123 162 512.05122 0.00000 100% 45.8 57s
1388 1612 0.00000 195 155 512.05122 0.00000 100% 37.8 61s
1740 1616 307.26728 267 167 512.05122 0.00000 100% 35.6 68s
H 1743 1614 508.5397778 0.00000 100% 35.6 69s
1744 1959 309.77296 268 154 508.53978 0.00000 100% 35.6 71s
2620 2356 0.00000 172 4071 508.53978 0.00000 100% 31.2 76s
H 2621 2239 508.3014444 0.00000 100% 31.1 77s
2622 2239 13.38639 208 79 508.30144 0.00000 100% 31.1 81s
2625 2241 86.78511 3 87 508.30144 0.00000 100% 31.1 91s
2626 2242 360.87639 291 144 508.30144 0.00000 100% 31.1 96s
2627 2243 293.68228 268 102 508.30144 0.00000 100% 31.1 102s
2628 2243 359.94689 229 154 508.30144 0.00000 100% 31.1 106s
2629 2244 64.63600 183 93 508.30144 0.00000 100% 31.1 112s
H 2629 2131 507.6976667 0.00000 100% 31.1 116s
2631 2132 322.49678 245 130 507.69767 0.00000 100% 31.0 121s
2632 2133 161.39933 82 204 507.69767 0.00000 100% 31.0 126s
2633 2134 365.38883 276 118 507.69767 0.00000 100% 31.0 130s
2634 2134 161.39933 144 232 507.69767 0.00000 100% 31.0 135s
2635 2135 150.34067 58 98 507.69767 0.00000 100% 31.0 140s
2637 2136 230.42067 4 114 507.69767 0.00000 100% 31.0 150s
2640 2141 0.00000 10 131 507.69767 0.00000 100% 39.8 155s
2702 2179 175.23697 18 130 507.69767 31.48383 93.8% 44.2 160s
2813 2226 304.80450 31 121 507.69767 31.48383 93.8% 47.4 165s
2975 2294 294.22250 50 153 507.69767 31.48383 93.8% 49.0 170s
3153 2370 143.40517 74 143 507.69767 31.48383 93.8% 50.8 175s
3340 2485 275.01283 94 115 507.69767 31.48383 93.8% 52.7 180s
3568 2616 143.40517 119 159 507.69767 31.48383 93.8% 54.5 185s
3715 2705 204.41850 137 159 507.69767 31.48383 93.8% 56.5 190s
3928 2851 143.40517 160 159 507.69767 31.48383 93.8% 58.5 197s
4033 2947 143.40517 169 168 507.69767 31.48383 93.8% 58.9 200s
4291 3128 237.10989 196 119 507.69767 31.48383 93.8% 59.0 206s
4452 3230 143.40517 215 144 507.69767 31.48383 93.8% 59.0 210s
4848 3572 159.43882 251 126 507.69767 31.48383 93.8% 57.9 219s
5126 3811 269.52410 289 99 507.69767 31.48383 93.8% 58.3 222s
5517 3869 375.38294 333 68 507.69767 31.48383 93.8% 56.6 225s
5969 3954 cutoff 42 507.69767 31.48383 93.8% 57.5 230s
6381 4082 cutoff 82 507.69767 37.21337 92.7% 56.9 235s
6603 4179 143.40517 39 168 507.69767 54.62600 89.2% 57.0 240s
6820 4600 143.40517 91 109 507.69767 54.62600 89.2% 56.9 246s
7594 5017 399.52346 307 61 507.69767 60.35553 88.1% 55.6 253s
8089 4965 143.40517 20 172 507.69767 85.28361 83.2% 54.9 256s
8286 5143 143.40517 60 145 507.69767 85.28361 83.2% 55.1 263s
8505 5179 143.40517 91 145 507.69767 85.28361 83.2% 54.8 266s
8744 5372 143.40517 146 97 507.69767 85.28361 83.2% 53.8 272s
8887 5470 143.40517 179 172 507.69767 85.28361 83.2% 53.4 275s
9208 5893 187.98144 230 126 507.69767 85.28361 83.2% 52.6 283s
9622 7084 365.79400 263 114 507.69767 86.04586 83.1% 51.2 288s
10915 7455 infeasible 231 507.69767 111.92133 78.0% 48.0 296s
11403 7656 143.40517 59 175 507.69767 111.92133 78.0% 48.3 300s
11847 8069 256.39106 130 151 507.69767 111.92133 78.0% 49.0 309s
12152 8242 256.39106 179 90 507.69767 111.92133 78.0% 48.3 314s
12343 8404 496.06223 213 113 507.69767 111.92133 78.0% 48.1 320s
12560 8559 445.76278 20 147 507.69767 111.92133 78.0% 48.6 327s
12797 8808 382.09600 38 148 507.69767 111.92133 78.0% 49.0 334s
13077 10640 143.40517 49 173 507.69767 111.92133 78.0% 48.8 344s
15088 11257 143.40517 81 210 507.69767 111.92133 78.0% 45.6 348s
15772 11286 197.24467 23 216 507.69767 142.57894 71.9% 45.3 352s
15801 11920 197.24467 31 169 507.69767 142.57894 71.9% 45.3 356s
16544 12102 294.58794 25 173 507.69767 143.40517 71.8% 44.5 361s
16730 12295 320.21170 79 153 507.69767 143.40517 71.8% 44.4 366s
16950 12451 361.24978 134 143 507.69767 143.40517 71.8% 44.3 371s
17171 12551 143.40517 26 216 507.69767 143.40517 71.8% 44.6 376s
17334 12697 406.12000 40 90 507.69767 143.40517 71.8% 45.4 381s
17546 12925 283.44983 94 114 507.69767 143.40517 71.8% 45.4 386s
17817 13074 471.11668 151 119 507.69767 143.40517 71.8% 45.3 392s
18004 13303 344.78094 121 135 507.69767 143.40517 71.8% 45.5 398s
18289 13561 304.80450 97 98 507.69767 143.40517 71.8% 45.4 404s
18606 13794 503.44474 187 65 507.69767 143.40517 71.8% 45.2 412s
18930 14028 315.14022 130 104 507.69767 143.40517 71.8% 45.3 418s
19265 14216 237.24494 129 90 507.69767 143.40517 71.8% 45.4 424s
19531 14455 272.67717 63 112 507.69767 143.40517 71.8% 45.5 431s
19820 15709 339.75663 110 152 507.69767 143.40517 71.8% 45.4 440s
21403 16173 413.76256 98 133 507.69767 143.40517 71.8% 45.1 451s
22124 16581 464.06678 100 114 507.69767 143.40517 71.8% 45.8 458s
22627 17019 infeasible 69 507.69767 143.40517 71.8% 45.8 466s
23139 17377 436.41217 45 144 507.69767 143.40517 71.8% 45.6 474s
23564 17666 170.78172 40 148 507.69767 143.40517 71.8% 45.7 483s
23938 18953 240.24689 118 165 507.69767 143.40517 71.8% 46.1 495s
25595 19623 387.02950 123 164 507.69767 143.40517 71.8% 46.4 503s
26444 20099 327.20783 41 180 507.69767 143.40517 71.8% 46.9 510s
27048 20405 303.47140 51 173 507.69767 143.40517 71.8% 47.2 516s
27397 20834 296.04972 72 149 507.69767 143.40517 71.8% 47.7 523s
27971 21133 448.62570 68 138 507.69767 143.40517 71.8% 48.2 530s
28424 21801 421.22239 51 172 507.69767 143.40517 71.8% 48.9 538s
29230 22269 304.80450 76 197 507.69767 143.40517 71.8% 49.1 546s
29878 22537 490.81043 62 180 507.69767 143.40517 71.8% 49.9 553s
30270 22765 337.54356 112 122 507.69767 143.40517 71.8% 50.6 559s
30533 23077 309.47266 65 243 507.69767 143.40517 71.8% 50.7 566s
30934 23461 444.90478 104 99 507.69767 143.40517 71.8% 51.0 574s
31443 23921 295.50950 60 233 507.69767 143.40517 71.8% 51.6 581s
32000 24593 412.22928 36 209 507.69767 143.40517 71.8% 51.9 593s
32805 25071 256.10815 99 109 507.69767 143.40517 71.8% 52.4 600s
Cutting planes:
Learned: 161
Gomory: 193
Lift-and-project: 7
Cover: 2152
Implied bound: 1251
Projected implied bound: 31
Clique: 319
MIR: 1037
Mixing: 2
StrongCG: 565
Flow cover: 1534
GUB cover: 79
Inf proof: 381
Zero half: 98
RLT: 104
Relax-and-lift: 20
BQP: 231
PSD: 10
Explored 33373 nodes (1775253 simplex iterations) in 600.18 seconds (574.98 work units)
Thread count was 4 (of 4 available processors)
Solution count 10: 507.698 508.301 508.54 ... 937.524
Time limit reached
Best objective 5.076976666667e+02, best bound 1.434051666667e+02, gap 71.7538%
User-callback calls 188905, time in user-callback 0.30 sec
And here´s the part of the code, which increases the running time extremely:
@variable(model, start[1:n] >= 0, Int);
@variable(model, end[1:l] >= 0, Int);
@variable(model, a[1:I,1:L,1:W,1:M,1:N], Bin);
@variable(model, max >= y[i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N] >= 0)
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N
@constraint(model, y[i, l, w, m, n] == a[i, l, w, m, n] * (T - ((100 * w - 250) * ((start[n] - end[l])) + T)))
end
@expression(model, cost,
sum(g[i] * c * y[i, l, w, m, n] / b * p
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N));
@objective(model, Min, cost_total = cost);
@odow
Additional question: is it possible to add to the code that z must always be a maximum of 800 without affecting other variables in their value range? The problem is that the min function is not applicable here:
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N
@constraint(model, y[i, l, w, m, n] == min,(800, a[i, l, w, m, n] * (T - ((100 * w - 250) * ((start[n] - end[l])) + T))))
end
Constraints of type MathOptInterface.ScalarNonlinearFunction-in-MathOptInterface.EqualTo{Float64} are not supported by the solver.
Can you provide a fully reproducible example that I can copy-paste? I don’t know what all the problem data are.
One thing to try is:
@variable(model, 0 <= y_tmp[i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N] <= max)
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N
@constraints(model, begin
y_tmp[i, l, w, m, n] == T - ((100 * w - 250) * ((start[n] - end[l])) + T)
y[i, l, w, m, n] == a[i, l, w, m, n] * y_tmp[i, l, w, m, n]
end)
end
or perhaps
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N
# @constraint(
# model,
# y[i, l, w, m, n] == a[i, l, w, m, n] * (T - ((100 * w - 250) * ((start[n] - end[l])) + T))
# )
# a == 1 => y == (100 * w - 250) * (start[n] - end[l])
# a == 0 => y == 0
@constraint(model, y[i, l, w, m, n] <= a[i, l, w, m, n] * max)
@constraint(model, a[i, l, w, m, n] --> {y[i, l, w, m, n] == (100 * w - 250) * (start[n] - end[l])})
end
If they don’t help, it might just be a hard problem. But it’s hard to offer concrete advice without a fully reproducible example. You might want to consider alternate formulations.
For the min, you’ll need to introduce additional binary variables. This link will help, if you swap max for min:
Alternatively, if you always want to maximize y, then you can use:
@odow
Thanks for the response. Here´s an example. there are, of course, even more conditions, but I think that should be enough:
I = 30
L = 12
N = 6
W = 2
M = 2
@variable(model, 72 >= start[1:n] >= 0, Int);
@variable(model, end[1:l] >= 0, Int);
@variable(model, a[1:I,1:L,1:W,1:M,1:N], Bin);
@variable(model, max >= y[i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N] >= 0)
@constraint(model, [i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N], a[i, l, w, m, n] * (start[n] - end[l]) >= 0);
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N
@constraint(model, y[i, l, w, m, n] == a[i, l, w, m, n] * (T - ((100 * w - 250) * ((start[n] - end[l])) + T)))
end
b = 3600
p = 80
c = 0.6
g = Array{Float64}(undef, i)
min = 10
max = 40
for i in 1:I
g[I] = round(rand() * (max- min)+ min, digits =2)
end
@expression(model, cost,
sum(g[i] * c * y[i, l, w, m, n] / b * p
for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N));
@objective(model, Min, cost_total = cost);
In this case, it really depends what the other conditions are.
I had to make a few changes to get your code to run:
using JuMP, Gurobi
I = 30
L = 12
N = 6
W = 2
M = 2
T = 72 # ???
b = 3600
p = 80
c = 0.6
y_min = 10
y_max = 40
g = round.(rand(I) .* (y_max - y_min) .+ y_min; digits = 2)
model = Model(Gurobi.Optimizer)
@variables(model, begin
0 <= x_start[1:N] <= 72, Int
x_end[1:L] >= 0, Int
a[1:I, 1:L, 1:W, 1:M, 1:N], Bin
0 <= y[1:I, 1:L, 1:W, 1:M, 1:N] <= y_max
end)
@constraints(model, begin
[i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N],
a[i, l, w, m, n] * (x_start[n] - x_end[l]) >= 0
[i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N],
y[i, l, w, m, n] == a[i, l, w, m, n] * -(100 * w - 250) * (x_start[n] - x_end[l])
end)
@expression(model, cost,
c / b * p * sum(g[i] * y[i, l, w, m, n] for i in 1:I, l in 1:L, w in 1:W, m in 1:M, n in 1:N),
)
@objective(model, Min, cost)
optimize!(model)
I think that, stepping back, you need to need to reconsider what your mathematical formulation (rather than JuMP or Julia code), but it’s hard to offer advice without the full model.