Originally posted by: SystemAdmin

Hi Folks,

I　encountered numerical issues when solving my problem (single thread and dual simplex method is used, markowitz threshold is set to 0.99999, CPLEX 12.2). I queried the stats of my problem, everything seems okay

Variables            :    7159  [Nneg: 266,  Fix: 1,  Binary: 6892]
Objective nonzeros   :    7159
Linear constraints   :    7772  [Less: 7149,  Greater: 518,  Equal: 105]
  Nonzeros           :  240342
  RHS nonzeros       :    7149
 
Variables            : Min LB: 0.0000000        Max UB: 1.000000
Objective nonzeros   : Min   : 1.000000         Max   : 1000.000
Linear constraints   :
  Nonzeros           : Min   : 1.000000         Max   : 10.00000
  RHS nonzeros       : Min   : 1.000000         Max   : 10.00000

I really appreciate for any help. Thanks.
The model file in .sav format is also attached.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Also I checked the kappa value which also seems fine:

Condition number of basis = 8.5e+004

And the error message I got from CPLEX:

CPLEX Error  1256: Basis singular.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't know what's going on, but I can confirm the issue. I ran your file on CPLEX 12.4.0.1 with all default settings, except that I told it to collect kappa statistics at every node. About 11 minutes into the run, still at the root node, I got error 1256 (but the run continued). I aborted the run and was told that the problem was integer feasible (three solutions in the pool) and that 100% of the bases were stable (largest condition number so far 1.2136e+06).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Paul Rubin wrote:
> I don't know what's going on, but I can confirm the issue. I ran your file on CPLEX 12.4.0.1 with all default settings, except that I told it to collect kappa statistics at every node. About 11 minutes into the run, still at the root node, I got error 1256 (but the run continued). I aborted the run and was told that the problem was integer feasible (three solutions in the pool) and that 100% of the bases were stable (largest condition number so far 1.2136e+06).
>
> Paul
>
> Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
Not only are the original model numerics OK, but the numerics of the presolved model are also
fine. Furthermore, the problem can be reproduced at the initial LP relaxation solve using either
the dual or primal simplex method. That means that the cuts CPLEX may add to the model are
not involved in the LP issues here.

I will take a closer look at this. Meanwhile, try running the model with the numerical
emphasis parameter turned on. At least for the initial LP relaxation solve, that seems
to help the dual simplex method significantly.

For future reference, here are a couple of things you can do
to get more information in a situation like this. First, set the MIP display parameter to 4, so
you can see the initial node LP solve output. Doing this with startalgorithm set to 2 to select
the dual simplex method reveals that the dual simplex method is definitely having some sort of
numerical trouble with the model, well before the final error termination:

Iteration: 58320 Dual objective = 34842.543124
Iteration: 58494 Dual objective = 34842.543123
Repairing basis singularity.
Dual 'id12171' fixed because of singularity.
Added to 1d columns superbasic list.
Dual 'id15941' fixed because of singularity.
Added to 1d columns superbasic list.
Iteration: 58595 Dual infeasibility = 12995993208.442230
Repairing basis singularity.
Dual 'id12159' fixed because of singularity.
Added to 1d columns superbasic list.
Iteration: 58601 Dual infeasibility = 249089148.585084
Iteration: 58701 Dual infeasibility = 1434077023757887.500000
Elapsed time = 187.90 sec. (59000 iterations).
Iteration: 59202 Dual infeasibility = 1424556877204855.750000
...

Iteration: 99048 Dual infeasibility = 0.000005
Iteration: 99102 Dual objective = 34857.884805
Iteration: 99202 Dual objective = 34847.413743
Iteration: 99303 Dual objective = 34847.061503
Iteration: 99465 Dual objective = 34843.331894
Repairing basis singularity.
Dual 'id10483' fixed because of singularity.
Dual 'id11723' fixed because of singularity.
Dual 'id13633' fixed because of singularity.
Dual 'id14397' fixed because of singularity.
Dual 'id15157' fixed because of singularity.
Dual 'id19261' fixed because of singularity.
Dual 'id19363' fixed because of singularity.
Dual 'id19651' fixed because of singularity.
Dual 'id20409' fixed because of singularity.
Added to 9d columns superbasic list.
Iteration: 99566 Dual infeasibility = 0.000475
Iteration: 99712 Dual infeasibility = 0.000006
Iteration: 99735 Dual objective = 34843.221766

...

Iteration: 103788 Dual objective = 34840.889596
Iteration: 103943 Dual objective = 34840.882656
Removing perturbation.
CPLEX Error 1256: Basis singular.
Root relaxation solution time = 386.44 sec.

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

• 0+ 0 0.0000 0 ---
• 0+ 0 9700.0000 0 ---

