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

Question

我有一个带有整数约束的 LP，我想使用 Python 以精确算术求解。 其实我只需要一个可行点即可

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

以前的尝试：

• Find exact solutions to Linear Program 提到 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）做something，称之为LP，但我不知道他们实际解决了哪个问题。

速度只是一个适中的问题。我的较大实例有大约 500 个带框约束的变量和 40 个等式，但涉及的数量可能很大。

Answer 1

也许我忽略了这一点，但任何你想要有理数解决方案的线性规划任务实际上是一个整数规划问题，你在其中找到所有小数变量的 LCD（最小公分母）并同意你以后用作整数的分子.所以，这个问题似乎只需要重新表述，你就可以获得确切的解决方案。

Answer 2

所以不幸的是，目前所有著名的 python 理性 LP 求解器都很糟糕，这只是最诚实的评估。

让我们从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 文件，我相信您可能正在使用 Window，在这种情况下您需要一个

sudo

等价物（快速谷歌搜索似乎建议 gsudo）并且您需要深入了解您的系统以找到您的 gmp 所在的位置与 qsoptex 一起安装。

问题：

所以不幸的是，QSOPTEX 在 MAC OS 上似乎随机出现段错误。我仍在尝试调试为什么会这样，以及是否可以轻松解决。

复合体：

我似乎也找不到 python3 接口，所以最好的选择是只使用 pexpect 与之交互。

pexpect

允许您从 python3 运行命令行命令。请参阅此处：https://www.geeksforgeeks.org/how-to-use-python-pexpect-to-automate-linux-commands/