Re: [Help-glpk] Fixing Numerical Instability Problems

[GLENN RHOADS]

On Fri, 18 Mar 2011 13:16:24 +0300
 Andrew Makhorin <address@hidden> wrote:
> Hello,
> 
> > I have an application that solves tens of million of tiny LPs
> coming
> > from matrix games.  On checking the kkt optimality conditions,
> there
> > are a dozen cases where both the primal and dual solutions are
> > incorrect, and about one hundred cases with low quality dual or
> primal
> > feasibility.
> 
> Could you please output (with glp_write_prob) two or three of your
> instances, for which solution reported is non-accurate or wrong, and
> post them to address@hidden (i.e. to me)? Thanks.

It may take a little while to get the "glp_write_prob" output because I
don't access to the computer resources needed to re-run these examples
(they were run by a colleague on a parallel research cluster) but I do
have a printout the LP coefficient matrices that caused a problem.  I'm
including a number of these instances.  Note that I'm not printing out
the last row, the last column, nor the r.h.s. because they are the same
for every LP of a given size.  The last column contains a -1.0 in every
entry except the lower-right corner entry which is a zero.  The last
constraint row contains a 1.0 in every entry except the lower-right
corner which again is a zero.  Every constraint row except the last is
<= 0 (in glpk form, you add an artificial variable and have the
constraint = 0).  The last constraint is = 1.0.  All of the output was
generated by the application program except for two lines that were
output by glpk saying that it was unable to factorize the basis matrix
and that basis recovery hadn't been implemented yet.  The fifth and
seventh LPs listed below were the only two in which there wasn't two or
more identical constraint rows.  Sorry about the mail facility word
wrapping the longer constraint rows; there doesn't seem to be a way to
avoid it.  If this information isn't sufficient and you really need to
see the output from glp_write_prob, let me know and I'll get that to
you when I can.  Thanks very much for your time.

-- Glenn C. Rhoads



The following LP matrix generated LOW quality dual feasibility.
18.1983   19.0527   18.4156   7.65079   0.674111   0.674111   
17.3157   18.1983   19.1983   9.07155   2.1926   2.1926   
20.1718   19.0515   17.7823   12.8041   6.09559   6.09559   
20.1718   19.0515   17.7823   12.8041   6.09559   6.09559   
20.1718   19.0515   17.7823   12.8041   6.09559   6.09559   
24.9017   24.4838   23.5043   10.8041   12.8041   12.8041   

The following LP matrix generated LOW quality primal feasibility.
-13.0756   -13.0756   -13.0756   -13.0756   -13.0756   -25.3243
-28.4666   
-16.0756   -13.0756   -13.0756   -13.0756   -13.0756   -25.3243
  -28.4666   
-11.9968   -12.1313   -12.1313   -12.1313   -12.1313   -16.3339
  -19.2927   
-11.9968   -12.1313   -12.1313   -12.1313   -12.1313   -16.3339
  -19.2927   
-11.9968   -12.1313   -12.1313   -12.1313   -12.1313   -16.3339
  -19.2927   
-9.57078   -9.67406   -9.67406   -9.67406   -9.67406   -19.3339
  -16.3339   
-0.0178652   -0.143781   -0.143781   -0.143781   -0.143781   -14.7827
  -19.7673   

Error: unable to factorize the basis matrix (1)
Sorry, basis recovery procedure not implemented yet
ERROR: Solving the following LP matrix generated error code 5
38.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
33.5624   30.1202   37.1202   42.2639   40.3855   40.3855   40.3855   
35.5788   32.6678   31.5907   37.1202   44.1202   44.1202   44.1202   

The following LP matrix generated an INCORRECT primal solution.
The following LP matrix generated an INCORRECT dual solution.
38.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
31.1011   42.8565   41.9829   38.7673   36.5605   36.5605   36.5605   
33.5624   30.1202   37.1202   42.2639   40.3855   40.3855   40.3855   
35.5788   32.6678   31.5907   37.1202   44.1202   44.1202   44.1202   

The following LP matrix generated LOW quality primal feasibility.
23.6872   23.4818   21.7406   19.4947   19.4947   15.5916   8.69889   
11.6872   23.5592   21.8829   19.6681   19.6681   15.7467   8.8391   
-0.0190884   11.6872   22.6361   20.4632   20.4632   16.4913   9.55531
  