Root node processing (before b&c):
Real time = 386.61
Parallel b&c, 4 threads:
Real time = 0.00
Sync time (average) = 0.00
Wait time (average) = 0.00

---

Total (root+branch&cut) = 386.61 sec.
You can also set the mip display parameter to 5 to see subsequent node LP solve output,
but that can often generate more output than you want to see, and is not needed in this case.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ed,

Do bases with singularities not get counted when kappa statistics are accumulated? The kappa stats (100% stable) seem inconsistent with the singularity messages.

Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Paul Rubin wrote:
> Ed,
>
> Do bases with singularities not get counted when kappa statistics are accumulated? The kappa stats (100% stable) seem inconsistent with the singularity messages.
>
> Paul
The kappa statistics require a basis factorization for the kappa computation, regardless of whether
CPLEX computes kappa exactly or using an less expensive estimate. So, the kappa statistics do not
include singular bases, which can be viewed as having an infinite condition number.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Moreover, the MIP kappa statistics only include the final LP bases. Hitting singular bases during the simplex solve from which CPLEX was able to recover does not matter. And in fact, this is fine, because if CPLEX comes up in the end with a stable basis that is primal and dual feasible, then the path for reaching this basis is irrelevant (except that intermediate singular bases can increase the solve time).

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, the intermediate singular bases did increase the solve time and from my observation, the increase is significant for this model.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> jimzhang wrote:
> Yes, the intermediate singular bases did increase the solve time and from my observation, the increase is significant for this model.

