On Fri, 18 Mar 2011 13:16:24 +0300 Andrew Makhorin <[email protected]> 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 [email protected] (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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
