HiGHS
HiGHS copied to clipboard
ERGO-Code
Model mas76 leads to message [ERROR: Setting model status to Solve error]
For version 1.12 of HiGHS, an for the following input file
time_limit = 300
presolve = on
solver = simplex
parallel = off
for the model mas76 , taken from the MIPLIB library, the following message was received in the output file:
ERROR: MIP solver claims optimality, but with num/max/sum primal(1/1.00001e-06/1.00001e-06) infeasibilities
ERROR: Setting model status to Solve error
What input parameters should I use to obtain the solution to the model mas76?
The following is the complete output file:
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option presolve to "on"
Set option solver to "simplex"
Set option parallel to "off"
Set option time_limit to 300
Set option log_file to "HiGHS.log"
MIP mas76 has 12 rows; 151 cols; 1640 nonzeros; 150 integer variables (150 binary)
Coefficient ranges:
Matrix [1e+00, 1e+04]
Cost [1e-05, 1e+00]
Bound [1e+00, 1e+12]
RHS [2e+01, 2e+05]
WARNING: Problem has some excessively small costs
WARNING: Problem has some excessively large column bounds
WARNING: Consider scaling the bounds by 1e-6, or setting the user_bound_scale option to -20
Presolving model
12 rows, 150 cols, 1639 nonzeros 0s
12 rows, 148 cols, 1615 nonzeros 0s
Presolve reductions: rows 12(-0); columns 148(-3); nonzeros 1615(-25)
Solving MIP model with:
12 rows
148 cols (145 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
1615 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 90710.514236 Large 0 0 0 0 0.0s
R 0 0 0 0.00% 38893.903641 44088.987759 11.78% 0 0 0 70 0.0s
L 0 0 0 0.00% 39030.304486 40005.054141 2.44% 1088 23 18 174 0.2s
53.7% inactive integer columns, restarting
Model after restart has 12 rows, 69 cols (68 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 676 nonzeros
0 0 0 0.00% 39031.930632 40005.054141 2.43% 15 0 0 1533 0.3s
0 0 0 0.00% 39031.930632 40005.054141 2.43% 15 15 4 1560 0.3s
Restarting search from the root node
Model after restart has 12 rows, 68 cols (67 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 664 nonzeros
1358 0 0 0.00% 39059.196002 40005.054141 2.36% 14 0 0 19569 1.3s
1358 0 0 0.00% 39059.196002 40005.054141 2.36% 14 5 2 19579 1.3s
Restarting search from the root node
Model after restart has 12 rows, 66 cols (65 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 640 nonzeros
3156 0 0 0.00% 39085.543774 40005.054141 2.30% 10 0 0 34702 2.6s
3156 0 0 0.00% 39085.543774 40005.054141 2.30% 10 4 2 34714 2.6s
15789 971 5770 15.12% 39109.828317 40005.054141 2.24% 1569 11 9689 120944 7.6s
29970 1636 12437 24.83% 39198.70587 40005.054141 2.02% 1718 9 9923 215771 12.6s
45839 2290 19971 31.43% 39226.9893 40005.054141 1.94% 1204 15 9781 318934 17.8s
60826 2810 27116 36.36% 39252.960148 40005.054141 1.88% 1163 19 9800 417225 22.8s
77432 3339 35063 41.66% 39286.765604 40005.054141 1.80% 1335 15 9963 521996 27.8s
91752 3744 41932 46.85% 39307.070225 40005.054141 1.74% 1271 6 9945 617903 33.0s
105448 4105 48519 49.68% 39318.200148 40005.054141 1.72% 1069 13 9912 709776 38.0s
119797 4432 55460 52.66% 39326.585998 40005.054141 1.70% 1148 15 10000 804387 43.0s
132752 4721 61716 60.05% 39340.93637 40005.054141 1.66% 1094 13 9907 891330 48.0s
145943 4952 68122 64.60% 39353.318877 40005.054141 1.63% 1253 10 9637 979368 53.0s
158776 5212 74325 67.56% 39360.856445 40005.054141 1.61% 1203 9 9785 1065k 58.0s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
172320 5455 80889 70.75% 39370.922183 40005.054141 1.59% 1167 19 9787 1157k 63.0s
186481 5714 87753 72.84% 39380.443482 40005.054141 1.56% 1185 7 9975 1251k 68.0s
199448 5894 94049 75.42% 39395.334452 40005.054141 1.52% 1167 7 9842 1338k 73.0s
212068 6054 100195 77.02% 39405.713262 40005.054141 1.50% 1204 12 9833 1424k 78.0s
225635 6067 106897 82.27% 39424.949246 40005.054141 1.45% 1187 12 9982 1514k 83.0s
240014 6145 113960 84.46% 39442.413798 40005.054141 1.41% 1098 20 9999 1609k 88.0s
252190 6104 119977 86.43% 39458.1665 40005.054141 1.37% 1105 16 9839 1693k 93.0s
265929 6002 126793 88.42% 39479.499141 40005.054141 1.31% 1291 8 9935 1784k 98.0s
277795 5901 132691 90.22% 39497.280005 40005.054141 1.27% 1264 12 9984 1867k 103.0s
289226 5635 138468 92.07% 39525.356938 40005.054141 1.20% 1185 15 9826 1948k 108.0s
298915 5228 143455 94.60% 39552.833956 40005.054141 1.13% 1271 10 9035 2022k 113.0s
309274 4609 148885 96.08% 39595.691881 40005.054141 1.02% 1287 9 5939 2099k 118.0s
316206 3999 152606 96.83% 39632.439401 40005.054141 0.93% 1316 14 4865 2160k 123.0s
323970 2944 156950 98.39% 39693.530016 40005.054141 0.78% 1279 12 3532 2227k 128.0s
330142 1134 160891 99.54% 39803.389563 40005.054141 0.50% 1195 7 1495 2292k 133.0s
331932 0 162341 100.00% 40001.055374 40005.054141 0.01% 1154 9 1272 2314k 134.5s
Solving report
Model mas76
Status Optimal
Primal bound 40005.054141
Dual bound 40001.055374
Gap 0.01% (tolerance: 0.01%)
P-D integral 2.05954656066
Solution status feasible
40005.054141 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 134.50
Max sub-MIP depth 5
Nodes 331932
Repair LPs 0
LP iterations 2314385
8608 (strong br.)
142338 (separation)
116113 (heuristics)
ERROR: MIP solver claims optimality, but with num/max/sum primal(1/1.00001e-06/1.00001e-06) infeasibilities
ERROR: Setting model status to Solve error
Model name : mas76
Model status : Solve error
HiGHS run time : 134.50
Interesting, this is very close to being feasible, since the default MIP feasibility tolerance is 1e-6. I'll look at how the post-optimality feasibility check is computed. I wouldn't change any options to try to avoid this. Also, there's no point in setting presolve=on (as it's run by default) parallel=on (as it's off by default) or solver=simplex (as it's chosen by default).
@fwesselm Did you say that there was a problem solving mas76 in your benchmarking?
This infeasibility is with respect to a bound of 157345, so the violation (1e-11) of the feasibility tolerance is 1e17 less than the bound - so the violation is less than double precision rounding. Hence using a different expression to compute the infeasibility (in the MIP solver and in the checking) can be the cause.
Although it's in Miplib 2017, it's a badly scaled MIP
@fwesselm Did you say that there was a problem solving mas76 in your benchmarking?
No, as far as I remember, there was no issue with mas76. I can double-check.
Also, there's no point in setting presolve=on (as it's run by default)
According to the HiGHS documentation, for parameter presolve, the parameter parallel and the parameter solver there is Default: "choose". This is why I set
presolve = on
solver = simplex
parallel = off
In that context, what is the meaning of Default: "choose"?
"choose" allows us to change the behaviour when, for example, we introduce a mechanism to decide which form of LP solver to use based on model properties. However, at present simplex will always be chosen.
I was sloppy in using the word "default", sorry
WARNING: Problem has some excessively small costs WARNING: Problem has some excessively large column bounds WARNING: Consider scaling the bounds by 1e-6, or setting the user_bound_scale option to -20
Based on the warning from the previous run, the user_bound_scale parameter was set to -20.
The full output report is shown below:
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option parallel to "off"
Set option time_limit to 300
Set option user_bound_scale to -20
Set option log_file to "HiGHS.log"
MIP mas76 has 12 rows; 151 cols; 1640 nonzeros; 150 integer variables (150 binary)
Assessing costs and bounds after applying user_bound_scale option value of -20
Coefficient ranges:
Matrix [1e-06, 1e+00]
Cost [1e-11, 1e+00]
Bound [1e+00, 1e+06]
RHS [1e-05, 2e-01]
WARNING: User-scaled problem has some excessively small costs
WARNING: User-scaled problem has some excessively small row bounds
Presolving model
12 rows, 150 cols, 1639 nonzeros 0s
12 rows, 148 cols, 1615 nonzeros 0s
Presolve reductions: rows 12(-0); columns 148(-3); nonzeros 1615(-25)
Solving MIP model with:
12 rows
148 cols (145 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
1615 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 0.074658816 Large 0 0 0 0 0.0s
R 0 0 0 0.00% 0.037092117 0.0420465353 11.78% 0 0 0 41 0.0s
L 0 0 0 0.00% 0.0372177601 0.0381517927 2.45% 212 24 6 141 0.1s
53.7% inactive integer columns, restarting
Model after restart has 12 rows, 69 cols (68 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 676 nonzeros
0 0 0 0.00% 0.037218511 0.0381517927 2.45% 14 0 0 893 0.2s
0 0 0 0.00% 0.037218511 0.0381517927 2.45% 14 14 4 916 0.2s
L 0 0 0 0.00% 0.0372231912 0.0381517927 2.43% 27 25 4 946 0.3s
L 176 30 72 1.56% 0.0372258365 0.0381517927 2.43% 134 23 1394 7663 0.8s
Restarting search from the root node
Model after restart has 12 rows, 66 cols (65 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 640 nonzeros
1754 0 0 0.00% 0.0372483569 0.0381517927 2.37% 20 0 0 24417 1.8s
1754 0 0 0.00% 0.0372483569 0.0381517927 2.37% 20 3 2 24425 1.8s
L 1754 0 0 0.00% 0.0372517482 0.0381509225 2.36% 95 30 2 24648 1.9s
Restarting search from the root node
Model after restart has 12 rows, 66 cols (65 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 640 nonzeros
3523 0 0 0.00% 0.0372517482 0.0381509225 2.36% 16 0 0 44462 3.3s
3523 0 0 0.00% 0.0372517482 0.0381509225 2.36% 16 3 2 44469 3.3s
L 3523 0 0 0.00% 0.0372517482 0.0381509225 2.36% 96 34 2 44687 3.6s
12868 617 4295 38.87% 0.0374328942 0.0381509225 1.88% 626 25 9869 142135 8.6s
23331 1011 9275 55.91% 0.0374849932 0.0381509225 1.75% 702 27 9507 244532 13.6s
L 27496 1146 11264 59.86% 0.0375186592 0.0381509225 1.66% 834 17 9933 285508 16.0s
HighsMipSolverData::transformNewIntegerFeasibleSolution tmpSolver.run();
34742 1335 14742 69.60% 0.0375726713 0.0381509225 1.52% 804 33 9972 367162 21.0s
41994 1416 18282 76.52% 0.0376145289 0.0381509225 1.41% 709 30 9970 447643 26.0s
49742 1422 22087 82.00% 0.0376667176 0.0381509225 1.27% 935 12 9971 527706 31.0s
57891 1209 26207 93.42% 0.0377593518 0.0381509225 1.03% 863 22 9877 610871 36.0s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
65223 598 30116 98.29% 0.0378813673 0.0381509225 0.71% 920 10 4451 684388 41.0s
67980 0 31779 100.00% 0.0381471097 0.0381509225 0.01% 1145 11 1861 716351 43.4s
Solving report
Model mas76
Status Optimal
Primal bound 0.0381509224892
Dual bound 0.038147109715
Gap 0.00999% (tolerance: 0.01%)
P-D integral 0.668114738835
Solution status feasible
0.0381509224892 (objective)
0 (bound viol.)
4.8827608623e-13 (int. viol.)
0 (row viol.)
Timing 43.44
Max sub-MIP depth 4
Nodes 67980
Repair LPs 1 (1 feasible; 0 iterations)
LP iterations 716351
6864 (strong br.)
93255 (separation)
36417 (heuristics)
WARNING: Solution optimality conditions: After removing user scaling
max 4.88e-13 integrality violations (tolerance = 1e-06)
num/max 1 / 0.912 (relative 1 / 5.8e-06) primal infeasibilities (tolerance = 1e-06)
After solving the user-scaled model, the unscaled solution has objective value 40004.1417
WARNING: User scaled problem solved to optimality, but unscaled solution does not satisfy feasibilty and optimality tolerances
That's interesting to see. It looks as if a stray printf has been left in. I'll fix that
The primal infeasibility after removing the user scaling is to be expected. Indeed, I'm surprised that there aren't more.
Setting the parameter mip_rel_gap = 0 the output of the HiGHS is the following
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option parallel to "off"
Set option time_limit to 300
Set option user_bound_scale to -20
Set option log_file to "HiGHS.log"
Set option mip_rel_gap to 0
MIP mas76 has 12 rows; 151 cols; 1640 nonzeros; 150 integer variables (150 binary)
Assessing costs and bounds after applying user_bound_scale option value of -20
Coefficient ranges:
Matrix [1e-06, 1e+00]
Cost [1e-11, 1e+00]
Bound [1e+00, 1e+06]
RHS [1e-05, 2e-01]
WARNING: User-scaled problem has some excessively small costs
WARNING: User-scaled problem has some excessively small row bounds
Presolving model
12 rows, 150 cols, 1639 nonzeros 0s
12 rows, 148 cols, 1615 nonzeros 0s
Presolve reductions: rows 12(-0); columns 148(-3); nonzeros 1615(-25)
Solving MIP model with:
12 rows
148 cols (145 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
1615 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 0.074658816 Large 0 0 0 0 0.0s
R 0 0 0 0.00% 0.037092117 0.0420465353 11.78% 0 0 0 41 0.0s
L 0 0 0 0.00% 0.0372177601 0.0381517927 2.45% 212 24 6 141 0.1s
53.7% inactive integer columns, restarting
Model after restart has 12 rows, 69 cols (68 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 676 nonzeros
0 0 0 0.00% 0.037218511 0.0381517927 2.45% 14 0 0 893 0.2s
0 0 0 0.00% 0.037218511 0.0381517927 2.45% 14 14 4 916 0.2s
L 0 0 0 0.00% 0.0372231912 0.0381517927 2.43% 27 25 4 946 0.3s
Restarting search from the root node
Model after restart has 12 rows, 65 cols (64 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 628 nonzeros
1011 0 0 0.00% 0.0372258365 0.0381517927 2.43% 28 0 0 17917 1.2s
1011 0 0 0.00% 0.0372258365 0.0381517927 2.43% 28 5 2 17933 1.2s
L 1011 0 0 0.00% 0.037255748 0.0381517927 2.35% 99 32 2 18143 1.4s
L 6234 453 2373 12.31% 0.037255748 0.0381509225 2.35% 529 38 9687 64613 3.8s
17749 1054 7813 31.22% 0.0374055339 0.0381509225 1.95% 687 31 9723 171238 8.8s
27933 1389 12729 41.18% 0.0374499314 0.0381509225 1.84% 704 20 9865 273487 13.8s
L 29926 1456 13690 42.09% 0.0374587456 0.0381509225 1.81% 534 23 9653 293398 15.0s
38364 1801 17728 48.29% 0.0374891332 0.0381509225 1.73% 581 30 9719 379582 20.0s
L 42212 1912 19596 50.99% 0.0375044307 0.0381509225 1.69% 533 34 9671 418513 22.1s
50251 2164 23481 54.83% 0.0375188451 0.0381509225 1.66% 837 20 9909 501585 27.1s
58319 2391 27398 58.80% 0.037542246 0.0381509225 1.60% 527 35 9591 584336 32.5s
66355 2548 31333 63.38% 0.0375609344 0.0381509225 1.55% 596 30 9852 670903 37.5s
L 73912 2748 35003 67.25% 0.0375694207 0.0381509225 1.52% 718 14 9797 749275 42.6s
81783 2849 38881 70.46% 0.0375821443 0.0381509225 1.49% 647 31 9841 836969 47.7s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
88803 2975 42324 73.09% 0.037593404 0.0381509225 1.46% 645 18 9991 915973 52.7s
96116 3043 45943 76.80% 0.0376064558 0.0381509225 1.43% 709 28 9923 994945 57.7s
104180 3173 49903 79.79% 0.0376188783 0.0381509225 1.39% 657 26 9770 1078k 62.7s
111775 3249 53658 82.22% 0.0376351594 0.0381509225 1.35% 552 32 9868 1162k 67.8s
121536 3307 58494 84.77% 0.0376481428 0.0381509225 1.32% 584 33 9941 1253k 73.0s
129865 3337 62636 87.57% 0.0376656614 0.0381509225 1.27% 723 17 9868 1336k 78.0s
137093 3287 66269 90.03% 0.0376797008 0.0381509225 1.24% 766 21 9910 1416k 83.0s
144673 3229 70080 91.40% 0.0377009537 0.0381509225 1.18% 671 27 9750 1497k 88.0s
152900 3107 74238 93.00% 0.0377243108 0.0381509225 1.12% 605 42 9934 1578k 93.0s
160322 2924 78032 94.25% 0.0377466444 0.0381509225 1.06% 912 18 9678 1655k 98.0s
168206 2703 82077 95.81% 0.0377744944 0.0381509225 0.99% 670 23 9668 1733k 103.0s
174597 2314 85461 96.88% 0.0378060261 0.0381509225 0.90% 817 19 7817 1806k 108.0s
181853 1849 89310 98.13% 0.0378445484 0.0381509225 0.80% 883 23 8350 1881k 113.0s
186722 1017 92162 99.07% 0.0379317639 0.0381509225 0.57% 859 24 2816 1944k 118.0s
188405 0 93514 100.00% 0.0381509225 0.0381509225 0.00% 881 21 972 1974k 120.7s
Solving report
Model mas76
Status Optimal
Primal bound 0.0381509224892
Dual bound 0.0381509224892
Gap 0%
P-D integral 1.69234805115
Solution status feasible
0.0381509224892 (objective)
0 (bound viol.)
5.62883073485e-13 (int. viol.)
0 (row viol.)
Timing 120.71
Max sub-MIP depth 4
Nodes 188405
Repair LPs 0
LP iterations 1974177
6994 (strong br.)
222651 (separation)
99004 (heuristics)
WARNING: Solution optimality conditions: After removing user scaling
max 5.63e-13 integrality violations (tolerance = 1e-06)
num/max 1 / 0.912 (relative 1 / 5.8e-06) primal infeasibilities (tolerance = 1e-06)
After solving the user-scaled model, the unscaled solution has objective value 40004.1417
WARNING: User scaled problem solved to optimality, but unscaled solution does not satisfy feasibilty and optimality tolerances
The value listed in miplib for mas76 is 40005.05398999999 but the value listed in HiGHS is 40004.1417.
What are your thoughts on this discrepancy?
This will be a consequence of scaling the bounds down by 2^20~10^6 and the resultant primal infeasibility.
Specifically, if you scale the bounds down by 10^6 and solve to the MIP feasibility tolerance of 10^-6, then infeasibilities of this value will be scaled up by 10^6 when the user scaling is removed.
What happens if you set user_bound_scale=-10?
Setting the parameter user_bound_scale = -10 the output is the following:
Running HiGHS 1.12.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option parallel to "off"
Set option time_limit to 300
Set option user_bound_scale to -10
Set option log_file to "HiGHS.log"
Set option mip_rel_gap to 0
MIP mas76 has 12 rows; 151 cols; 1640 nonzeros; 150 integer variables (150 binary)
Assessing costs and bounds after applying user_bound_scale option value of -10
Coefficient ranges:
Matrix [1e-03, 1e+01]
Cost [1e-08, 1e+00]
Bound [1e+00, 1e+09]
RHS [1e-02, 2e+02]
WARNING: User-scaled problem has some excessively small costs
WARNING: User-scaled problem has some excessively large column bounds
WARNING: Consider setting the user_bound_scale option to -20
Presolving model
12 rows, 150 cols, 1639 nonzeros 0s
12 rows, 148 cols, 1615 nonzeros 0s
Presolve reductions: rows 12(-0); columns 148(-3); nonzeros 1615(-25)
Solving MIP model with:
12 rows
148 cols (145 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
1615 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 83.28624987 Large 0 0 0 0 0.0s
R 0 0 0 0.00% 37.98232777 43.05565211 11.78% 0 0 0 42 0.0s
L 0 0 0 0.00% 38.11553172 39.06743569 2.44% 1090 23 17 146 0.2s
53.7% inactive integer columns, restarting
Model after restart has 12 rows, 69 cols (68 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 676 nonzeros
0 0 0 0.00% 38.11711976 39.06743569 2.43% 15 0 0 1406 0.4s
0 0 0 0.00% 38.11711976 39.06743569 2.43% 15 15 4 1437 0.4s
L 0 0 0 0.00% 38.13637105 39.06743569 2.38% 1015 31 4 1556 0.6s
L 0 0 0 0.00% 38.13637105 39.06743569 2.38% 1015 31 4 2125 0.7s
Restarting search from the root node
Model after restart has 12 rows, 67 cols (66 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 652 nonzeros
1547 0 0 0.00% 38.14065018 39.06743569 2.37% 8 0 0 18366 1.6s
1547 0 0 0.00% 38.14065018 39.06743569 2.37% 8 3 4 18370 1.6s
Restarting search from the root node
Model after restart has 12 rows, 67 cols (66 bin., 0 int., 0 impl., 1 cont., 0 dom.fix.), and 652 nonzeros
4774 0 0 0.00% 38.17093927 39.06743569 2.29% 15 0 0 43046 3.9s
4774 0 0 0.00% 38.17093927 39.06743569 2.29% 15 4 4 43060 3.9s
L 4774 0 0 0.00% 38.17272155 39.0674347 2.29% 2141 34 4 43540 4.4s
16000 759 5209 13.28% 38.24129309 39.0674347 2.11% 1804 16 9839 115973 9.4s
28953 1409 11325 21.71% 38.27448921 39.0674347 2.03% 1536 13 9512 192810 14.4s
41979 1979 17528 27.66% 38.3053785 39.0674347 1.95% 1412 12 9959 271783 19.4s
54249 2444 23403 35.47% 38.31555441 39.0674347 1.92% 1455 18 9540 346368 24.4s
65848 2830 28983 40.65% 38.33996037 39.0674347 1.86% 1499 10 9688 419529 29.7s
77077 3198 34383 45.22% 38.35239566 39.0674347 1.83% 1527 10 9972 489929 34.7s
89044 3546 40169 47.91% 38.36107091 39.0674347 1.81% 1491 10 9930 560327 39.7s
99522 3830 45240 50.80% 38.3692051 39.0674347 1.79% 1465 11 9918 628333 44.7s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
111228 4074 50936 54.14% 38.3808241 39.0674347 1.76% 1478 9 9809 700211 49.7s
124423 4419 57331 57.96% 38.39297982 39.0674347 1.73% 1587 19 9810 778164 54.7s
135896 4715 62897 61.67% 38.3983265 39.0674347 1.71% 1511 13 9777 848141 59.7s
147144 4946 68383 64.32% 38.41064344 39.0674347 1.68% 1398 11 9570 917900 64.7s
159181 5252 74223 67.10% 38.42199139 39.0674347 1.65% 1446 13 9746 990957 69.7s
172355 5551 80622 70.26% 38.4300845 39.0674347 1.63% 1408 9 9943 1066k 74.7s
183906 5760 86266 72.47% 38.44003948 39.0674347 1.61% 1406 8 9996 1136k 79.7s
195364 5913 91894 74.41% 38.44961859 39.0674347 1.58% 1695 9 9927 1205k 84.7s
207137 6060 97681 76.73% 38.45903886 39.0674347 1.56% 1518 16 9943 1274k 89.7s
217961 6157 103023 78.41% 38.46986402 39.0674347 1.53% 1540 18 9795 1343k 95.1s
230158 6248 109049 80.07% 38.47947138 39.0674347 1.50% 1637 9 9905 1415k 100.2s
242532 6351 115156 82.76% 38.48920435 39.0674347 1.48% 1881 7 9936 1488k 105.2s
253762 6419 120714 84.81% 38.49844113 39.0674347 1.46% 1455 9 9578 1557k 110.2s
264125 6450 125863 85.64% 38.50901385 39.0674347 1.43% 1572 10 9847 1621k 115.2s
276069 6407 131834 87.45% 38.52051206 39.0674347 1.40% 1503 13 9839 1690k 120.2s
287961 6361 137776 89.16% 38.53313388 39.0674347 1.37% 1388 9 9951 1760k 125.2s
298935 6340 143250 90.65% 38.54446191 39.0674347 1.34% 1274 9 9938 1826k 130.2s
310501 6238 149056 92.09% 38.56683671 39.0674347 1.28% 1377 9 9974 1895k 135.2s
321005 6042 154381 93.69% 38.58919754 39.0674347 1.22% 1447 6 9975 1960k 140.2s
330564 5731 159299 94.82% 38.61212136 39.0674347 1.17% 1178 14 9805 2021k 145.2s
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
339401 5378 163881 95.86% 38.63689152 39.0674347 1.10% 1403 12 9661 2080k 150.2s
347301 4876 168067 96.95% 38.67677936 39.0674347 1.00% 1308 9 8665 2135k 155.2s
353524 4159 171523 97.83% 38.73137275 39.0674347 0.86% 1372 10 3841 2183k 160.2s
357982 3323 174161 98.39% 38.77689303 39.0674347 0.74% 1330 10 2238 2224k 165.2s
362747 1746 177320 99.24% 38.86525707 39.0674347 0.52% 1198 8 1286 2270k 170.2s
365308 0 179471 100.00% 39.0674347 39.0674347 0.00% 1177 10 1079 2298k 172.9s
Solving report
Model mas76
Status Optimal
Primal bound 39.0674346953
Dual bound 39.0674346953
Gap 0%
P-D integral 2.67477351448
Solution status feasible
39.0674346953 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 172.92
Max sub-MIP depth 5
Nodes 365308
Repair LPs 0
LP iterations 2298658
7830 (strong br.)
123887 (separation)
115058 (heuristics)
WARNING: Solution optimality conditions: After removing user scaling
max 0 integrality violations (tolerance = 1e-06)
num/max 1 / 0.00101 (relative 0 / 6.44e-09) primal infeasibilities (tolerance = 1e-06)
After solving the user-scaled model, the unscaled solution has objective value 40005.053128
WARNING: User scaled problem solved to optimality, but unscaled solution does not satisfy feasibilty and optimality tolerances
The return value by HiGHS is 40005.053128.
Great!
Thank you for your help!
I have noticed that setting the value of parameter mip_rel_gap = 0 and the value of parameter mip_abs_gap = 1e-06, for both set user_bound_scale=-10 and set user_bound_scale=-20, the value of the column BestBound is equal to the value of the column BestSol at the last iteration of the branch-and-bound algorithm.
Will you be making any improvements to this issue in future versions of HiGHS?
That's interesting to see. It looks as if a stray printf has been left in. I'll fix that
That was fixed in 869cbd4
@jajhall In the context of issue #2664, should I close this issue? What is your suggestion?
I don't want to close this yet. The issue may be related to #2664, but I'm not in a position to work on the underlying cause for a couple of weeks - I'm on holiday - so I'd like to keep the issue open as an aide memoire.
For the sake of completeness, the table below lists the objective value for various values of the HiGHS option user_bound_scale.
- The column HiGHS Log contains links to the obtained log files.
- The WARNING in column Objective value means:
User scaled problem solved to optimality, but unscaled solution does not satisfy feasibilty and optimality tolerances
| user_bound_scale | Objective value | Nodes | LP iterations | HiGHS Log |
|---|---|---|---|---|
| 0 | ERROR | 194 521 | 1 395 755 | mas76-00 |
| -1 | 40005.0541418 | 283 613 | 1 935 798 | mas76-01 |
| -2 | 40005.0541419 | 296 391 | 1 983 017 | mas76-02 |
| -3 | 40005.0541419 | 290 440 | 1 993 584 | mas76-03 |
| -4 | WARNING 40005.05413 | 284 989 | 1 934 414 | mas76-04 |
| -5 | WARNING 40005.054118 | 389 087 | 2 545 152 | mas76-05 |
| -6 | WARNING 40005.054098 | 382 561 | 2 504 295 | mas76-06 |
| -7 | WARNING 40005.0541418 | 287 513 | 1 896 358 | mas76-07 |
| -8 | WARNING 40005.053896 | 303 466 | 2 006 597 | mas76-08 |
| -9 | WARNING 40005.05364 | 244 638 | 1 580 568 | mas76-09 |
| -10 | WARNING 40005.053128 | 365 308 | 2 298 658 | mas76-10 |
| -11 | WARNING 40005.052104 | 268 928 | 1 691 837 | mas76-11 |
| -12 | WARNING 40005.050056 | 299 522 | 1 816 193 | mas76-12 |
| -13 | WARNING 40005.04596 | 344 329 | 2 116 603 | mas76-13 |
| -14 | WARNING 40005.0541408 | 375 350 | 2 189 283 | mas76-14 |
| -15 | WARNING 40005.0213939 | 178 982 | 1 123 183 | mas76-15 |
| -16 | WARNING 40005.0464574 | 315 104 | 1 889 305 | mas76-16 |
| -17 | WARNING 40004.9230899 | 226 976 | 1 589 873 | mas76-17 |
| -18 | WARNING 40004.792018 | 146 752 | 1 030 681 | mas76-18 |
| -19 | WARNING 40004.529874 | 176 033 | 1 789 113 | mas76-19 |
| -20 | WARNING 40004.1417 | 188 405 | 1 974 177 | mas76-20 |
The table below lists the objective value for different random_seed values of the HiGHS option in the range of 0 to 20.
Out of 21 cases, the error was only returned for the value random_seed = 0. The other 20 cases returned the value 40005.0541, which agrees with the value provided in the MIPLIB, i.e. 40005.05398999999, see mas76.
| random_seed | Objective value | Nodes | LP iterations | HiGHS Log |
|---|---|---|---|---|
| 0 | ERROR | 194 521 | 1 395 755 | mas76-00 |
| 1 | 40005.0541419 | 345 893 | 2 266 984 | mas76-01 |
| 2 | 40005.054142 | 123 008 | 898 124 | mas76-02 |
| 3 | 40005.054142 | 226 242 | 1 562 534 | mas76-03 |
| 4 | 40005.0541409 | 304 931 | 2 060 513 | mas76-04 |
| 5 | 40005.054142 | 313 632 | 2 137 971 | mas76-05 |
| 6 | 40005.0541419 | 290 945 | 1 966 123 | mas76-06 |
| 7 | 40005.0541384 | 279 086 | 1 870 579 | mas76-07 |
| 8 | 40005.054142 | 188 621 | 1 314 101 | mas76-08 |
| 9 | 40005.0541419 | 219 148 | 1 560 975 | mas76-09 |
| 10 | 40005.054142 | 281 712 | 1 947 222 | mas76-10 |
| 11 | 40005.054142 | 351 740 | 2 346 257 | mas76-11 |
| 12 | 40005.054142 | 120 722 | 851 772 | mas76-12 |
| 13 | 40005.0541419 | 504 939 | 3 285 525 | mas76-13 |
| 14 | 40005.0541419 | 231 953 | 1 566 294 | mas76-14 |
| 15 | 40005.054141 | 258 779 | 1 757 498 | mas76-15 |
| 16 | 40005.0541011 | 342 142 | 2 329 526 | mas76-16 |
| 17 | 40005.0541419 | 133 073 | 951 248 | mas76-17 |
| 18 | 40005.0541417 | 238 920 | 1 622 901 | mas76-18 |
| 19 | 40005.0541419 | 257 187 | 1 788 130 | mas76-19 |
| 20 | 40005.0541419 | 452 916 | 3 034 108 | mas76-20 |