Are you saying you still get intermediate singular bases even if you turn on CPLEX's numerical emphasis?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, here is the log for iterations after I turn on CPLEX's numerical emphasis (# of threads is set to 1 and I am using 12.2.0.2)

New value 

for extreme numerical caution emphasis: yes

Read time =    0.00 sec. Problem changed to LP. Tried aggregator 1 time. LP Presolve eliminated 167 rows and 120 columns. Reduced LP has 7605 rows, 7039 columns, and 239050 nonzeros. Presolve time =    0.06 sec.   Iteration log . . . Iteration:     1   Dual objective     =        323950.000000 Iteration:   416   Dual objective     =        314070.000000 Iteration:   838   Dual objective     =        304220.000000 Iteration:  1271   Dual objective     =        294340.000000 Iteration:  1709   Dual objective     =        284180.000000 Iteration:  2158   Dual objective     =        273660.000000 Perturbation started. Iteration:  2403   Dual objective     =        270710.000000 Iteration:  2691   Dual objective     =         35223.331340 Iteration:  2887   Dual objective     =         35145.414631 Iteration:  3085   Dual objective     =         35071.664583 Iteration:  3269   Dual objective     =         35022.081213 Iteration:  3478   Dual objective     =         34966.252058 Iteration:  3654   Dual objective     =         34949.999394 Iteration:  3847   Dual objective     =         34919.998011 Iteration:  4003   Dual objective     =         34919.997867 Iteration:  4214   Dual objective     =         34919.997757 Iteration:  4421   Dual objective     =         34909.997758 Iteration:  4615   Dual objective     =         34899.997811 Iteration:  4789   Dual objective     = 34896.519352 Iteration:  4953   Dual objective     =         34885.539786 Iteration:  5138   Dual objective     =         34873.623289 Iteration:  5321   Dual objective     =         34870.787891 Iteration:  5464   Dual objective     =         34869.249189 Iteration:  5641   Dual objective     =         34867.041623 Iteration:  5827   Dual objective     =         34866.522435 Iteration:  5984   Dual objective     =         34865.693606 Iteration:  6143   Dual objective     =         34865.400108 Iteration:  6314   Dual objective     =         34863.302324 Iteration:  6445   Dual objective     =         34863.049587 Iteration:  6588   Dual objective     =         34861.504001 Iteration:  6739   Dual objective     =         34858.644134 Iteration:  6866   Dual objective     =         34858.301406 Iteration:  7004   Dual objective     =         34857.358862 Iteration:  7128   Dual objective     =         34856.777735 Iteration:  7256   Dual objective     =         34854.964817 Iteration:  7426   Dual objective     =         34853.640189 Iteration:  7606   Dual objective     =         34853.366002 Repairing basis singularity. Added to superbasic list. Markowitz threshold set to 0.99999 Iteration:  7611   Dual infeasibility =          1842.280772 Iteration:  7914   Dual infeasibility =             0.650049 Iteration:  8153   Dual infeasibility =             1.454494 Iteration:  8346   Dual infeasibility =             0.363782 Iteration:  8524   Dual infeasibility =             0.034774 Repairing basis singularity. Added to superbasic list. Iteration:  8717   Dual infeasibility =             0.032197 Iteration:  8893   Dual infeasibility =             0.003359 Iteration:  9061   Dual infeasibility =             0.000008 Iteration:  9137   Dual objective     =         34868.319740 Iteration:  9283   Dual objective     =         34860.601370 Iteration:  9448   Dual objective     =         34859.989941 Iteration:  9657   Dual objective     =         34858.910774 Iteration:  9858   Dual objective     =         34854.858033 Iteration: 10019   Dual objective     =         34849.459034 Iteration: 10164   Dual objective     =         34849.256079 Iteration: 10291   Dual objective     =         34849.144178 Iteration: 10404   Dual objective     =         34848.929576 Iteration: 10530   Dual objective     =         34848.920692 Iteration: 10649   Dual objective     =         34848.920516 Iteration: 10787   Dual objective     =         34848.920275 Iteration: 10914   Dual objective     =         34848.920058 Iteration: 11045   Dual objective     =         34848.837228 Iteration: 11196   Dual objective     =         34848.251278 Iteration: 11327   Dual objective     =         34846.841207 Iteration: 11462   Dual objective     =         34846.841169 Iteration: 11618   Dual objective     =         34846.674186 Iteration: 11758   Dual objective     =         34846.674172 Iteration: 11917   Dual objective     =         34846.089600 Elapsed time =   10.97 sec. (12000 iterations). Iteration: 12062   Dual objective     =         34846.081245 Iteration: 12210   Dual objective     =         34845.852803 Iteration: 12355   Dual objective     =         34845.847371 Iteration: 12494   Dual objective     =         34845.832778 Iteration: 12619   Dual objective     =         34845.830345 Iteration: 12737   Dual objective     =         34845.826079 Iteration: 12871   Dual objective     =         34845.826071 Iteration: 12997   Dual objective     =         34845.826060 Iteration: 13135   Dual objective     =         34845.826058 Iteration: 13271   Dual objective     =         34845.817571 Iteration: 13410   Dual objective     =         34845.817565 Iteration: 13532   Dual objective     =         34845.817557 Iteration: 13648   Dual objective     =         34845.808556 Iteration: 13788   Dual objective     =         34845.705730 Iteration: 13901   Dual objective     =         34845.665995 Iteration: 14031   Dual objective     =         34845.665840 Iteration: 14157   Dual objective     =         34845.665688 Iteration: 14328   Dual objective     = 34845.662599 Iteration: 14463   Dual objective     =         34845.583538 Iteration: 14591   Dual objective     =         34845.135094 Iteration: 14733   Dual objective     =         34845.054179 Iteration: 14879   Dual objective     =         34844.994518 Iteration: 15024   Dual objective     =         34844.934557 Iteration: 15154   Dual objective     =         34844.864525 Iteration: 15294   Dual objective     =         34844.615622 Iteration: 15450   Dual objective     =         34844.390341 Iteration: 15575   Dual objective     =         34844.338671 Iteration: 15734   Dual objective     =         34844.254779 Iteration: 15921   Dual objective     =         34844.000620 Iteration: 16075   Dual objective     =         34843.921655 Iteration: 16211   Dual objective     =         34843.870168 Iteration: 16339   Dual objective     =         34843.857752 Iteration: 16463   Dual objective     =         34843.855969 Iteration: 16613   Dual objective     =         34843.849973 Iteration: 16801   Dual objective     =         34843.847439 Iteration: 16952   Dual objective     =         34843.781505 Elapsed time =   22.87 sec. (17000 iterations). Iteration: 17095   Dual objective     =         34843.739892 Iteration: 17246   Dual objective     =         34843.580452 Iteration: 17416   Dual objective     =         34843.573228 Iteration: 17566   Dual objective     =         34843.565507 Iteration: 17708   Dual objective     =         34843.546217 Iteration: 17836   Dual objective     =         34843.537675 Iteration: 17937   Dual objective     =         34843.533071 Iteration: 18070   Dual objective     =         34843.525846 Iteration: 18171   Dual objective     =         34843.524945 Iteration: 18303   Dual objective     =         34843.523585 Repairing basis singularity. Added to superbasic list. Added to superbasic list. Added to superbasic list. Added to superbasic list. Added to superbasic list. Iteration: 18312   Dual infeasibility =             9.509961 Iteration: 18561   Dual infeasibility =             0.295272 Iteration: 18770   Dual infeasibility =             0.054270 Iteration: 18903   Dual infeasibility =             0.018431 Iteration: 19067   Dual infeasibility =             0.004411 Iteration: 19232   Dual infeasibility =             0.002087 Iteration: 19403   Dual infeasibility =             0.000702 Iteration: 19558   Dual infeasibility =             0.000186 Iteration: 19626   Dual objective     =         34845.246605 Iteration: 19776   Dual objective     =         34845.054200 Iteration: 19910   Dual objective     =         34844.707344 Iteration: 20028   Dual objective     =         34844.115043 Iteration: 20162   Dual objective     =         34844.093144 Iteration: 20317   Dual objective     =         34843.996649 Iteration: 20467   Dual objective     =         34843.991754 Iteration: 20603   Dual objective     =         34843.622167 Iteration: 20733   Dual objective     =         34843.564383 Iteration: 20903   Dual objective     =         34843.405893 Elapsed time =   34.48 sec. (21000 iterations). Iteration: 21039   Dual objective     =         34843.201894 Iteration: 21189   Dual objective     =         34842.835051 Iteration: 21334   Dual objective     =         34842.465117 Iteration: 21474   Dual objective     =         34842.166243 Iteration: 21597   Dual objective     =         34842.163302 Iteration: 21754   Dual objective     =         34842.108822 Iteration: 21894   Dual objective     =         34842.081867 Iteration: 22052   Dual objective     =         34841.978895 Iteration: 22224   Dual objective     =         34841.549959 Iteration: 22381   Dual objective     =         34841.447616 Iteration: 22520   Dual objective     =         34841.270782 Iteration: 22671   Dual objective     =         34841.270332 Iteration: 22815   Dual objective     =         34841.267669 Iteration: 22925   Dual objective     =         34841.151283 Iteration: 23070   Dual objective     =         34841.151275 Iteration: 23208   Dual objective     =         34841.151264 Iteration: 23343   Dual objective     = 34841.151236 Iteration: 23491   Dual objective     =         34841.148941 Iteration: 23619   Dual objective     =         34841.146487 Iteration: 23743   Dual objective     =         34841.146338 Iteration: 23878   Dual objective     =         34841.145934 Iteration: 24013   Dual objective     =         34841.145728 Iteration: 24174   Dual objective     =         34841.145707 Iteration: 24318   Dual objective     =         34841.145696 Iteration: 24419   Dual objective     =         34841.136154 Repairing basis singularity. Dual 
'id9616' fixed because of singularity. Added to superbasic list. Dual 
'id10159' fixed because of singularity. Added to superbasic list. Iteration: 24519   Dual infeasibility =            48.377625 Iteration: 24537   Dual infeasibility =             0.999442 Iteration: 24573   Dual infeasibility =             1.542147 Iteration: 24728   Dual infeasibility =             0.316028 Iteration: 24981   Dual infeasibility =             0.025299 Elapsed time =   47.52 sec. (25000 iterations). Iteration: 25215   Dual infeasibility =             0.009543 Iteration: 25363   Dual infeasibility =             0.001593 Iteration: 25555   Dual infeasibility =             0.000143 Iteration: 25718   Dual infeasibility =             0.000091 Iteration: 25878   Dual infeasibility =             0.000024 Iteration: 26039   Dual infeasibility =             0.000001 Iteration: 26046   Dual objective     =         34841.444673 Iteration: 26202   Dual objective     =         34841.397980 Iteration: 26358   Dual objective     =         34841.165274 Iteration: 26519   Dual objective     =         34841.164694 Iteration: 26678   Dual objective     =         34841.141824 Iteration: 26825   Dual objective     =         34841.138471 Iteration: 26962   Dual objective     =         34841.136165 Iteration: 27123   Dual objective     =         34841.129107 Iteration: 27262   Dual objective     =         34841.098896 Iteration: 27405   Dual objective     =         34841.097197 Iteration: 27544   Dual objective     =         34841.033029 Iteration: 27693   Dual objective     =         34841.031800 Iteration: 27855   Dual objective     =         34841.028599 Iteration: 28011   Dual objective     =         34841.009914 Iteration: 28151   Dual objective     =         34841.009827 Iteration: 28285   Dual objective     =         34840.956345 Iteration: 28418   Dual objective     =         34840.952773 Iteration: 28566   Dual objective     =         34840.936826 Iteration: 28686   Dual objective     =         34840.931911 Iteration: 28834   Dual objective     =         34840.929733 Elapsed time =   59.73 sec. (29000 iterations). Iteration: 29023   Dual objective     =         34840.927762 Iteration: 29179   Dual objective     =         34840.927447 Iteration: 29337   Dual objective     =         34840.925507 Iteration: 29500   Dual objective     =         34840.923196 Iteration: 29617   Dual objective     =         34840.920957 Iteration: 29737   Dual objective     =         34840.914050 Iteration: 29908   Dual objective     =         34840.901636 Iteration: 30047   Dual objective     =         34840.878571 Iteration: 30201   Dual objective     =         34840.852072 Iteration: 30342   Dual objective     =         34840.832872 Iteration: 30461   Dual objective     =         34840.823873 Iteration: 30561   Dual objective     =         34840.816037 Iteration: 30700   Dual objective     =         34840.807845 Iteration: 30801   Dual objective     =         34840.798407 Iteration: 30902   Dual objective     =         34840.796216 Iteration: 31003   Dual objective     =         34840.795374 Iteration: 31104   Dual objective     =         34840.789552 Iteration: 31169   Dual objective     =         34840.788558 Iteration: 31192   Dual objective     =         34840.788553 Iteration: 31195   Dual infeasibility =             0.177700 Iteration: 31203   Dual objective     =         34840.858153 Removing perturbation. Iteration: 31238   Dual infeasibility =            15.286609 Iteration: 31316   Dual objective     =         34853.861798 Iteration: 31467   Dual objective     =         34842.406246 Iteration: 31544   Dual objective     =         34742.466042 Iteration: 31644   Dual objective     =         34742.466042 Iteration: 31765   Dual objective     =         34742.466041 Iteration: 31905   Dual objective     =         34742.282341 Elapsed time =   70.31 sec. (32000 iterations). Iteration: 32049   Dual objective     =         34742.282341 Iteration: 32238   Dual objective     =         34742.282340 Iteration: 32415   Dual objective     =         34737.033180 Iteration: 32550   Dual objective     =         34737.033179 Iteration: 32678   Dual objective     =         34737.033171 Iteration: 32785   Dual objective     =         34736.901263 Iteration: 32906   Dual objective     =         34736.868743 Iteration: 33025   Dual objective     =         34736.662646 Iteration: 33137   Dual objective     =         34736.618967 Iteration: 33238   Dual objective     =         34736.509027 Iteration: 33351   Dual objective     =         34736.503174 Iteration: 33491   Dual objective     =         34736.392167 Iteration: 33592   Dual objective     =         34735.659225 Iteration: 33693   Dual objective     =         34735.149148 Iteration: 33812   Dual objective     =         34734.948534 Iteration: 33965   Dual objective     =         34734.908505 Iteration: 34068   Dual objective     =         34734.861876 Iteration: 34182   Dual objective     =         34734.847381 Iteration: 34326   Dual objective     =         34734.818432 Iteration: 34493   Dual objective     =         34734.746866 Removing shift (1508). Iteration: 34531   Dual infeasibility =           911.543095 Iteration: 34727   Dual infeasibility =            15.071144 Iteration: 34906   Dual infeasibility =             0.537401 Elapsed time =   80.48 sec. (35000 iterations). Iteration: 35151   Dual infeasibility =             0.464713 Iteration: 35253   Dual objective     =         34860.152257 Iteration: 35380   Dual objective     =         34856.784576 Iteration: 35481   Dual objective     =         34856.426757 Iteration: 35607   Dual objective     =         34856.383390 Iteration: 35715   Dual objective     =         34856.279069 Iteration: 35867   Dual objective     =         34855.018162 Iteration: 35986   Dual objective     =         34852.555635 Iteration: 36104   Dual objective     =         34852.393163 Repairing basis singularity. Dual 
'id22679' fixed because of singularity. Added to superbasic list. Iteration: 36260   Dual objective     =         34847.777952 Iteration: 36417   Dual objective     =         34846.322065 Reperturbation started. Iteration: 36462   Dual objective     =         34845.334721 Iteration: 36589   Dual objective     =         34844.136229 Iteration: 36685   Dual objective     =         34843.656836 Iteration: 36856   Dual objective     =         34842.945689 Iteration: 37000   Dual objective     =         34842.632622 Iteration: 37129   Dual objective     =         34842.260922 Iteration: 37276   Dual objective     =         34841.801362 Iteration: 37435   Dual objective     =         34841.673795 Iteration: 37573   Dual objective     =         34841.673794 Iteration: 37683   Dual objective     =         34841.670766 Iteration: 37806   Dual objective     =         34841.572492 Iteration: 37950   Dual objective     =         34841.548885 Elapsed time =   91.09 sec. (38000 iterations). Iteration: 38095   Dual objective     =         34841.466558 Iteration: 38246   Dual objective     =         34841.454225 Iteration: 38398   Dual objective     =         34841.343824 Iteration: 38548   Dual objective     =         34841.343824 Iteration: 38696   Dual objective     =         34841.223453 Iteration: 38856   Dual objective     =         34841.143345 Iteration: 38988   Dual objective     =         34841.136451 Iteration: 39149   Dual objective     =         34841.136450 Iteration: 39299   Dual objective     =         34841.136450 Iteration: 39451   Dual objective     =         34841.136450 Iteration: 39615   Dual objective     =         34841.131901 Iteration: 39785   Dual objective     =         34841.040131 Iteration: 39922   Dual objective     =         34840.980255 Iteration: 40067   Dual objective     =         34840.918219 Iteration: 40239   Dual objective     =         34840.861125 Iteration: 40409   Dual objective     =         34840.753117 Iteration: 40533   Dual objective     =         34840.735220 Iteration: 40634   Dual objective     =         34840.697890 Iteration: 40766   Dual objective     =         34840.694092 Iteration: 40876   Dual objective     =         34840.684711 Iteration: 40977   Dual objective     =         34840.672170 Iteration: 41135   Dual objective     =         34840.630373 Iteration: 41300   Dual objective     =         34840.553244 Iteration: 41438   Dual objective     =         34840.528125 Iteration: 41591   Dual objective     =         34840.507540 Iteration: 41731   Dual objective     =         34840.473788 Iteration: 41906   Dual objective     =         34840.430282 Elapsed time =  103.76 sec. (42000 iterations). Iteration: 42052   Dual objective     =         34840.393711 Iteration: 42224   Dual objective     =         34840.391606 Iteration: 42374   Dual objective     =         34840.329083 Iteration: 42475   Dual objective     =         34840.288617 Iteration: 42612   Dual objective     =         34840.288597 Iteration: 42759   Dual objective     =         34840.246184 Iteration: 42860   Dual objective     =         34840.231465 Iteration: 42967   Dual objective     =         34839.999987 Iteration: 43077   Dual objective     =         34839.999986 Iteration: 43242   Dual objective     =         34839.999985 Iteration: 43270   Dual objective     =         34839.999985 Removing perturbation. Fixed rows satisfy optimality criteria.   Dual simplex - Optimal:  Objective = 3.4840000000e+004 Solution time =  107.97 sec.  Iterations = 43287 (5175)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

And I have some other cases with different inputs but the same model which could not be solved even after turning on numerical emphasis. Is there any email box I could send them to? Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> jimzhang wrote:
> And I have some other cases with different inputs but the same model which could not be solved even after turning on numerical emphasis. Is there any email box I could send them to? Thanks.
If you gzip them you could upload them to this forum, assuming they are of similar size to the one that you previously sent.

Meanwhile, we did look into the model that you already sent, and we confirmed that it has some bases that appear to have very high condition numbers despite the benign
coefficients in the constraint matrix. For example, take the attached SAV file,
which comes from the LP relaxation of the presolved model of the SAV file you previously updated. Read it into CPLEX, set a simplex iteration limit of 0 and
run the primopt command. The resulting solution has huge values and a huge condition
number:

CPLEX> d sol qu
Maximum bound infeasibility = 5.89546e+21
Maximum reduced-cost infeasibility = 3.74011e+24
Maximum Ax-b residual = 1.9455e+23
Maximum c-B'pi residual = 3.73668e+24
Maximum |x| = 5.72207e+21
Maximum |slack| = 5.89546e+21
Maximum |pi| = 1.13337e+23
Maximum |red-cost| = 3.74011e+24
Condition number of unscaled basis = 1.0e+75
This is one of the intermediate bases that CPLEX encountered, so that explains
the singular basis messages you saw. I had a look at the solution values that were
large and tried to use them to understand why a basis might have a huge condition
number like this. But, unfortunately, I was not successful. Perhaps with your
knowledge of your model you can do likewise and shed some light on this. In other
words, look at the variables with large solution values and the constraints they
intersect, and see if you can explain why such large values could arise.

Otherwise, if you have smaller models that reproduce this behavior, those might
help us as well. Also, an explanation of the model might help as well.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks, I will investigate it with your suggestions.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Ed,

I tried to read the 17459.sav, however, CPLEX gave me this error message

CPLEX> read C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cplex\bin\x86_w
in32\17459.sav
CPLEX Error  1560: File 'C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cp
lex\bin\x86_win32\17459.sav' is not a SAV file.

Have you any idea regarding this?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> jimzhang wrote:
> Hi Ed,
>
> I tried to read the 17459.sav, however, CPLEX gave me this error message
>

> CPLEX> read C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cplex\bin\x86_w
> in32\17459.sav
> CPLEX Error  1560: File 'C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cp
> lex\bin\x86_win32\17459.sav' is not a SAV file.
>

>
> Have you any idea regarding this?
>
> Thanks.

Jim,
The issue here is that I did my investigation with a more recent version of
CPLEX. We made some changes to SAV format starting with CPLEX 12.3 to support
large numbers of nonzeros. While CPLEX 12.3 and later can read in SAV files generated
from earlier versions of CPLEX, the reverse is not true.
So, if you have access to 12.3 or later, use that. If not, let me know, and I will generate the corresponding SAV file that will work with 12.2.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Ed, I do not have the version of 12.3. I really appreciate if you could export a 12.2 version for me. Many thanks.

I did a little more investigate after that. It seems that if I remove some of the terms from the objective functions (the ones with coefficients of 10). There would be no singular basis encountered. But the range of coefficients is just from 10 to 1000, which is quite normal...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> jimzhang wrote:
> Hi Ed, I do not have the version of 12.3. I really appreciate if you could export a 12.2 version for me. Many thanks.

I have attached a suitable gzipped SAV file. Read it in to 12.2, set an iteration
limit of 0, invoke either primopt or dualopt, then examine the solution quality
('dis solution quality'). If you can tell us anything about why this particular
basis might have a high condition number, that would help us a lot. Also, if you
are willing to let us give this file to a couple of academics who are interested
in ill conditioned problems, let me know.

>
> I did a little more investigate after that. It seems that if I remove some of the terms from the objective functions (the ones with coefficients of 10). There would be no singular basis encountered. But the range of coefficients is just from 10 to 1000, which is quite normal...

Agreed. However, while models with wide ranges of coefficients often result in
large basis condition numbers, that is not a necessary condition. Wide ranges
of coefficients tend to introduce more round off error in a finite precision computing
environment, which makes a model more susceptible to problems if it has bases with
high condition numbers. But, you can have ill conditioned models under perfect
precision with benign coefficients as well. For example, here is a matrix that
we encountered in some of our internal testing. It came from the ilaser0 model on
Mittelmann's QP test set. It's a square matrix of the form

1/6    4/6     1/6 1/6     4/6   1/6 1/6   4/6    1/6 1/6    4/6   1/6 ... ... 1/6  4/6  1/6 1/6  4/6 1/6

All the coefficients are reasonable, and the matrix is even upper triangular.
Yet, this will cause trouble for numerous reasons:

1) Just looking at the determinant, we see that it is 6ˆ(-m) where m is the dimension of the matrix. So, this is essentially zero, and the matrix
is essentially singular despite the reasonable diagonal elements. Given that
the condition number can be interpreted as the reciprocal of the distance to
singularity of a matrix, this means that the matrix has a large condition number.

