用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 个等式，但涉及的数量可能很大。

Answer 1

也许我没有抓住重点，但任何你想要有理数解的线性规划任务实际上都是一个整数规划问题，你找到所有小数变量的 LCD（最小公分母）并同意稍后用作整数的分子。所以，看起来这个问题只需要重新表述就可以得到精确的解决方案。