5
$\begingroup$

So a while back I had asked this question: Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?

And basically the overwhelming consensus was that the best libraries for exact linear programming were:

  1. QSOPT-Exact

  2. GLPK

and there were a few others. So I wanted libraries that are nicely compatible with python3 on a mac os.

I started with QSOPT-Exact, which I installed via the two links below

https://github.com/jonls/qsopt-ex

https://github.com/jonls/python-qsoptex

This library has worked well for me in the past but today it seems like it has a segfault (this might be due to Mac OS) which I raised as an issue here: https://github.com/jonls/python-qsoptex/issues/8

Now the next option was GLPK and I was able get GLPK working with python3 by installing

  1. brew install glpk
  2. python3 -m pip install PuLP

But while GLPK can be called via the exact flag it does not output rationals but rather a floating point representation of the exact result. See here:

enter image description here

And heres the code:

from fractions import Fraction

prob = pulp.LpProblem("sidsproblem", pulp.LpMaximize)

x1 = pulp.LpVariable("x_1",0,1)
x2 = pulp.LpVariable("x_2",0,1)

prob += x1 + x2
prob += (5*x1 + 4*x2 <= 1)
prob += (4*x1 - 11*x2 <= -1)
prob += (x1 <= 0.23)
prob += (x2 <= Fraction(2,9))
prob.writeLP("sidsproblem2.lp")

prob.solve(pulp.GLPK(options=['--exact']))

for v in prob.variables():
    print(v.name, "=", v.varValue)

So clearly GLPK is doing exact arithmetic but the interface which talks to python3 hands python3 a float as opposed to a rational. Which defeats the point on my end.

Which now makes me wonder, what high quality WORKING implementations of exact linear programming libraries exist for python3? It seems like the options are few and limited now and I wanted to know what any of you have successfully used in the past year.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

SCIP has an exact linear solver; it's still in development, but it should be more or less easy to use.

First, install SCIP with the exact solver: https://github.com/leoneifler/exact-SCIP

Then, in PuLP (because you are using it), give the path to this installation of SCIP, plus an option for using the exact solver (exact/exact_enabled): https://coin-or.github.io/pulp/technical/solvers.html#pulp.apis.SCIP

Improve this answer
$\endgroup$
1
  • $\begingroup$ Was not aware of this. Nice reference. $\endgroup$
    – Mark L. Stone
    Commented Apr 10, 2023 at 12:04
1
$\begingroup$

Not sure about high-quality, but here's one I wrote: flexible_lp. It uses two-phase simplex.

It should work well for small/medium problems but isn't optimized for speed. Just published, so happy for any feedback!

Improve this answer
$\endgroup$
0
$\begingroup$

Google OR tools is the other option if you have not explored it. You can model IP or MIP using google or tools, it has very good python interface with good documentation. you can use open source solver like scip, clp, cbc, glop to solve LP - example link

OR tools also gives flexibility to integrate your choice of solver - https://developers.google.com/optimization/lp/lp_advanced

Improve this answer
$\endgroup$
1
  • $\begingroup$ The problem of OR-Tools is that there are not great options for exact solutions. Glop can be quite numerically stable, but it's still not exact. $\endgroup$
    – dourouc05
    Commented Apr 12, 2023 at 22:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.