## Saturday, April 25, 2009

### GLPK: gams vs glpsol

The GAMS version of GLPK seems numerically less stable than the standalone GLPK version (at least for this case). Here is a GAMS model, where we used an option file to not use a final LP to get duals:

 \$ontext     Alphametics, Simple formulation     Erwin Kalvelagen, 1998      G E O R G I A        O R E G O N      V E R M O N T    ---------------    V I R G I N I A \$offtext set i /G,E,O,R,I,A,N,V,M,T/; alias (i,j); abort\$(card(i) <> 10) "set i should have 10 elements"; parameter v(i); v(i) = ord(i)-1; variables      y(i) 'decision variables'      x(i,j) 'auxiliary variables for uniqueness'      z 'dummy objective variable' ; binary variable x; equation      addition 'the actual problem'      ydef(i) 'calculate y'      xrow(i) 'row sums'      xcol(j) 'column sums'      dummy_objective ; addition..               1e6*y('G') + 1e5*y('E') + 1e4*y('O') + 1e3*y('R') + 100*y('G') + 10*y('I') + y('A') +                            1e5*y('O') + 1e4*y('R') + 1e3*y('E') + 100*y('G') + 10*y('O') + y('N') +               1e6*y('V') + 1e5*y('E') + 1e4*y('R') + 1e3*y('M') + 100*y('O') + 10*y('N') + y('T') =e= 1e7*y('V') + 1e6*y('I') + 1e5*y('R') + 1e4*y('G') + 1e3*y('I') + 100*y('N') + 10*y('I') + y('A'); ydef(i).. y(i) =e= sum(j, x(i,j)*v(j)); xrow(i).. sum(j, x(i,j)) =e= 1; xcol(j).. sum(i, x(i,j)) =e= 1; * * bounds on leading digits: they can not be 0 * y.lo('G') = 1; y.lo('V') = 1; dummy_objective.. z =e= sum(i, y(i)); model m /all/; m.optfile=1; solve m using mip minimizing z; option y:0; display y.l; \$onecho > coinglpk.opt solvefinal=0 \$offecho

This gives:

 **** SOLVER STATUS     1 NORMAL COMPLETION         **** MODEL STATUS      8 INTEGER SOLUTION          **** OBJECTIVE VALUE               45.0000 ---- VAR y  decision variables          LOWER          LEVEL          UPPER         MARGINAL G         1.0000         1.0000        +INF            EPS     NOPT E        -INF             .            +INF            EPS     NOPT O        -INF             .            +INF            EPS     NOPT R        -INF             .            +INF            EPS     NOPT I        -INF             .            +INF            EPS     NOPT A        -INF             .            +INF            EPS     NOPT N        -INF             .            +INF            EPS     NOPT V         1.0000         1.0000        +INF            EPS     NOPT M        -INF             .            +INF            EPS     NOPT T        -INF             .            +INF            EPS     NOPT

This solution is not correct. I suspect the NOPTS are just the result of a bug in GAMS link. As explained in a previous posting this behavior may be because of scaling. The log file looks like: