Hi Paul,
I take your advice and set emphasis on numerical. And the node log is as following.
CPXPARAM_TimeLimit 7200
CPXPARAM_Emphasis_Numerical 1
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_Strategy_KappaStats 2
Aggregator has done 197300 substitutions...
Tried aggregator 11 times.
Aggregator has done 201411 substitutions...
MIP Presolve eliminated 493784 rows and 400087 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128202 coefficients.
Aggregator did 201411 substitutions.
Reduced MIP has 443125 rows, 462047 columns, and 2524342 nonzeros.
Reduced MIP has 22163 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.70 sec. (20468.63 ticks)
Found incumbent of value 7.3414962e+14 after 46.38 sec. (30852.56 ticks)
Probing fixed 0 vars, tightened 83669 bounds.
Probing time = 1.95 sec. (304.46 ticks)
Integer feasible solution rejected --- infeasible on original model
Tried aggregator 3 times.
MIP Presolve eliminated 39549 rows and 22667 columns.
MIP Presolve modified 22364 coefficients.
Aggregator did 86 substitutions.
Reduced MIP has 403490 rows, 439294 columns, and 2413489 nonzeros.
Reduced MIP has 22148 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.39 sec. (2005.39 ticks)
Probing fixed 0 vars, tightened 776 bounds.
Probing time = 1.52 sec. (64.14 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 44.41 sec. (16737.34 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 7.34150e+14 -1.29579e+14 117.65%
0 0 2.63168e+13 134 7.34150e+14 2.63168e+13 116351 96.42%
Integer feasible solution rejected --- infeasible on original model
0 0 2.63168e+13 75 2.72642e+13 Cuts: 864 116710 3.47%
0 0 2.63168e+13 57 2.72642e+13 Cuts: 250 116953 3.47%
0 0 2.63168e+13 58 2.72642e+13 Cuts: 189 117023 3.47%
0 0 2.63168e+13 53 2.72642e+13 Cuts: 118 117085 3.47%
0 0 2.63168e+13 52 2.72642e+13 Cuts: 81 117103 3.47%
Integer feasible solution rejected --- infeasible on original model
Integer feasible solution rejected --- infeasible on original model
Heuristic still looking.
Integer feasible solution rejected --- infeasible on original model
0 2 2.63218e+13 52 2.72642e+13 2.63168e+13 117103 3.47%
Elapsed time = 219.98 sec. (117365.74 ticks, tree = 0.01 MB, solutions = 2)
1 3 2.63218e+13 52 2.72642e+13 2.63218e+13 117105 3.46%
.
.(omit the process since no obvious change)
.
30699 23299 2.63294e+13 0 2.72642e+13 2.63266e+13 11499675 3.44%
30702 23952 2.63282e+13 39 2.72642e+13 2.63266e+13 11582648 3.44%
Elapsed time = 7204.22 sec. (1612787.47 ticks, tree = 2184.44 MB, solutions = 2)
Nodefile size = 124.46 MB (97.96 MB after compression)
Implied bound cuts applied: 3
Flow cuts applied: 158
Mixed integer rounding cuts applied: 204
Gomory fractional cuts applied: 430
Root node processing (before b&c):
Real time = 215.47 sec. (117087.18 ticks)
Parallel b&c, 24 threads:
Real time = 6990.69 sec. (1500206.60 ticks)
Sync time (average) = 1410.03 sec.
Wait time (average) = 2.96 sec.
------------
Total (root+branch&cut) = 7206.16 sec. (1617293.78 ticks)
Solution pool: 3 solutions saved.
MIP - Time limit exceeded, integer feasible: Objective = 2.7264199938e+13
Current MIP best bound = 2.6326587715e+13 (gap = 9.37612e+11, 3.44%)
Solution time = 7206.17 sec. Iterations = 11670847 Nodes = 30704 (25513)
Deterministic time = 1617296.82 ticks (224.43 ticks/sec)
CPLEX> dis sol best
Current MIP best bound = 2.6326587715e+13 (gap = 9.37612e+11, 3.44%)
CPLEX> dis sol obj
MIP - Time limit exceeded, integer feasible: Objective = 2.7264199938e+13And the kappa is as following.
Incumbent solution:
MILP objective 2.7264199938e+13
MILP solution norm |x| (Total, Max) 4.73889e+08 3.43200e+06
MILP solution error (Ax=b) (Total, Max) 2.00259e-08 2.32831e-10
MILP x bound error (Total, Max) 8.00003e-03 1.00000e-04
MILP x integrality error (Total, Max) 0.00000e+00 0.00000e+00
MILP slack bound error (Total, Max) 7.60020e-03 1.00000e-04
Branch-and-cut subproblem optimization:
Max condition number: 1.3429e+12
Percentage (number) of stable bases: 0.00% (0)
Percentage (number) of suspicious bases: 97.51% (59730)
Percentage (number) of unstable bases: 2.49% (1525)
Percentage (number) of ill-posed bases: 0.00% (0)
Attention level: 0.017220
CPLEX encountered numerical difficulties while solving this model.
The best bound is 2.63265e+13, which is still greater than 2.63168e+13. It seems that integer feasible solution is excluded by cutting plane again... Not sure is this a proof that cplex cutting plane may cut off a integer feasible solution?
This time, I get a worse objective value 2.7264e+13 and the gap is 3.44%. I guess setting kappa and emphasis on numerical significantly lower the solving, and the result I get is restricted by time limit. Therefore, I am going to solve it again without time limit and keep other setting similar to this time. I will post it maybe tomorrow or next week. Let's see what will happen!
------------------------------
Chia-Yuan Wu
------------------------------
Original Message:
Sent: Tue June 16, 2020 01:09 PM
From: Paul Rubin
Subject: MIP - Best Integer VS Best Bound
I'm not really an expert on numerical stability, but a condition number of 5e+08, while not the worst I've seen, is not encouraging. The good news is that none of the bases encountered were unstable (bad) or ill-posed (very bad). The fact that all the bases were "suspicious" is probably a result of the very large coefficients you have in some of your constraints.
Overall, I would say that this report suggests that numerical issues are not bad. Unfortunately, that neither proves nor disproves the conjecture that numerical problems led CPLEX to generate a cut that cut off the optimal solution. You could try setting the numerical emphasis parameter to on and then retry the first run and see if the optimum gets cut off again. The numerical emphasis setting will slow the solver a bit, but I think you will still get a result in an acceptable amount of time.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------
Original Message:
Sent: Mon June 15, 2020 10:12 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound
Hi Paul,
I set the kappa before I solve the problem, and the result is as following.
This is my first time to set kappa... All I can understand is that "CPLEX encountered numerical difficulties while solving this model" ... :(
For other information, how can I interpret it? Does it provide any important information?
Branch-and-cut subproblem optimization:Max condition number: 5.3910e+08Percentage (number) of stable bases: 0.00% (0)Percentage (number) of suspicious bases: 100.00% (119)Percentage (number) of unstable bases: 0.00% (0)Percentage (number) of ill-posed bases: 0.00% (0)Attention level: 0.010000CPLEX encountered numerical difficulties while solving this model.
------------------------------
Chia-Yuan Wu
Original Message:
Sent: Mon June 15, 2020 10:59 AM
From: Paul Rubin
Subject: MIP - Best Integer VS Best Bound
CPLEX cannot add a cut that renders infeasible a solution it has already found (at least in theory), but in your no-polishing run it has not found the better solution you mention. In theory, CPLEX should not cut off an optimal solution, but in practice bad numerics plus rounding error might cause that to happen. Your constraint matrix coefficients span 11 orders of magnitude, which is not the worst I've ever seen but could possibly create problems. It is also possible to have numeric precision problems that are not caused by mixtures of large and small numbers.
If you are using the interactive optimizer, try issuing the command "set mip strategy kappa" before solving. Set the parameter to 2. Once the solver is done, there is a display command to show the kappa statistics. They will tell you whether CPLEX encountered numerically problematic (unstable) bases.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Mon June 15, 2020 01:34 AM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound
Hi Paul,
Yes, I guess cplex adds a cut so that it makes the best bound increase. But I doubt that this cut may remove some integer feasible solution, since there exists a better integer solution with objective value being 2.6316820597e+13 from polishing. Is it possible for cplex to remove some integer feasible solution when it adds cuts?
I have to admit my problem may have some numerical issues... I paste my problem statistics below. Cplex engineer, Danial, has told me many times that I had better lower the range of problem coefficient, but unfortunately, so far I couldn't do that due to the scenario restriction...
Objective sense : MinimizeVariables : 1063687 [Box: 858680, Binary: 205007]Objective nonzeros : 134961Linear constraints : 1137395 [Less: 549484, Greater: 116817, Equal: 471094] Nonzeros : 4844344 RHS nonzeros : 209187Variables : Min LB: 0.0000000 Max UB: 2.147484e+09Objective nonzeros : Min : 1.000000 Max : 4.472000e+07Linear constraints : Nonzeros : Min : 1.314905e-06 Max : 760511.0 RHS nonzeros : Min : 1.000000 Max : 3432000
------------------------------
Chia-Yuan Wu
Original Message:
Sent: Sun June 14, 2020 11:16 PM
From: Paul Rubin
Subject: MIP - Best Integer VS Best Bound
I'm not sure what the best way to get fixed width font is. I used the code input window (the tool bar button {;}) and picked Java as the language (but probably any language would do). There should be a better way, but I do not know what it is.
The word "cutoff" means that the node at which that log line was printed was pruned/fathomed, presumably due to its bound being worse than the current incumbent solution. I don't recall whether nodes with infeasible LPs also are printed as "cutoff" or whether they appear in the log as "infeasible". A node with an LP whose solution is integer-feasible will say "integral" in those two columns if it is a new incumbent; if not, I assume it will say "cutoff".
As to why the lower bound increased at the end of the first run, there is no way to know from the log. I suspect CPLEX added a cut that tightened the bound. Why did it raise the bound above the value of the optimal solution in the second run? Probably bad numerics in the model. You might consider printing out the model statistics and having CPLEX collect kappa (basis condition number) statistics during a run without polishing.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Sun June 14, 2020 09:25 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound
Hi Paul,
Sorry for the messy log format. I would love to fix it as your post, but I don't know how to do it... Where can I set the fixed width font?
Back to your answer, I can't understand "The word "cutoff" replaces both the node objective value and the number of integer infeasibilities". What does it mean?
If "cutoff" appears in Objective Column, how do we interpret it normally? My biggest question is obviously there exists a better integer solution with objective value 2.6316820597e+13. Why does the solver terminate at objective 2.6318239290e+13 when I don't turn on polishing and why can the best bound increase from 2.6316820597e+13 to 2.6318239290e+13?
------------------------------
Chia-Yuan Wu
Original Message:
Sent: Fri June 12, 2020 04:58 PM
From: Paul Rubin
Subject: MIP - Best Integer VS Best Bound
It would help readability if you pasted logs in using a fixed width font. At any rate, I'm looking at the last line of the node log for the run without polishing:
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
As I read that, the best known integer solution has value 2.63182e+13, the best bound is 2.63168e+13, there have been 283,017 iterations, and the gap is 0.01%. The word "cutoff" replaces both the node objective value and the number of integer infeasibilities. I think you might be misreading the line.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University