bug-glpk
[Top][All Lists]
Advanced

[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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]