[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: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] Wrong dual value using interior method |
Date: |
Tue, 26 Oct 2010 20:15:44 +0400 |
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