Re: [Bug-glpk] Wrong dual value using interior method

[Andrew Makhorin]

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