2) If you do the solve Bx_B = b with this matrix for any right hand side b, you can quickly see that it will generate really large values for x_B.

3) If you step through the pivoting operations to calculate the inverse of this basis matrix, you will see that the inverse indeed has large
values. Given that the condition number of a matrix is defined as product of the norms of the matrix and its inverse, this has a huge condition number as the dimension
increases. It's already large for just m = 20.
For this particular basis matrix, one could easily see that the basis matrix was
ill conditioned. I suspect your model is similar in some way, but the nature of the large condition number in the basis in the attached SAV file is not as easy to see as with the example above. I was hoping with your knowledge of the model, you might
be able to either explain the corresponding behavior in your model, or shed some light
on the constraints and variables that you think are involved.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> jimzhang wrote:
> Hi Ed, I do not have the version of 12.3. I really appreciate if you could export a 12.2 version for me. Many thanks.

I have attached a suitable gzipped SAV file. Read it in to 12.2, set an iteration
limit of 0, invoke either primopt or dualopt, then examine the solution quality
('dis solution quality'). If you can tell us anything about why this particular
basis might have a high condition number, that would help us a lot. Also, if you
are willing to let us give this file to a couple of academics who are interested
in ill conditioned problems, let me know.

>
> I did a little more investigate after that. It seems that if I remove some of the terms from the objective functions (the ones with coefficients of 10). There would be no singular basis encountered. But the range of coefficients is just from 10 to 1000, which is quite normal...

