5

I have an LP with integer constraints that I want to solve in exact arithmetic, using Python. In fact, I only need a feasible point.

Edit: "Exact arithmetic" here means rational numbers, of unbounded enumerator and denominator.

Previous attempts:

Speed is only a moderate issue. My larger instances have about 500 variables with box-constraints and 40 equalities, but the numbers involved might be large.

sophros
  • 14,672
  • 11
  • 46
  • 75
Hennich
  • 682
  • 3
  • 18
  • 1
    When you say exact arithmetic, do you mean your variables should be integers? Rational numbers? – Matthew Woodruff Dec 06 '18 at 20:21
  • 1
    @MatthewWoodruff rational numbers – Hennich Dec 06 '18 at 20:24
  • 1
    Interesting. You could certainly write a simplex solver that does this, especially for problems this small, but I'm not aware of any LP solver that doesn't use floating point numbers. Here's a related question: https://stackoverflow.com/questions/33154412/scipy-linear-programming-rational-numbers . – Matthew Woodruff Dec 06 '18 at 20:30
  • 1
    Probably not what you want to hear, but this would be a neat project. – Matthew Woodruff Dec 06 '18 at 20:31
  • It's called mixed integer programming (MIP)? Check out [or-tools](https://developers.google.com/optimization/mip/integer_opt) – spinkus Dec 16 '18 at 03:24
  • Try Prolog. It is better suitable for this task: https://www.swi-prolog.org/pldoc/doc/_SWI_/library/clp/simplex.pl – Jose Cabrera Zuniga Apr 07 '23 at 16:46

2 Answers2

0

Maybe I am missing the point but any Linear Programming task where you want rational number solution is in fact an Integer Programming problem where you find LCD (Least Common Denominator) for all of the fractional variables and agree the numerators which you later use as integers. So, it seems like the problem only needs reformulation and you can get the exact solution.

sophros
  • 14,672
  • 11
  • 46
  • 75
  • 1
    I would have to find an a priori bound on the scaling, which is pretty large. And then I would need an ILP-solver, that uses BigInteger, buy any such solver should(?) have an exact LP-relaxation anyway. – Hennich Jan 21 '20 at 10:46
  • Second @Hennich's comment this answer is really not relevant. If people want an exact LP solver then thats what they want. They shouldn't be forced to use an IP solver – Sidharth Ghoshal Apr 07 '23 at 03:10
  • @SidharthGhoshal Since the question did not attract many answers I hoped to help with a reformulation of the problem. How does this force the OP to do anything? – sophros Apr 07 '23 at 09:45
0

So unfortunately all the famous rational LP solvers for python are less than perfect at the moment.

Let's start with QSOPTEX:

On Mac OS one can install QSOPTEX and get it working with python3 by first installing:

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

and then installing

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

The installation of the second piece is a little complex because as of April 7, 2023, if you used brew to install gmp then to install python-qsoptex you need to use something along the lines of

sudo GMP_INCLUDE_DIR=/usr/local/Cellar/gmp/6.2.1_1/include GMP_LIBRARY_DIR=/usr/local/Cellar/gmp/6.2.1_1/lib  QSOPTEX_INCLUDE_DIR=/usr/local/include QSOPTEX_LIBRARY_DIR=/usr/local/lib \
        python3 setup.py install

Since your answer mentions .so files I believe you might be using Window in which case you want a sudo equivalent (a quick google search seems to suggest gsudo) and you will need to dig around your system to find where your gmp is installed along with qsoptex.

Issues:

So unfortunately QSOPTEX appears to segfault somewhat randomly on MAC OS. I'm still trying debug why that is the case and if it is an easy fix.

Soplex:

I can't seem to find a python3 interface either so your best bet is to just use pexpect to interact with this. pexpect allows you to run command line commands from python3. See here: https://www.geeksforgeeks.org/how-to-use-python-pexpect-to-automate-linux-commands/

Sidharth Ghoshal
  • 658
  • 9
  • 31