Monday, November 23, 2009

Debug unbounded models

To test a high precision linear optimization solver,
the following problem has been presented:

    Maximize: f(X) =     Σ [2+sin(m+Pi/m)]Xm

    Constraints: b(n) = M[2+sin(n+Pi/n)]  ;  n = 1,2,..,N

    Cost Matrix:     Σ sin[m+Pi/(m+n)]Xm  <=  b(n)

    Xm  >= 0 ,   M <= N ,  Pi = 3.14...

For M = N = 256, the resulting (extended-precision) maximum
                f(X) = 0.3711087372584210920E+10

Using an AMD Athlon 64 CPU with a clock rate of 2600 MHz,
the calculation time - including extended precision data input -
is 3.0 sec.

Could someone verify this result?

You may need to do more debugging. The GAMS model with any LP solvers shows unbounded. A good way to debug is to add a bound on the objective variable so we can look at a solution:


parameter m(i); m(i)=ord(i);
parameter n(j); n(j)=ord(j);

parameter b(j);
b(j) =

positive variable x(i);
variable z;

equations obj,e(j);

obj.. z =e=
sum(i, (2+sin(m(i)+pi/m(i)))*x(i));
sum(i, sin(m(i)+pi/(n(j)+m(i)))*x(i)) =l= b(j);

model mlp /all/;
solve mlp maximizing z using lp;
display x.l;

This can show:

----     22 VARIABLE x.L 

i25 5.01776E+14

(other solvers may give a different solution). All other elements are zero. Indeed for this x(25) we have an objective coefficient greater than zero: 2 + sin(x) is always possible. The coefficients for x(25) for the constraints are all negative. This can be seen from:


You can verify by clicking on:

So indeed when we make x(25) larger the objective will improve while the constraints do not limit this move.


  • A standard text book full-tableau lp solver using extended precision will still be numerically unstable.
  • Gurobi has a “quad” option to use extended precision.

No comments:

Post a Comment