[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Bug or confused user?
|
From: |
Reginald Beardsley |
|
Subject: |
Re: [Help-glpk] Bug or confused user? |
|
Date: |
Wed, 1 Sep 2010 13:22:48 -0700 (PDT) |
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 <address@hidden> wrote:
> From: Xypron <address@hidden>
> Subject: Re: [Help-glpk] Bug or confused user?
> To: "Reginald Beardsley" <address@hidden>
> Cc: address@hidden
> 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
> > address@hidden
> > http://lists.gnu.org/mailman/listinfo/help-glpk
> >
> >
>
>