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/

;parameterm(i); m(i)=ord(i);parametern(j); n(j)=ord(j);

parameterb(j);

b(j) =card(i)*(2+sin(n(j)+pi/n(j)));

positivevariablex(i);variablez;

equationsobj,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);

modelmlp /all/;

z.up=1e15;solvemlp maximizing z using lp;displayx.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.