[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] Wrong dual value using interior method
From: |
glpk xypron |
Subject: |
Re: [Bug-glpk] Wrong dual value using interior method |
Date: |
Tue, 26 Oct 2010 19:08:07 +0200 |
Hello Andrew,
> > maximize obj: x + y;
> > s.t. c1: 0.1 * y + x <= 1.;
> > s.t. c2: 0.1 * y + x >= 1.;
> > s.t. d1: y + 0.1 * x <= 5.;
> > s.t. d2: y + 0.1 * x >= 5.;
> c1: value = 1, dual = 1.340170
> c2: value = 1, dual = -0.431079
> d1: value = 5, dual = 1.326582
> d2: value = 5, dual = -0.417491
Of constraints c1 and c2 only one can be active, same for
d1 and d2.
I expect the dual of the active constraint to be nonzero,
and the dual of the inactive constraint to be zero.
This is what the simplex method returns, but the interior
method does not.
Best regards
Xypron
-------- Original-Nachricht --------
> Datum: Tue, 26 Oct 2010 20:15:44 +0400
> Von: Andrew Makhorin <address@hidden>
> An: xypron <address@hidden>
> CC: address@hidden
> Betreff: Re: [Bug-glpk] Wrong dual value using interior method
> On Tue, 2010-10-26 at 06:23 -0700, xypron wrote:
> > The interior solver outputs incorrect dual values
> > for a feasable solution:
> >
> > var x;
> > var y;
> > maximize obj: x + y;
> > s.t. c1: 0.1 * y + x <= 1.;
> > s.t. c2: 0.1 * y + x >= 1.;
> > s.t. d1: y + 0.1 * x <= 5.;
> > s.t. d2: y + 0.1 * x >= 5.;
> > solve;
> > printf "c1: value = %d, dual = %f\n", c1.val, c1.dual;
> > printf "c2: value = %d, dual = %f\n", c2.val, c2.dual;
> > printf "d1: value = %d, dual = %f\n", d1.val, d1.dual;
> > printf "d2: value = %d, dual = %f\n", d2.val, d2.dual;
> > end;
> >
> > ./glpsol --interior -m test.mod
> > outputs
> > c1: value = 1, dual = -0.432591
> > c2: value = 1, dual = 1.341682
> > d1: value = 5, dual = -0.447088
> > d2: value = 5, dual = 1.356179
> >
>
> Hi Xypron,
>
> I cannot reproduce the error. I solved your instance using glpsol 4.44
> and found nothing incorrect.
>
> address@hidden:~/Desktop/glpk-4.44/examples$ ./glpsol -m test --interior -o
> test.lst
> GLPSOL: GLPK LP/MIP Solver, v4.44
> Parameter(s) specified in the command line:
> -m test --interior -o test.lst
> Reading model section from test...
> 13 lines were read
> Generating obj...
> Generating c1...
> Generating c2...
> Generating d1...
> Generating d2...
> Model has been successfully generated
> Scaling...
> A: min|aij| = 1.000e-01 max|aij| = 1.000e+00 ratio = 1.000e+01
> Problem data seem to be well scaled
> Original LP has 5 row(s), 2 column(s), and 10 non-zero(s)
> Working LP has 4 row(s), 8 column(s), and 20 non-zero(s)
> Matrix A has 20 non-zeros
> Matrix S = A*A' has 10 non-zeros (upper triangle)
> Approximate minimum degree ordering (AMD)...
> Computing Cholesky factorization S = L*L'...
> Matrix L has 10 non-zeros
> Guessing initial point...
> Optimization begins...
> 0: obj = -4.520547945e+00; rpi = 1.1e+00; rdi = 8.0e-01; gap =
> 5.0e-17
> 1: obj = -5.598478814e+00; rpi = 1.5e-01; rdi = 9.7e-02; gap =
> 3.7e-02
> 2: obj = -5.468598344e+00; rpi = 1.5e-02; rdi = 9.8e-03; gap =
> 3.7e-03
> 3: obj = -5.455950382e+00; rpi = 1.5e-03; rdi = 9.8e-04; gap =
> 3.7e-04
> 4: obj = -5.454685947e+00; rpi = 1.5e-04; rdi = 9.8e-05; gap =
> 3.7e-05
> 5: obj = -5.454559504e+00; rpi = 1.5e-05; rdi = 9.8e-06; gap =
> 3.7e-06
> 6: obj = -5.454546859e+00; rpi = 1.5e-06; rdi = 9.8e-07; gap =
> 3.7e-07
> 7: obj = -5.454545595e+00; rpi = 1.5e-07; rdi = 9.8e-08; gap =
> 3.7e-08
> 8: obj = -5.454545469e+00; rpi = 1.5e-08; rdi = 9.8e-09; gap =
> 3.7e-09
> 9: obj = -5.454545456e+00; rpi = 1.5e-09; rdi = 9.8e-10; gap =
> 3.7e-10
> OPTIMAL SOLUTION FOUND
> Time used: 0.0 secs
> Memory used: 0.1 Mb (96321 bytes)
> c1: value = 1, dual = 1.340170
> c2: value = 1, dual = -0.431079
> d1: value = 5, dual = 1.326582
> d2: value = 5, dual = -0.417491
> Model has been successfully processed
> Writing interior-point solution to `test.lst'...
>
> Problem: test
> Rows: 5
> Columns: 2
> Non-zeros: 10
> Status: OPTIMAL
> Objective: obj = 5.454545456 (MAXimum)
>
> No. Row name Activity Lower bound Upper bound
> Marginal
> ------ ------------ ------------- ------------- -------------
> -------------
> 1 obj 5.45455
> < eps
> 2 c1 1 1
> 1.34017
> 3 c2 1 1
> -0.431079
> 4 d1 5 5
> 1.32658
> 5 d2 5 5
> -0.417491
>
> No. Column name Activity Lower bound Upper bound
> Marginal
> ------ ------------ ------------- ------------- -------------
> -------------
> 1 x 0.505051
> < eps
> 2 y 4.94949
> < eps
>
> Karush-Kuhn-Tucker optimality conditions:
>
> KKT.PE: max.abs.err = 2.69e-16 on row 4
> max.rel.err = 2.45e-17 on row 4
> High quality
>
> KKT.PB: max.abs.err = 7.80e-10 on row 2
> max.rel.err = 3.90e-10 on row 2
> High quality
>
> KKT.DE: max.abs.err = 0.00e+00 on column 0
> max.rel.err = 0.00e+00 on column 0
> High quality
>
> KKT.DB: max.abs.err = 2.02e-10 on column 2
> max.rel.err = 2.02e-10 on column 2
> High quality
>
> End of output
>
>
> Andrew Makhorin
>
--
Neu: GMX De-Mail - Einfach wie E-Mail, sicher wie ein Brief!
Jetzt De-Mail-Adresse reservieren: http://portal.gmx.net/de/go/demail