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: Find exact solutions to Linear Program mentions qsoptex, but when I try to import it, I get ImportError: libqsopt_ex.so.2: cannot open shared object file: No such file or directory , although to my knowledge, I gave to path to that library. SoPlex works on the console, but I could not find a Python interface. PySCIPOpt ( https://github.com/SCIP-Interfaces/PySCIPOpt ) is the Python interface for SCIP, including SoPlex, but I don't see how to call a specific solver (with specific options). cdd ( https://pycddlib.readthedocs.io/en/latest/linprog.html ) does something , calling it LP, but I have no idea which problem they actually solve. 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.

pythonalgorithmlinear-programmingrational-number

Reputation: 699

Solving rational number Linear Programming problem in Python

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:

Find exact solutions to Linear Program mentions qsoptex, but when I try to import it, I get ImportError: libqsopt_ex.so.2: cannot open shared object file: No such file or directory, although to my knowledge, I gave to path to that library.
SoPlex works on the console, but I could not find a Python interface.
PySCIPOpt (https://github.com/SCIP-Interfaces/PySCIPOpt) is the Python interface for SCIP, including SoPlex, but I don't see how to call a specific solver (with specific options).
cdd (https://pycddlib.readthedocs.io/en/latest/linprog.html) does something, calling it LP, but I have no idea which problem they actually solve.

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.

Upvotes: 5

Answers (2)

Sidharth Ghoshal

Reputation: 720

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/

Upvotes: 0

sophros

Reputation: 16728

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.