0.34237   -0.31279   23.1196   21.0702   21.0702   17.0995   10.1569   
1.647   1.30096   -0.880443   23.1196   23.1196   19.0895   12.0588   
6.89897   6.65038   4.50306   2.06602   2.06602   26.066   19.0474   
11.3489   11.1098   8.97651   6.52667   6.52667   2.06602   26.066   

The following LP matrix generated LOW quality dual feasibility.
-11.3   -2.4491   -2.77708   -3.61255   -4.85965   -5.76187   -6.97009
  -8.24576   
-20.3   -2.36386   -2.69936   -3.53556   -4.77325   -5.6688   -6.88507
  -8.16297   
-19.8068   -20.1023   -11.1023   -2.6794   -3.91354   -4.76241
  -6.01995   -7.30483   
-18.997   -19.2811   -19.6858   -11.1023   -2.88196   -3.6899
  -4.96856   -6.26103   
-17.8449   -18.165   -18.5432   -19.4993   -11.1023   -2.10231
  -3.44927   -4.72717   
-13.9575   -14.2871   -14.6649   -15.6284   -17.0508   -17.9623
  -8.96231   0.0376903   
-8.24775   -8.6584   -9.05048   -10.0549   -11.5635   -12.6271
  -14.0438   -15.6672   
-8.24775   -8.6584   -9.05048   -10.0549   -11.5635   -12.6271
  -14.0438   -15.6672   

The following LP matrix generated LOW quality dual feasibility.
-18.3728   -9.37281   -0.591873   -0.885409   -2.11329   -5.59066
  -7.2957   -11.7384   
-18.1729   -18.2505   -9.37281   -0.372811   -1.75454   -5.24582
  -6.92904   -11.3923   
-16.9808   -17.0634   -17.5889   -17.9793   -0.50547   -3.90611
  -5.52936   -9.99025   
-16.4482   -16.5334   -17.0417   -17.4098   -9.50547   -3.25935
  -4.85697   -9.34296   
-15.7136   -15.8079   -16.3134   -16.6971   -18.5055   -2.49109
  -3.97814   -8.48106   
-14.6288   -14.7008   -15.1538   -15.5206   -17.1428   -11.4911
  -2.49109   -7.13329   
-9.80612   -9.86195   -10.2317   -10.5746   -12.03   -16.5674
  -18.8276   -0.827566   
-0.830876   -0.890575   -1.32117   -1.7124   -3.24395   -7.70996
  -9.72931   -18.8276   

The following LP matrix generated LOW quality dual feasibility.
-0.422215   -0.465209   -0.600736   -0.997069   -1.4869   -3.9756
  -6.89235   -22.0928   
-14.4119   -7.41193   -0.411934   -0.875107   -1.38651   -3.92019
  -6.86417   -22.0701   
-13.5146   -13.6143   -13.7708   -6.77078   0.229221   -2.66902
  -5.76249   -20.8887   
-11.2404   -11.3682   -11.6458   -12.1707   -12.7914   -0.193337
  -3.3626   -18.3207   
-10.0368   -10.1989   -10.4762   -11.0021   -11.6295   -7.19334
  -1.8996   -16.7948   
-6.32622   -6.52881   -6.85515   -7.40658   -8.10133   -12.0135
  -7.19334   -12.5336   
-4.03085   -4.23764   -4.58231   -5.14373   -5.86675   -9.9195
  -14.1933   -10.1082   
-4.03085   -4.23764   -4.58231   -5.14373   -5.86675   -9.9195
  -14.1933   -10.1082   

The following LP matrix generated LOW quality dual feasibility.
-22.3373   -10.3373   1.40248   1.06221   -1.60309   -2.47942
  -3.55648   -11.8711   
-22.1106   -22.2047   -10.3373   1.66266   -1.20277   -2.09501
  -3.18285   -11.5676   
-20.7311   -20.8489   -21.4736   -21.9219   0.525873   -0.403925
  -1.45767   -10.0602   
-20.7311   -20.8489   -21.4736   -21.9219   0.525873   -0.403925
  -1.45767   -10.0602   
-18.024   -18.1277   -18.6987   -19.164   -22.429   -10.429   1.57097
  -7.26934   
-13.6481   -13.8115   -14.4948   -15.0208   -18.6309   -19.6693
  -21.0774   -2.91593   
-13.6481   -13.8115   -14.4948   -15.0208   -18.6309   -19.6693
  -21.0774   -2.91593   
-10.2695   -10.3871   -10.9769   -11.4598   -14.7095   -15.6696
  -16.8924   -14.9159