Agreed. However, while models with wide ranges of coefficients often result in
large basis condition numbers, that is not a necessary condition. Wide ranges
of coefficients tend to introduce more round off error in a finite precision computing
environment, which makes a model more susceptible to problems if it has bases with
high condition numbers. But, you can have ill conditioned models under perfect
precision with benign coefficients as well. For example, here is a matrix that
we encountered in some of our internal testing. It came from the ilaser0 model on
Mittelmann's QP test set. It's a square matrix of the form

1/6    4/6     1/6 1/6     4/6   1/6 1/6   4/6    1/6 1/6    4/6   1/6 ... ... 1/6  4/6  1/6 1/6  4/6 1/6

All the coefficients are reasonable, and the matrix is even upper triangular.
Yet, this will cause trouble for numerous reasons:

1) Just looking at the determinant, we see that it is 6ˆ(-m) where m is the dimension of the matrix. So, this is essentially zero, and the matrix
is essentially singular despite the reasonable diagonal elements. Given that
the condition number can be interpreted as the reciprocal of the distance to
singularity of a matrix, this means that the matrix has a large condition number.

2) If you do the solve Bx_B = b with this matrix for any right hand side b, you can quickly see that it will generate really large values for x_B.

3) If you step through the pivoting operations to calculate the inverse of this basis matrix, you will see that the inverse indeed has large
values. Given that the condition number of a matrix is defined as product of the norms of the matrix and its inverse, this has a huge condition number as the dimension
increases. It's already large for just m = 20.
For this particular basis matrix, one could easily see that the basis matrix was
ill conditioned. I suspect your model is similar in some way, but the nature of the large condition number in the basis in the attached SAV file is not as easy to see as with the example above. I was hoping with your knowledge of the model, you might
be able to either explain the corresponding behavior in your model, or shed some light
on the constraints and variables that you think are involved.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Something seemed to go wrong with my last post, and the attachment was lost. Here it is.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Ed,
Thanks for your explanations. I did some further investigation and found that there is a pattern of constraint in my model (in the attached file), if I dis-activate it, the model will be solved with no numerical issues and the numerical issue will be raised up if I activate it.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I would like to populate a couple of constraints of a small case for this pattern of constraints on the purpose of illustration, let's say t=1,2,3, {Ln} = {1,2,3}

