在Python中解决有理数线性规划问题

Question

我有一个带整数约束的LP问题，想要使用Python来进行精确算术求解。实际上，我只需要找到一个可行点。

编辑：这里的"精确算术"指的是无限枚举和分母的有理数。

之前的尝试：

• 寻找线性规划的精确解决方案提到了qsoptex，但当我尝试导入它时，我得到了ImportError: libqsopt_ex.so.2: cannot open shared object file: No such file or directory，尽管据我所知，我已经给出了该库的路径。
• Soplex在控制台上可以运行，但我找不到Python接口。
• PySCIPOpt (https://github.com/SCIP-Interfaces/PySCIPOpt)是SCIP的Python接口，包括SoPlex，但我不知道如何调用特定的求解器（具有特定选项）。
• cdd (https://pycddlib.readthedocs.io/en/latest/linprog.html)做了一些事情，称其为LP，但我不知道他们实际解决了哪个问题。

速度只是一个中等的问题。我的大一些的问题有大约500个带有箱式约束的变量和40个等式，但涉及到的数字可能很大。

- Hennich

---

当您说精确算术时，您是指变量应该是整数？有理数？ - Matthew Woodruff

@MatthewWoodruff 有理数 - Hennich

有趣。对于这种小问题，您肯定可以编写一个单纯形求解器来完成此任务，但我不知道是否有任何不使用浮点数的线性规划求解器。这里有一个相关的问题：https://stackoverflow.com/questions/33154412/scipy-linear-programming-rational-numbers。 - Matthew Woodruff

可能不是你想听的，但这将是一个很棒的项目。 - Matthew Woodruff

它被称为混合整数规划（MIP）吗？请查看 or-tools。 - spinkus

试试Prolog。它更适合这个任务： https://www.swi-prolog.org/pldoc/doc/_SWI_/library/clp/simplex.pl - Jose Cabrera Zuniga

Answer 1

也许我没有理解问题的重点，但是任何需要有理数解的线性规划任务实际上都是一个整数规划问题，其中你需要找到所有分数变量的最小公倍数（LCD），并同意后面用作整数的分子。因此，问题似乎只需要重新表述，就可以得到精确的解决方案。

- sophros

---

我需要找到一个先验的缩放上限，这个上限相当大。然后我需要一个使用BigInteger的ILP求解器，但是任何这样的求解器都应该有一个精确的LP松弛。 - Hennich

第二个评论并不相关。如果人们想要一个精确的线性规划求解器，那就是他们想要的。他们不应该被强制使用整数规划求解器。 - Sidharth Ghoshal

@SidharthGhoshal 由于这个问题没有吸引到很多答案，我希望通过重新阐述问题来帮助。这如何迫使OP去做任何事情？ - sophros

Answer 2

很不幸，目前所有著名的Python线性规划求解器都存在一些问题。

让我们从QSOPTEX开始：

在Mac OS上，可以先安装QSOPTEX，然后再安装python3，就可以让它正常工作：

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

然后安装

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

第二个部分的安装有点复杂，因为截止到2023年4月7日，如果你用brew来安装gmp，那么要安装python-qsoptex，你需要使用类似以下的命令。

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

由于您的回答提到了.so文件，我认为您可能正在使用Windows，因此您需要一个sudo等效物（快速谷歌搜索似乎建议使用gsudo），并且您需要在系统中查找gmp和qsoptex的安装位置。

问题：

不幸的是，QSOPTEX在MAC OS上似乎会随机崩溃。我仍在尝试调试为什么会出现这种情况以及是否容易修复。

Soplex：

我似乎也找不到python3接口，所以您最好只使用pexpect与其交互。pexpect允许您从python3运行命令行命令。请参见此处：https://www.geeksforgeeks.org/how-to-use-python-pexpect-to-automate-linux-commands/

- Sidharth Ghoshal