python - 如何求解非负整数的线性方程组？

Question

给定一个线性系统 Ax = b，其中矩阵 A 和向量 b 具有整数值，我想找到所有 求解此方程的非负整数 向量x。

到目前为止，我已经找到了一些技巧，例如 Smith normal form或 Hermite normal form的矩阵来找到整数解，我想我可以使用线性求解器来找到非负解。是否有图书馆可以使这更容易？

Python 解决方案是理想的，但如果一个库以另一种语言存在，我想了解它。

Answer 1

您可以使用整数规划来做到这一点，为您拥有的每个 x 值定义一个非负整数决策变量。然后，您可以解决具有约束 Ax=b 和目标 0 的问题，它会搜索您的方程组的任何可行整数解。

这可以使用 python 中的 pulp 包轻松实现。例如，考虑解决以下系统:

x+2y+z = 5
3x+y-z = 5

你可以用 pulp 解决这个问题:

import pulp
A = [[1, 2, 1], [3, 1, -1]]
b = [5, 5]
mod = pulp.LpProblem('prob')
vars = pulp.LpVariable.dicts('x', range(len(A[0])), lowBound=0, cat='Integer')
for row, rhs in zip(A, b):
    mod += sum([row[i]*vars[i] for i in range(len(row))]) == rhs
mod.solve()
[vars[i].value() for i in range(len(A[0]))]
# [1.0, 2.0, 0.0]

这确定了一个可行的整数解，x=1, y=2, z=0。