xypron, The example is a constrained, overdetermined L1 regression of a line, but it doesn't converge to the correct values for mc & m000_000. Instead it terminates w/ mc=0 and m000_000 = 1.42372e+09 and a large residual error. It should converge to mc = -2.5e4 & m000_000 = 1.8e9.
I get the same result if I don't use exact arithmetic or use the interior point method. I encounter this behavior in a few percent of ~1300 runs. Most of the time it works beautifully. The actual jobs are moderately large, so I thought for a while I had an error in generating the CPLEX file. Several earlier attempts to formulate a small example resulted in problems that were solved correctly. thanks, Reg --- On Wed, 9/1/10, Xypron <[email protected]> wrote: > From: Xypron <[email protected]> > Subject: Re: [Help-glpk] Bug or confused user? > To: "Reginald Beardsley" <[email protected]> > Cc: [email protected] > Date: Wednesday, September 1, 2010, 1:37 PM > Hello Reginald, > > --exact causes the simplex solver to use exact math. > The tests for the "Karush-Kuhn-Tucker optimality > conditions" in > glpapi11.c use double precision. > > Please, point out where you see an error in the output of > your example. > > Best regards > > Xypron > > > > Reginald Beardsley wrote: > > I'm trying to solve a basis pursuit using > glpsol. Most of the time it works fine, but a few > cases fail. I've been able to reduce a failure case > down to the short example that follows. > > > > Comments or advice? > > > > Thanks, > > Reg > > > > > > The details: > > > > I'm using GLPSOL: GLPK LP/MIP Solver, v4.44 w/ > GMP V 4.3.2 on a Solaris 10 x86 system. > > > > The example attempts to solve for the multiplicative > and > > additive constants seen here. The input is > exact, so I'd expect the error to be zero. NB the example is > constructed from a manual approximation to real data and > reproduces the issue seen w/ real data. > > > > m000_000 = 1.8e9 > > mc = -2.5e4 > > > > 1.761766315436816104e-05 * 1.8e9 - 2.5e4 = 6711.79 > > 3.931749670328427322e-05 * 1.8e9 - 2.5e4 = 45771.5 > > 5.452595896563653798e-05 * 1.8e9 - 2.5e4 = 73146.7 > > 6.644022638020372074e-05 * 1.8e9 - 2.5e4 = 94592.4 > > 7.594246564290120299e-05 * 1.8e9 - 2.5e4 = 111696 > > > > My input file in CPLEX format is: > > > > minimize > > z : + a000 + a001 > + a002 + a003 + a004 > > subject to > > mc + > 1.761766315436816104e-05 m000_000 + x000 - a000 > = 6711.79 > > > > mc + > 3.931749670328427322e-05 m000_000 + x001 - a001 > = 45771.5 > > > > mc + > 5.452595896563653798e-05 m000_000 + x002 - a002 > = 73146.7 > > > > mc + > 6.644022638020372074e-05 m000_000 + x003 - a003 > = 94592.4 > > > > mc + > 7.594246564290120299e-05 m000_000 + x004 - a004 > = 111696 > > > > mc + > 1.761766315436816104e-05 m000_000 - y000 + a000 > = 6711.79 > > > > mc + > 3.931749670328427322e-05 m000_000 - y001 + a001 > = 45771.5 > > > > mc + > 5.452595896563653798e-05 m000_000 - y002 + a002 > = 73146.7 > > > > mc + > 6.644022638020372074e-05 m000_000 - y003 + a003 > = 94592.4 > > > > mc + > 7.594246564290120299e-05 m000_000 - y004 + a004 > = 111696 > > > > > > bounds > > > > 0.0<= m000_000 > > > > x000>= 0.0 > > x001>= 0.0 > > x002>= 0.0 > > x003>= 0.0 > > x004>= 0.0 > > > > y000>= 0.0 > > y001>= 0.0 > > y002>= 0.0 > > y003>= 0.0 > > y004>= 0.0 > > > > a000>= 0.0 > > a001>= 0.0 > > a002>= 0.0 > > a003>= 0.0 > > a004>= 0.0 > > > > end > > > > I'm running glpsol w/: > > > > glpsol --exact --lp in -o out > > > > Which produces: > > > > Problem: > > Rows: 10 > > Columns: 17 > > Non-zeros: 40 > > Status: OPTIMAL > > Objective: z = 36634.69154 (MINimum) > > > > No. Row > name St Activity > Lower bound Upper > bound Marginal > > ------ ------------ -- ------------- ------------- > ------------- ------------- > > 1 r.4 > NS > 6711.79 > 6711.79 > = > -1 > > 2 r.6 > NS > 45771.5 > 45771.5 > = > -1 > > 3 r.8 > NS > 73146.7 > 73146.7 > = > -1 > > 4 r.10 > NS > 94592.4 > 94592.4 > = -0.232702 > > 5 r.12 > NS > 111696 111696 > =< eps > > 6 r.15 > NS > 6711.79 > 6711.79 > =< eps > > 7 r.17 > NS > 45771.5 > 45771.5 > =< eps > > 8 r.19 > NS > 73146.7 > 73146.7 > =< eps > > 9 r.21 > NS > 94592.4 > 94592.4 > = 0.767298 > > 10 r.23 > NS 111696 > 111696 > = > 1 > > > > No. Column name > St Activity Lower > bound Upper bound Marginal > > ------ ------------ -- ------------- ------------- > ------------- ------------- > > 1 a000 > B > 18370.9 > 0 > > 2 a001 > B > 10205.7 > 0 > > 3 a002 > B > 4483.1 > 0 > > 4 a003 > B > 0 > 0 > > 5 a004 > B > 3575.05 > 0 > > 6 mc > NL > 0 > 0 > 1.4654 > > 7 m000_000 > B 1.42372e+09 > 0 > > 8 x000 > NL > 0 > 0 > > 1 > > 9 x001 > NL > 0 > 0 > > 1 > > 10 x002 > NL > 0 > 0 > > 1 > > 11 x003 > NL > 0 > 0 > 0.232702 > > 12 x004 > B 7150.11 > 0 > > 13 y000 > B 36741.7 > 0 > > 14 y001 > B 20411.4 > 0 > > 15 y002 > B > 8966.2 > 0 > > 16 y003 > NL > 0 > 0 > 0.767298 > > 17 y004 > NL > 0 > 0 > > 1 > > > > Karush-Kuhn-Tucker optimality conditions: > > > > KKT.PE: max.abs.err = 9.85e-06 on row 4 > > max.rel.err = > 5.20e-11 on row 4 > > High quality > > > > KKT.PB: max.abs.err = 5.39e-06 on row 2 > > max.rel.err = > 1.18e-10 on row 2 > > High quality > > > > KKT.DE: max.abs.err = 3.31e-15 on column 7 > > max.rel.err = > 3.31e-15 on column 7 > > High quality > > > > KKT.DB: max.abs.err = 0.00e+00 on row 0 > > max.rel.err = > 0.00e+00 on row 0 > > High quality > > > > End of output > > > > > > > > > > > > _______________________________________________ > > Help-glpk mailing list > > [email protected] > > http://lists.gnu.org/mailman/listinfo/help-glpk > > > > > > _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
