Debug unbounded models

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

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

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

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

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

For M = N = 256, the resulting (extended-precision) maximum
is
                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:

 

set
  i /i1*i256/
  j /j1*j256/
;
parameter m(i); m(i)=ord(i);
parameter n(j); n(j)=ord(j);

parameter b(j);
b(j) = card(i)*(2+sin(n(j)+pi/n(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));
e(j)..  sum(i, sin(m(i)+pi/(n(j)+m(i)))*x(i)) =l= b(j);

model mlp /all/;
z.up=1e15;
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: http://www.wolframalpha.com/input/?i=plot+sin(25%2Bpi/(25%2Bn))+for+n%3D1+to+256.

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

Notes:

• 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.