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 <[email protected]> > An: xypron <[email protected]> > CC: [email protected] > 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. > > m...@host:~/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 _______________________________________________ Bug-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/bug-glpk