y_1_1 + y_2_2 + y_3_2 <= 1
y_2_1 + y_1_2 + y_3_2 <= 1
y_3_1 + y_1_2 + y_2_2 <= 1
y_1_2 + y_2_3 + y_3_3 <= 1
y_2_2 + y_1_3 + y_3_3 <= 1
y_3_2 + y_1_3 + y_2_3 <= 1

The coefficient matrix would be (if I am correct)

1,0,0,1,1,0,0,0,0
0,1,0,1,0,1,0,0,0
0,0,1,1,1,1,0,0,0
0,0,0,1,0,0,0,1,1
0,0,0,0,1,0,1,0,1
0,0,0,0,0,1,1,1,0

But I am not sure what the internal coefficient matrix in CPLEX looks like (after adding slack variables, and presolving?) Hope it helpful. Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I did see some of the y variables taking ridiculously large values (either positive or negative) in the file you provided, so is possible that some of the y variables happening to be in the basis and the basis impacted by the pattern of constraints I showed in the last thread has some determinant close to 0, as a result, they are taking ridiculous values? Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

A little more observations:
If I reformulate the pattern of constraints in the following way

y_1_1 + y_2_2 <= 1
y_1_1 + y_3_2 <= 1
y_2_1 + y_1_2 <= 1
y_2_1 + y_3_2 <= 1
y_3_1 + y_1_2 <= 1
y_3_1 + y_2_2 <= 1
y_1_2 + y_2_3 <= 1
y_1_2 + y_3_3 <= 1
y_2_2 + y_1_3 <= 1
y_2_2 + y_3_3 <= 1
y_3_2 + y_1_3 <= 1
y_3_2 + y_2_3 <= 1

