High Precision Linear Optimization Solver
Dan
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?
Thanks,
D. Baruth
x86(at)iging(dot)com
Dan
"Ó" below supposed to be "Sigma" = Sum
Dan
> 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)
erwin
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
er...@amsterdamoptimization.com
http://amsterdamoptimization.com
----------------------------------------------------------------
On Nov 17, 7:47 pm, Dan <goo...@iging.com> wrote:
> 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)
Dan
> No that is incorrect. The problem is unbounded.
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
> ----------------------------------------------------------------
>
> On Nov 17, 7:47 pm, Dan <goo...@iging.com> wrote:
>
> > 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?
>
> > Thanks,
>
> > D. Baruth
> > x86(at)iging(dot)com
What part is unbounded? Please explain.
erwin
> What part is unbounded? Please explain.
I don't understand what you are asking here. May be "any part" is the
correct answer.
I.e. I think there is an unbounded ray: keep all x(i)=0 except x(25).
Now consider:
sin[25+Pi/(25+n)]
This is negative for all n:
http://www.wolframalpha.com/input/?i=plot+sin(25%2Bpi/(25%2Bn))+for+n%3D1+to+256
so the constraint is non-binding. The obj coeff is > 0 so we can
increase x(25) as
much as we want. ==> unbounded.
Notes:
1. A text book tableaux implementation using extended precision still
does not
give you a high-precision solver.
2. There is already a real LP solver that has extended (quad)
precision:
http://www.gurobi.com/html/doc/refman/node378.html#sec:Parameters
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
er...@amsterdamoptimization.com
http://amsterdamoptimization.com
----------------------------------------------------------------
Dan
My solver recognizes this type of problem. Setting the all-negative
variables to zero solves the problem, however.
My solver works with an internal 256 bit (mantissa) precision, using
virtual floating point registers.
(See http://www.iging.com/transcendental/VFPR.htm)
I would very much appreciate if you could verify the following
cases...
M = N = 4 ==> f(X) = 0.109635422375115572E+2 [0.6 msec]
M = N = 16 ==> f(X) = 0.191393769216501217E+13 [0.024 sec]
Thanks,
Dan
x86(at)iging(.)com
On Nov 21, 11:28 pm, erwin <erwin.kalvela...@gmail.com> wrote:
> > What part is unbounded? Please explain.
>
> I don't understand what you are asking here. May be "any part" is the
> correct answer.
> I.e. I think there is an unbounded ray: keep all x(i)=0 except x(25).
> Now consider:
>
> sin[25+Pi/(25+n)]
>
> This is negative for all n:
>
> http://www.wolframalpha.com/input/?i=plot+sin(25%2Bpi/(25%2Bn))+for+n...
>
> so the constraint is non-binding. The obj coeff is > 0 so we can
> increase x(25) as
> much as we want. ==> unbounded.
>
> Notes:
> 1. A text book tableaux implementation using extended precision still
> does not
> give you a high-precision solver.
> 2. There is already a real LP solver that has extended (quad)
> precision:
> http://www.gurobi.com/html/doc/refman/node378.html#sec:Parameters
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
ashutosh mahajan
> Thank you for the remarks.
>
> My solver recognizes this type of problem. Setting the all-negative
> variables to zero solves the problem, however.
>
> My solver works with an internal 256 bit (mantissa) precision, using
> virtual floating point registers.
> (See http://www.iging.com/transcendental/VFPR.htm)
>
> I would very much appreciate if you could verify the following
> cases...
>
> M = N = 4 ==> f(X) = 0.109635422375115572E+2 [0.6 msec]
> M = N = 16 ==> f(X) = 0.191393769216501217E+13 [0.024 sec]
>
> Thanks,
>
> Dan
> x86(at)iging(.)com
QSopt_ex claims is a solver developed by Espinoza et al, to solve LPs
exactly when the inputs are rational. Might be helpful for your case.
http://www2.isye.gatech.edu/~wcook/qsopt/ex/
you can try it without downloading or compiling on the NEOS webpage:
http://neos.mcs.anl.gov/neos/solvers/index.html