MIP - Best Integer VS Best Bound | Decision Optimization

5. RE: MIP - Best Integer VS Best Bound

Like

Chia-Yuan Wu

Posted Mon June 15, 2020 01:35 AM

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      : Minimize
Variables            : 1063687  [Box: 858680,  Binary: 205007]
Objective nonzeros   :  134961
Linear constraints   : 1137395  [Less: 549484,  Greater: 116817,  Equal: 471094]
  Nonzeros           : 4844344
  RHS nonzeros       :  209187

Variables            : Min LB: 0.0000000        Max UB: 2.147484e+09
Objective nonzeros   : Min   : 1.000000         Max   : 4.472000e+07
Linear constraints   :
  Nonzeros           : Min   : 1.314905e-06     Max   : 760511.0
  RHS nonzeros       : Min   : 1.000000         Max   : 3432000

------------------------------
Chia-Yuan Wu
------------------------------

Original Message

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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------

#DecisionOptimization

6. RE: MIP - Best Integer VS Best Bound

Like

Paul Rubin

Posted Mon June 15, 2020 11:00 AM

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

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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------

#DecisionOptimization

7. RE: MIP - Best Integer VS Best Bound

Like

Chia-Yuan Wu

Posted Mon June 15, 2020 10:13 PM

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+08
Percentage (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.010000
CPLEX encountered numerical difficulties while solving this model.

------------------------------
Chia-Yuan Wu
------------------------------

Original Message

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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------

#DecisionOptimization

8. RE: MIP - Best Integer VS Best Bound

Like

Paul Rubin

Posted Tue June 16, 2020 01:09 PM

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

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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------

#DecisionOptimization

9. RE: MIP - Best Integer VS Best Bound

Like

Chia-Yuan Wu

Posted Wed June 17, 2020 02:38 AM
Edited by System Admin Fri January 20, 2023 04:46 PM

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+13

And 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

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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------
#DecisionOptimization

10. RE: MIP - Best Integer VS Best Bound

Like

Paul Rubin

Posted Wed June 17, 2020 12:33 PM

This is informative, because it appears the with numerical emphasis on you have a lower bound that cuts of the "optimal" solutions of both your original runs. I suggest that you try substituting both the without-polishing solution and the with-polishing solution into your model and see whether they actually satisfy the constraints to within CPLEX tolerances. It is possible that both solutions are actually infeasible, but were accepted by CPLEX due to rounding problems.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message

Original Message:
Sent: Wed June 17, 2020 02:38 AM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi Paul,

I take your advice and set emphasis on numerical. And the node log is as following.

CPXPARAM_TimeLimit                               7200CPXPARAM_Emphasis_Numerical                      1CPXPARAM_MIP_Tolerances_MIPGap                   0CPXPARAM_MIP_Strategy_KappaStats                 2Aggregator 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 modelTried 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 modelInteger feasible solution rejected --- infeasible on original modelHeuristic 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:  3Flow cuts applied:  158Mixed integer rounding cuts applied:  204Gomory fractional cuts applied:  430Root 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+13Current 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 bestCurrent MIP best bound =  2.6326587715e+13 (gap = 9.37612e+11, 3.44%)CPLEX> dis sol objMIP - Time limit exceeded, integer feasible:  Objective =  2.7264199938e+13

And the kappa is as following.

Incumbent solution:MILP objective                                 2.7264199938e+13MILP solution norm |x| (Total, Max)            4.73889e+08  3.43200e+06MILP solution error (Ax=b) (Total, Max)        2.00259e-08  2.32831e-10MILP x bound error (Total, Max)                8.00003e-03  1.00000e-04MILP x integrality error (Total, Max)          0.00000e+00  0.00000e+00MILP slack bound error (Total, Max)            7.60020e-03  1.00000e-04Branch-and-cut subproblem optimization:Max condition number:                    1.3429e+12Percentage (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.017220CPLEX 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

Original Message:
Sent: Thu June 11, 2020 11:40 PM
From: Chia-Yuan Wu
Subject: MIP - Best Integer VS Best Bound

Hi,

I am solving an MIP Problem with .sav file twice via Interactive by different cplex param setting. The common setting include timelimit 3600s and mip mipgap 0. The only different setting between these two are one with polishafter 0 second and the other not.

I know Best Bound provides a valid lower bound for a minimal problem. I find that for the one without polishing, from the node log, it shows that Best Bound is 2.63168e+13, but when gap reaches 0%, and it finally comes out with the best bound 2.63182e+13. Since gap is 0%, the Best Integer is 2.63182e+13, which is the optimal objective value cplex gives me. However, for the one with polishing, the Best Bound is 2.63168e+13 from node log. And when gap equals to 0%, both Best Bound and Best Integer are 2.63168e+13. Obviously, the solution with polishing is better than without polishing (this is a minimal problem). My question is that why the one without polishing, of which Best Bound increases from 2.63168e+13 to 2.63182e+13. It seems to exist a better Integer solution... What I expect is Best Bound remains 2.63168e+13, and Best Integer decreases from 2.63182e+13 to 2.63168e+13 so that the gap reaches 0% and I can gain a better solution.

I provide the node log here.

Without polishing:

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 30.75 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 46.20 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.98 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.95 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.50 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.86 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
* 0+ 0 2.63360e+13 2.63168e+13 0.07%
* 0+ 0 2.63211e+13 2.63168e+13 0.02%
0 0 2.63168e+13 1125 2.63211e+13 Cuts: 682 121628 0.02%
0 0 2.63168e+13 949 2.63210e+13 Cuts: 5362 143136 0.02%
0 0 2.63168e+13 938 2.63182e+13 Cuts: 2714 188092 0.01%
0 0 2.63168e+13 890 2.63182e+13 Cuts: 3790 239675 0.01%
0 0 2.63168e+13 664 2.63182e+13 Cuts: 3151 260850 0.01%
0 0 2.63168e+13 702 2.63182e+13 Cuts: 1646 282360 0.01%
0 0 cutoff 2.63182e+13 2.63168e+13 283017 0.01%
Elapsed time = 501.97 sec. (318850.28 ticks, tree = 0.01 MB, solutions = 4)

Implied bound cuts applied: 234
Flow cuts applied: 703
Mixed integer rounding cuts applied: 4692
Flow path cuts applied: 7
Gomory fractional cuts applied: 154

Root node processing (before b&c):
Real time = 502.20 sec. (318913.27 ticks)
Parallel b&c, 24 threads:
Real time = 5.69 sec. (624.12 ticks)
Sync time (average) = 0.21 sec.
Wait time (average) = 2.15 sec.
------------
Total (root+branch&cut) = 507.89 sec. (319537.39 ticks)

Solution pool: 6 solutions saved.

MIP - Integer optimal solution: Objective = 2.6318239290e+13
Solution time = 507.91 sec. Iterations = 283017 Nodes = 0
Deterministic time = 319540.43 ticks (629.13 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6318239290e+13
CPLEX> dis sol best
Current MIP best bound = 2.6318239290e+13 (gap = 1.20313, 0.00%)

With polishing: (Better solution)

CPLEX> opt
CPXPARAM_TimeLimit 3600
CPXPARAM_MIP_Tolerances_MIPGap 0
CPXPARAM_MIP_PolishAfter_Time 0
Aggregator has done 197337 substitutions...
Tried aggregator 11 times.
Aggregator has done 201516 substitutions...
MIP Presolve eliminated 494054 rows and 400145 columns.
MIP Presolve added 925 rows and 0 columns.
MIP Presolve modified 128168 coefficients.
Aggregator did 201516 substitutions.
Reduced MIP has 442750 rows, 461632 columns, and 2521682 nonzeros.
Reduced MIP has 22161 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 31.13 sec. (20641.51 ticks)
Found incumbent of value 7.1972772e+14 after 47.09 sec. (31106.79 ticks)
Probing fixed 0 vars, tightened 83428 bounds.
Probing time = 1.97 sec. (303.75 ticks)
Tried aggregator 3 times.
MIP Presolve eliminated 39553 rows and 22671 columns.
MIP Presolve modified 22328 coefficients.
Aggregator did 85 substitutions.
Reduced MIP has 403112 rows, 438876 columns, and 2410830 nonzeros.
Reduced MIP has 22146 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 12.03 sec. (1976.82 ticks)
Probing fixed 0 vars, tightened 804 bounds.
Probing time = 1.47 sec. (70.08 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 43.56 sec. (17534.51 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

* 0+ 0 2.65728e+13 -1.29579e+14 587.64%
0 0 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%

Starting condition for polishing reached (PolishAfterTime).
Starting solution polishing.

0 2 2.63168e+13 113 2.65728e+13 2.63168e+13 118474 0.96%
Elapsed time = 122.47 sec. (60113.51 ticks, tree = 0.01 MB, solutions = 2)
* 1+ 1 2.63360e+13 2.63168e+13 0.07%
* 1+ 1 2.63359e+13 2.63168e+13 0.07%
* 1+ 1 2.63268e+13 2.63168e+13 0.04%
* 1+ 1 2.63168e+13 2.63168e+13 0.00%

Root node processing (before b&c):
Real time = 118.70 sec. (59941.29 ticks)
Parallel b&c, 24 threads:
Real time = 3484.30 sec. (2681661.92 ticks)
Sync time (average) = 35.32 sec.
Wait time (average) = 1.87 sec.
------------
Total (root+branch&cut) = 3603.00 sec. (2741603.21 ticks)

Solution pool: 13 solutions saved.

MIP - Integer optimal solution: Objective = 2.6316820597e+13
Solution time = 3603.03 sec. Iterations = 118478 Nodes = 1
Deterministic time = 2741606.26 ticks (760.92 ticks/sec)

CPLEX> dis sol obj
MIP - Integer optimal solution: Objective = 2.6316820597e+13
CPLEX> dis sol best
Current MIP best bound = 2.6316820597e+13 (gap = 0, 0.00%)

------------------------------
Chia-Yuan Wu
------------------------------
#DecisionOptimization

Decision Optimization

Decision Optimization