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);
b(j) = card(i)*(2+sin(n(j)+pi/n(j)));
positive variable x(i);
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/;
solve mlp maximizing z using lp;
This can show:
---- 22 VARIABLE x.L
(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.
- 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.