Obtain a feasible solution but there are constraints that are not met.
Answered
I am a beginner in Gurobi
In a model that I created, I have a variable called ycity.
ycity={}
for temperature in temperature_type:
for city in cities:
for period in periods:
for period2 in periods:
ycity[temperature,city,period,period2]=vsc.addVar(vtype=gp.GRB.BINARY, name="ycity")
and I have two constraints that are related to ycity variable :
for temperature in temperature_type:
for city in cities:
for period in periods:
for period2 in periods:
vsc.addConstr(ycity[temperature,city,period,period2] * big_M + (period2 - deliverytime_city[city,period,temperature]) >= 0, name="Constraint 1")
vsc.addConstr(((1-ycity[temperature,city,period,period2]) * big_M) - (period2 - deliverytime_city[city,period,temperature]) >= 1, name="Constraint 2")
Its found feasible solution:
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 59125 rows, 35588 columns and 133873 nonzeros
Model fingerprint: 0xfe4a32d2
Variable types: 0 continuous, 35588 integer (19995 binary)
Coefficient statistics:
Matrix range [4e-02, 1e+20]
Objective range [1e+00, 3e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+20]
Warning: Model contains large matrix coefficient range
Warning: Model contains large rhs
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 54148 rows and 30570 columns
Presolve time: 0.10s
Presolved: 4977 rows, 5018 columns, 16049 nonzeros
Variable types: 0 continuous, 5018 integer (1334 binary)
Root relaxation: objective 8.256182e+04, 1277 iterations, 0.03 seconds (0.03 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 82561.8194 0 255 - 82561.8194 - - 0s
0 0 83177.3744 0 475 - 83177.3744 - - 0s
0 0 83499.5000 0 471 - 83499.5000 - - 0s
0 0 83562.0000 0 479 - 83562.0000 - - 0s
0 0 83562.0000 0 474 - 83562.0000 - - 0s
0 0 83562.0000 0 504 - 83562.0000 - - 0s
0 0 83562.0000 0 511 - 83562.0000 - - 0s
0 0 83562.0000 0 512 - 83562.0000 - - 0s
0 0 83562.0000 0 553 - 83562.0000 - - 0s
0 0 83562.0000 0 570 - 83562.0000 - - 0s
0 0 83562.0000 0 611 - 83562.0000 - - 0s
0 0 83562.0000 0 335 - 83562.0000 - - 0s
0 2 83562.0000 0 302 - 83562.0000 - - 1s
* 1418 690 181 86010.000000 83594.5000 2.81% 23.4 1s
H 1527 440 85610.000000 83594.5000 2.35% 22.4 2s
H 1547 421 85490.000000 83594.5000 2.22% 22.6 2s
H 1578 382 85470.000000 83690.5000 2.08% 24.0 3s
H 1578 363 85310.000000 83715.7985 1.87% 24.0 3s
H 1578 345 85270.000000 83715.7985 1.82% 24.0 3s
1584 349 84969.7415 30 453 85270.0000 83767.8782 1.76% 23.9 5s
H 1584 331 85240.000000 83767.8782 1.73% 23.9 5s
3340 1107 84783.9160 30 497 85240.0000 83767.8782 1.73% 43.0 10s
H 4068 1300 85070.000000 83767.8782 1.53% 42.3 11s
6866 2407 83767.8782 27 766 85070.0000 83767.8782 1.53% 40.3 15s
10701 3859 84097.7244 28 578 85070.0000 83767.8782 1.53% 41.0 20s
15690 5226 84882.2338 32 511 85070.0000 83767.8782 1.53% 41.0 25s
H17730 5585 85060.000000 83781.1767 1.50% 42.1 27s
18945 6042 84635.0000 28 700 85060.0000 83808.9255 1.47% 42.1 30s
24191 7002 83943.4950 23 762 85060.0000 83906.3151 1.36% 42.4 35s
29146 7667 cutoff 43 85060.0000 83985.4550 1.26% 42.4 40s
34365 8221 84768.0473 34 560 85060.0000 84074.0243 1.16% 42.6 46s
38591 8791 84756.3430 26 822 85060.0000 84156.3757 1.06% 42.6 51s
42431 9076 84452.0244 33 335 85060.0000 84209.7960 1.00% 42.1 61s
42445 9085 85000.0000 52 872 85060.0000 84209.7960 1.00% 42.1 65s
42464 9098 85048.6237 40 890 85060.0000 84209.7960 1.00% 42.1 70s
42480 9109 84459.4462 29 934 85060.0000 84209.7960 1.00% 42.1 75s
42495 9119 84782.4713 33 872 85060.0000 84222.7155 0.98% 42.1 80s
43100 9294 85032.6074 51 469 85060.0000 84222.7155 0.98% 43.6 85s
45584 9426 84346.8677 35 782 85060.0000 84222.7155 0.98% 43.7 90s
49436 9196 84515.0937 49 636 85060.0000 84308.4934 0.88% 43.5 95s
52840 8929 cutoff 52 85060.0000 84411.6446 0.76% 43.2 100s
57350 8647 84937.8704 44 661 85060.0000 84531.9640 0.62% 42.2 105s
61966 7547 cutoff 44 85060.0000 84636.5642 0.50% 41.3 110s
66034 6198 cutoff 45 85060.0000 84760.6973 0.35% 40.8 115s
70613 4661 cutoff 43 85060.0000 84846.3902 0.25% 40.5 121s
75424 4851 85040.1316 49 529 85060.0000 84942.0000 0.14% 39.2 127s
77833 5317 84998.5877 54 377 85060.0000 84955.6278 0.12% 38.4 131s
80933 5769 84971.7254 56 387 85060.0000 84958.2831 0.12% 37.4 136s
84527 5967 cutoff 55 85060.0000 84964.8000 0.11% 36.3 140s
86517 6305 cutoff 54 85060.0000 84965.9600 0.11% 35.7 153s
92778 6223 cutoff 50 85060.0000 84967.5106 0.11% 34.2 158s
96140 5832 cutoff 57 85060.0000 84972.9538 0.10% 33.4 162s
99248 5178 84994.5707 55 394 85060.0000 84978.8000 0.10% 32.8 167s
102350 4595 cutoff 49 85060.0000 84982.5000 0.09% 32.2 172s
105622 3922 cutoff 56 85060.0000 84990.0000 0.08% 31.6 177s
108820 3410 cutoff 51 85060.0000 84995.0000 0.08% 31.0 181s
112105 2317 85012.7273 55 356 85060.0000 85000.0000 0.07% 30.4 185s
Cutting planes:
Gomory: 125
Lift-and-project: 7
Implied bound: 25
MIR: 898
StrongCG: 139
Flow cover: 21
Inf proof: 55
Zero half: 37
Mod-K: 5
RLT: 1
Relax-and-lift: 22
Explored 118202 nodes (3484161 simplex iterations) in 189.78 seconds (88.80 work units)
Thread count was 16 (of 16 available processors)
Solution count 9: 85060 85070 85240 ... 86010
Optimal solution found (tolerance 1.00e-04)
Best objective 8.506000000000e+04, best bound 8.506000000000e+04, gap 0.0000%
I have checked that "Constraint 2" is not satisfied
for temperature in temperature_type:
for city in cities:
for period in periods:
for period2 in periods:
print((ycity[temperature,city,period,period2].x* big_M + (period2 - deliverytime_city[city,period,temperature].x) >= 0 ))
print(((1-ycity[temperature,city,period,period2].x)* big_M) - (period2 - deliverytime_city[city,period,temperature].x) >= 1)
and the result appears:
True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False True False
[...]
How did it happen? and what is the solution so that all constraints are met?
Let me know if there is something incorrect with my code.
1
-
Hi Dominico,
It is likely that, if the constraints are being violated at all, it is by a very small margin. Numerical issues are a big topic in computer science, it arises from the simplest problem such as comparing two floating number to more complex calculations done in a mathematical solver.
You may check if that is indeed the case adding an error margin, for example:
for temperature in temperature_type: for city in cities: for period in periods: for period2 in periods: print((ycity[temperature,city,period,period2].x* big_M + (period2 - deliverytime_city[city,period,temperature].x) >= (0 -0.0001) )) print(((1-ycity[temperature,city,period,period2].x)* big_M) - (period2 - deliverytime_city[city,period,temperature].x) >= (1 -0.0001))
If you need more precision, you may want to change the NumericFocus parameter.
There are also two warning that you should look at, which can greatly improve the solver time of your model as well as the precision:
Coefficient statistics: Matrix range [4e-02, 1e+20] Objective range [1e+00, 3e+01] Bounds range [1e+00, 1e+00] RHS range [1e+00, 1e+20] Warning: Model contains large matrix coefficient range Warning: Model contains large rhs Consider reformulating model or setting NumericFocus parameter to avoid numerical issues.
There are 2 warnings regarding big ranges in matrix coefficients and RHS. This can makes your model a lot slower to solve and may lead to greater numerical issues.
It is recommended that you keep your coefficients range small. Your "big M" may be too big (I have a feeling you are using 1e+20). You should try to keep it as small as possible to satisfy your model. This "big M" might vary from constraint to constraint, for example, and be based on the maximum/minimum value the other terms may have.
1
Please sign in to leave a comment.
Comments
1 comment