[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] spx_simplex: numerical instability (primal simplex, phas
|
From: |
Andrew Makhorin |
|
Subject: |
Re: [Help-glpk] spx_simplex: numerical instability (primal simplex, phase I) and infinite looping in glpk on large model |
|
Date: |
Wed, 4 Apr 2007 02:19:54 +0400 |
> I am attaching 3 versions of the same model that differe in their
> limits on two rows. KnockoutRow and KnockoutRow_up
>
> All versions of the model display the error:
> spx_simplex: numerical instability (primal simplex, phase I)
This is a warning, not an error. The solver signals you that it
encounters some numeric difficulties.
>
> However the version ec_kn10_kca_mps.txt loops infinitely
>
> Also all column ending in _kcol are intended to be integer (actualy
> binary as their lower limit = 0 and upper limit = 1)).
They are not marked as integer in the mps file.
>
> I am attaching the output as well.
>
> I have tried scaling my objective function (which has a coeffecent of
> 1) by small numbers and scalling my limits as well but neither approach
> has helped remove the instabilities.
I successfully solved both your model with glpsol using default
settings. (The second model has an invalid rhs value 'none', which I
replaced by 0.0; check that.) In both cases the kkt conditions show
that the solution is optimal.
lpx_read_freemps: reading problem data from `ec_kn0_kc0_mps'...
lpx_read_freemps: problem EcoliOptTest
lpx_read_freemps: 5466 rows, 5463 columns, 25579 non-zeros
lpx_read_freemps: 47442 records were read
lpx_simplex: original LP has 5466 rows, 5463 columns, 25579 non-zeros
lpx_simplex: presolved LP has 2421 rows, 4266 columns, 19699 non-zeros
lpx_adv_basis: size of triangular part = 2404
0: objval = 1.000000000e+02 infeas = 1.000000000e+00 (16)
200: objval = 1.000000000e+02 infeas = 3.792186352e-01 (16)
400: objval = 1.000000000e+02 infeas = 1.048764377e-01 (16)
600: objval = 0.000000000e+00 infeas = 2.797813788e-02 (16)
800: objval = 0.000000000e+00 infeas = 4.405286874e-03 (15)
1000: objval = 0.000000000e+00 infeas = 1.785013450e-03 (6)
1200: objval = -1.000000000e+02 infeas = 1.146701135e-03 (2)
1400: objval = -1.000000000e+02 infeas = 4.655608098e-04 (1)
1594: objval = -1.000000000e+02 infeas = 4.654032647e-04 (1)
spx_simplex: numerical instability (primal simplex, phase I)
1594: objval = -1.000000000e+02 infeas = 1.000000000e+00 (1)
1600: objval = -1.000000000e+02 infeas = 9.999982812e-01 (1)
1800: objval = -1.000000000e+02 infeas = 9.999971052e-01 (1)
2000: objval = -1.000000000e+02 infeas = 9.999970810e-01 (1)
2200: objval = -1.000000000e+02 infeas = 9.999970719e-01 (1)
2400: objval = -1.000000000e+02 infeas = 9.999970757e-01 (0)
2441: objval = -1.000000000e+02 infeas = 9.750012871e-01 (0)
spx_simplex: numerical instability (primal simplex, phase I)
2441: objval = -1.000000000e+02 infeas = 1.000000000e+00 (0)
2600: objval = -1.000000000e+02 infeas = 9.999999045e-01 (0)
2800: objval = -1.000000000e+02 infeas = 9.999998799e-01 (0)
3000: objval = -1.000000000e+02 infeas = 1.000000081e+00 (0)
3190: objval = -1.000000000e+02 infeas = 9.706699170e-01 (0)
spx_simplex: numerical instability (primal simplex, phase I)
3190: objval = -1.000000000e+02 infeas = 1.000000000e+00 (0)
3200: objval = -1.000000000e+02 infeas = 9.999999863e-01 (0)
3295: objval = -1.000000000e+02 infeas = 1.000000025e+00 (0)
spx_simplex: numerical instability (primal simplex, phase I)
3295: objval = -1.000000000e+02 infeas = 1.000000000e+00 (0)
3400: objval = -1.000000000e+02 infeas = 9.999999600e-01 (0)
3600: objval = -1.000000000e+02 infeas = 8.335858617e-01 (0)
3800: objval = -3.993314261e+01 infeas = 1.503026623e-01 (0)
4000: objval = -3.993314261e+01 infeas = 1.503012506e-01 (0)
4200: objval = -4.806268921e+01 infeas = 1.184182545e-02 (0)
4400: objval = -4.804668444e+01 infeas = 1.163052677e-02 (0)
4600: objval = -5.702963360e+01 infeas = 6.796432678e-03 (0)
4800: objval = 0.000000000e+00 infeas = 1.192327731e-04 (0)
4921: objval = 0.000000000e+00 infeas = 4.703292913e-10 (0)
* 4921: objval = 0.000000000e+00 infeas = 7.739387887e-08 (0)
* 4947: objval = 7.755530756e-05 infeas = 7.755530781e-05 (0)
spx_simplex: numerical instability (primal simplex, phase II)
4947: objval = 7.755530756e-05 infeas = 1.000000000e+00 (0)
4957: objval = -5.106315371e-11 infeas = 3.269697200e-09 (0)
OPTIMAL SOLUTION FOUND
Time used: 21.0 secs
Memory used: 6.0M
Problem: EcoliOptTest
Rows: 5466
Columns: 5463
Non-zeros: 25579
Status: OPTIMAL
Objective: objective = -5.106315371e-11 (MINimum)
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 2.14e-12 on row 5466
max.rel.err. = 2.14e-12 on row 5466
High quality
KKT.PB: max.abs.err. = 9.26e-13 on row 10
max.rel.err. = 9.26e-13 on row 10
High quality
KKT.DE: max.abs.err. = 1.57e-08 on column 1428
max.rel.err. = 1.57e-08 on column 1428
Medium quality
KKT.DB: max.abs.err. = 1.57e-08 on column 1427
max.rel.err. = 1.57e-08 on column 1427
Medium quality
lpx_read_freemps: reading problem data from `ec_kn10_kca_mps'...
lpx_read_freemps: problem EcoliOptTest
lpx_read_freemps: 10344 rows, 7901 columns, 38988 non-zeros
lpx_read_freemps: 75483 records were read
lpx_simplex: original LP has 10344 rows, 7901 columns, 38988 non-zeros
lpx_simplex: presolved LP has 6563 rows, 6704 columns, 30418 non-zeros
lpx_adv_basis: size of triangular part = 6546
0: objval = 1.000000000e+02 infeas = 1.000000000e+00 (7)
200: objval = 1.000000000e+02 infeas = 9.503194639e-01 (0)
400: objval = 1.000000000e+02 infeas = 8.071842564e-01 (0)
600: objval = 1.000000000e+02 infeas = 6.023741809e-01 (0)
800: objval = 1.000000000e+02 infeas = 4.479975533e-01 (0)
1000: objval = 1.000000000e+02 infeas = 3.277919418e-01 (0)
1200: objval = 1.000000000e+02 infeas = 3.054617729e-01 (0)
1400: objval = 1.000000000e+02 infeas = 2.848318237e-01 (0)
1600: objval = 1.000000000e+02 infeas = 2.547180947e-01 (0)
1800: objval = 1.000000000e+02 infeas = 2.348929496e-01 (0)
2000: objval = 1.000000000e+02 infeas = 7.580034731e-02 (0)
2200: objval = 1.000000000e+02 infeas = 5.380357985e-02 (0)
2400: objval = 1.000000000e+02 infeas = 4.447718346e-02 (0)
2600: objval = 0.000000000e+00 infeas = 2.163165826e-02 (0)
2800: objval = 0.000000000e+00 infeas = 9.206036661e-03 (0)
3000: objval = 0.000000000e+00 infeas = 3.464345263e-03 (0)
3200: objval = 0.000000000e+00 infeas = 6.798636521e-04 (0)
3400: objval = -4.893498452e+01 infeas = 9.245026478e-05 (0)
3599: objval = 0.000000000e+00 infeas = 8.148552804e-05 (0)
spx_simplex: numerical instability (primal simplex, phase I)
3599: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0)
3600: objval = 0.000000000e+00 infeas = 9.999999174e-01 (0)
3800: objval = 0.000000000e+00 infeas = 9.619423534e-01 (0)
4000: objval = 0.000000000e+00 infeas = 9.025200214e-01 (0)
4200: objval = 0.000000000e+00 infeas = 8.354277353e-01 (0)
4400: objval = 0.000000000e+00 infeas = 7.926022119e-01 (0)
4600: objval = 0.000000000e+00 infeas = 7.209118990e-01 (0)
4800: objval = 0.000000000e+00 infeas = 6.976498265e-01 (0)
5000: objval = 0.000000000e+00 infeas = 6.656279088e-01 (0)
5200: objval = 0.000000000e+00 infeas = 6.193804858e-01 (0)
5400: objval = 0.000000000e+00 infeas = 5.866616117e-01 (0)
5600: objval = 0.000000000e+00 infeas = 5.497202270e-01 (0)
5800: objval = 0.000000000e+00 infeas = 5.316316637e-01 (0)
6000: objval = 0.000000000e+00 infeas = 5.161894189e-01 (0)
6200: objval = 0.000000000e+00 infeas = 4.752238619e-01 (0)
6400: objval = 0.000000000e+00 infeas = 4.357406119e-01 (0)
6600: objval = 0.000000000e+00 infeas = 4.144603147e-01 (0)
6800: objval = 0.000000000e+00 infeas = 3.998364926e-01 (0)
7000: objval = 0.000000000e+00 infeas = 3.811679809e-01 (0)
7200: objval = 0.000000000e+00 infeas = 3.620290097e-01 (0)
7400: objval = 0.000000000e+00 infeas = 3.361000416e-01 (0)
7600: objval = 0.000000000e+00 infeas = 3.126001512e-01 (0)
7800: objval = 0.000000000e+00 infeas = 3.011041615e-01 (0)
8000: objval = 0.000000000e+00 infeas = 2.885252849e-01 (0)
8200: objval = 0.000000000e+00 infeas = 2.633898176e-01 (0)
8400: objval = 0.000000000e+00 infeas = 2.383452512e-01 (0)
8600: objval = 0.000000000e+00 infeas = 2.081959007e-01 (0)
8800: objval = 0.000000000e+00 infeas = 1.999851699e-01 (0)
9000: objval = 0.000000000e+00 infeas = 1.807084693e-01 (0)
9200: objval = 0.000000000e+00 infeas = 1.654721578e-01 (0)
9400: objval = 0.000000000e+00 infeas = 1.486520671e-01 (0)
9600: objval = 0.000000000e+00 infeas = 4.413984280e-02 (0)
9800: objval = 0.000000000e+00 infeas = 3.617680713e-02 (0)
10000: objval = 0.000000000e+00 infeas = 2.794131037e-02 (0)
10200: objval = 0.000000000e+00 infeas = 1.414006526e-02 (0)
10389: objval = 0.000000000e+00 infeas = 3.966171074e-15 (0)
* 10389: objval = 0.000000000e+00 infeas = 2.921240889e-13 (0)
* 10400: objval = -7.379339154e+00 infeas = 2.956754640e-13 (0)
* 10564: objval = -1.731682502e+01 infeas = 2.290866331e-13 (0)
OPTIMAL SOLUTION FOUND
Time used: 110.0 secs
Memory used: 10.3M
Problem: EcoliOptTest
Rows: 10344
Columns: 7901
Non-zeros: 38988
Status: OPTIMAL
Objective: objective = -17.31682502 (MINimum)
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 7.73e-12 on row 4441
max.rel.err. = 3.87e-12 on row 4441
High quality
KKT.PB: max.abs.err. = 3.41e-13 on row 129
max.rel.err. = 3.41e-13 on row 129
High quality
KKT.DE: max.abs.err. = 2.58e-14 on column 2577
max.rel.err. = 2.58e-14 on column 2577
High quality
KKT.DB: max.abs.err. = 3.20e-14 on row 2828
max.rel.err. = 3.20e-14 on row 2828
High quality