Re: [Help-glpk] Modifying the column statuses to make a validLPbasis after some column bounds have been modified.

[Andrew Makhorin]

> Yes - here is the output below.
> 
> The first call uses the advanced basis then the second uses the basis
> from the previous LP after the problem has been completely erased and
> re-created.
> 
> In the sequence I am erasing the problem then I re-create the problem
> from scratch using all of your row, column and matrix input routines in
> the exactly the same order as I did on the previous call.
> 
> If you would I can send the source code for you to have a better look.
> 
> Jeff
> 
> Scaling...
>  A: min|aij| = 4.547e-013  max|aij| = 1.250e+004  ratio = 2.749e+016
> Constructing initial basis...
> Size of triangular part = 4859
> GLPK Simplex Optimizer, v4.45
> 4859 rows, 10379 columns, 20248 non-zeros
>       0: obj = -6.731724452e+011  infeas = 7.974e+006 (0)
>     500: obj =  1.896863371e+012  infeas = 5.424e+006 (0)
>    1000: obj =  4.612794462e+012  infeas = 1.493e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>    1089: obj =  4.842645635e+012  infeas = 1.263e+006 (0)
>    1500: obj =  5.217739896e+012  infeas = 5.100e+005 (0)
>    2000: obj =  5.573868991e+012  infeas = 3.434e+000 (0)
> *  2057: obj =  5.573881030e+012  infeas = 3.582e-007 (0)
> *  2500: obj =  1.142676788e+012  infeas = 5.911e-006 (0)
> *  3000: obj =  2.377783470e+009  infeas = 7.378e-006 (0)
> *  3500: obj = -1.240573534e+004  infeas = 6.213e-005 (0)
> *  3965: obj = -1.243844952e+004  infeas = 6.243e-005 (0)
> OPTIMAL SOLUTION FOUND
> 
>            6        3029        1350           0
>    30.7972708460954        119221.166034464       0.000000000000000E+000
>   0.000000000000000E+000
> 
> Scaling...
>  A: min|aij| = 2.220e-016  max|aij| = 2.500e+004  ratio = 1.126e+020
> GLPK Simplex Optimizer, v4.45
> 4859 rows, 10379 columns, 19736 non-zeros
> glp_simplex: initial basis is singular
> Constructing initial basis...
> Size of triangular part = 4859
> GLPK Simplex Optimizer, v4.45
> 4859 rows, 10379 columns, 19736 non-zeros
>       0: obj = -1.601555230e+011  infeas = 2.265e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     182: obj = -2.570324242e+010  infeas = 2.119e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     244: obj =  7.724130824e+010  infeas = 2.008e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     250: obj =  7.724132639e+010  infeas = 2.008e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     256: obj =  7.724132453e+010  infeas = 2.008e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     261: obj =  7.724130671e+010  infeas = 2.008e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     270: obj =  7.817161920e+010  infeas = 2.007e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     347: obj =  1.033473724e+011  infeas = 1.980e+006 (0)
> Warning: numerical instability (primal simplex, phase I)
>     384: obj =  1.253287420e+011  infeas = 1.970e+006 (0)
>     500: obj =  8.890733663e+010  infeas = 1.942e+006 (0)
>    1000: obj =  1.951531160e+012  infeas = 7.679e+004 (0)
>    1500: obj =  2.042339927e+012  infeas = 3.092e+004 (0)
> Warning: numerical instability (primal simplex, phase I)
>    1778: obj =  2.105430455e+012  infeas = 6.970e+001 (0)
> *  1858: obj =  2.104354963e+012  infeas = 6.995e-008 (0)
> *  2000: obj =  1.954714476e+012  infeas = 6.996e-008 (0)
> *  2500: obj =  2.367490133e+011  infeas = 7.853e-008 (0)
> *  3000: obj =  5.004399020e+010  infeas = 8.308e-008 (0)
> *  3500: obj = -1.240275155e+004  infeas = 1.265e-009 (0)
> *  3952: obj = -1.243844725e+004  infeas = 4.012e-008 (0)
> OPTIMAL SOLUTION FOUND
> 
> -----Original Message-----
> From: Andrew Makhorin [mailto:address@hidden 
> Sent: Monday, May 02, 2011 7:40 AM
> To: Kelly, Jeff (ON0F)
> Subject: RE: [Help-glpk] Modifying the column statuses to make a
> validLPbasis after some column bounds have been modified.
> 
> > Thanks, I was not including all of the variables or column statuses.
> > 
> > Now I get for some problems a singular basis return code - is there a
> > typical reason that would stand-out why a basis would become singular
> > with only column bound changes?
> > 
> 
> Do you mean that you call glp_simplex, which returns OK, then
> glp_set_col_bnds for one or more columns, and then glp_simplex, which
> reports that the basis is singular? Or there are some other routines
> called in that sequence?
> 
> 
> 

Kelly,

Most likely the error happens because of badly scaling of the
coefficient matrix:

 A: min|aij| = 4.547e-013  max|aij| = 1.250e+004  ratio = 2.749e+016
 A: min|aij| = 2.220e-016  max|aij| = 2.500e+004  ratio = 1.126e+020

If you remove tiny constraint coefficients (say, whose magnitude is less 
than 1e-9) replacing them by exact zeros, the error must disappear.

Or not to use glp_adv_basis at all (currently it does not take into 
account magnitude of constraint coefficients).


Andrew Makhorin