[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Modifying the column statuses to make a validLPbasis aft
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Modifying the column statuses to make a validLPbasis after some column bounds have been modified. |
Date: |
Mon, 02 May 2011 17:03:59 +0400 |
> 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