There would be no numerical issues so far.

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I also have another pattern of constraints which should be relevant to this issue

Relevant formulations

y_1_1 + y_2_1 + y_3_1 <= 1
y_1_2 + y_2_2 + y_3_2 <= 1
y_1_3 + y_2_3 + y_3_3 <= 1

Actually, I found by the first formulation I provided previously could satisfy these relevant formulations automatically. But I still include it in the model file. Would CPLEX remove this relevant formulation in the pre-solving? if not, would this be an issue?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> EdKlotz wrote:
> > jimzhang wrote:
> > Hi Ed,
> >
> > I tried to read the 17459.sav, however, CPLEX gave me this error message
> >

> > CPLEX> read C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cplex\bin\x86_w > > in32\17459.sav > > CPLEX Error  1560: File 
'C:\cc_view\yd_tools\orapps\Tools\ILOG\Cplex\12.2.0.2\cp > > lex\bin\x86_win32\17459.sav
' is not a SAV file. > >

> >
> > Have you any idea regarding this?
> >
> > Thanks.
>
> Jim,
> The issue here is that I did my investigation with a more recent version of
> CPLEX. We made some changes to SAV format starting with CPLEX 12.3 to support
> large numbers of nonzeros. While CPLEX 12.3 and later can read in SAV files generated
> from earlier versions of CPLEX, the reverse is not true.
> So, if you have access to 12.3 or later, use that. If not, let me know, and I will generate the corresponding SAV file that will work with 12.2.
Jim, if you have any info regarding the subset of constraints and variables that create the large condition numbers, let us know. Otherwise, if we can keep the 17459.sav.gz file (and also the original model) and add it to our R&D test set, let us know; that might help us add some future features to CPLEX that would provide users more info on any ill conditioning in their models.

Ed
#CPLEXOptimizers
#DecisionOptimization