Arbitrary precision linear programming

[Mike]

I'd like to be able to do linear programming to arbitrary precision.  The documentation that I've found claims that both the glpk  and PPL solvers should do this, but I haven't been able to get either to work.

As an example, the following code prints c to high precision, but the solutions only to 12 digits.  Where should I look for guidance?
Note: this seeks to maximize x+y given that 3x<=1 and 3y<=1, so the solution is (1/3, 1/3)

Mike M

R=RealField(100)
c=Matrix(R, 2, 1, [-1, -1])
G=Matrix(R, 2, 2, [3, 0, 0, 3])
h=Matrix(R, 2, 1, [1, 1])
print c  # To check the precision being used by "print"
print

sol=linear_program(c,G,h)
print sol['x']
sol=linear_program(c,G,h, solver='glpk')
print sol['x']
sol=linear_program(c,G,h, solver='PPL')
print sol['x']

[slelievre]

This reminds me of a recent discussion about precision
and number of correct digits through a calculation:

https://groups.google.com/d/topic/sage-devel/ypcOxPlv__s/discussion

[Andrey Novoseltsev]

My "straightforward" simplex method for teaching can handle this one correctly:

http://sagecell.sagemath.org/?z=eJxljUGLwjAQhe-F_oeHe0kgLa2ee60XhVL3JoukSdwOGxNJIui_31hkYRHeDLx58_HGbjTS9mSsZm3T8LJQ3V6mQHc2CqwFWoFjlVfVfuVw-z_MOm4EmkWb58P8TudZ2Gsgl6CAD3x6qNmoH6TZ4BqMokjeYTLkvnGLRmN6YLUAqxdYFmUxoMNuGIKfrLkcknRaBt37cGFbgbm2FBPjAqxS_GX-aof6TE7akyaVcpUMD8brSUZSp-jt7Xlj_BfTdE8X&lang=sage

It can get pretty bad on degenerate problems, however, since it assumes all computations are exact even when they are not.

Andrey

[Volker Braun]

If your problem is over QQ then just use that (PPL supports exact rationals).

[Mike]

This was a "demonstration problem" - my actual application will involve arbitrary-precision reals with lots of constraints.

It appears that PPL not only supports rationals, but insists on them.  It seems to set the base_ring to QQ, as the output from the following code is "Rational Field", but I can find no way to alter base_ring.  Any suggestions on how I might accomplish that?  (For glpk the base_ring is "Real Double Field", and I can't find a way to alter that either.)

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "PPL")
print p.base_ring()

[Dima Pasechnik]

On 2014-10-24, Mike <mill...@gmail.com> wrote:
> This was a "demonstration problem" - my actual application will involve
> arbitrary-precision reals with lots of constraints.
>
> It appears that PPL not only supports rationals, but insists on them. It
> seems to set the base_ring to QQ, as the output from the following code is
> "Rational Field", but I can find no way to alter base_ring. Any

no, you can't do this. PPL is a C++ library that only works with rationals.

Do you mean to say that your "abritrary precision reals" are irrational?
If not, then why don't you just work with rationals?

> suggestions on how I might accomplish that? (For glpk the base_ring is
> "Real Double Field", and I can't find a way to alter that either.)

the arbitrary precision part of glpk does not have a Sage interface,
nobody got around to dig it up.