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

Question

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

到目前为止，我已经找到了一些技术，例如矩阵的 Smith normal form or the Hermite normal form 来找到整数解，我想我可以使用线性求解器来找到非负解。有没有可以使这更容易的库？

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

Answer 1

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

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

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

您可以通过以下方式解决这个问题：

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。

Answer 2

这是Z3模型。 Z3 是微软的定理证明器。该模型与之前提出的 MIP 模型非常相似。

在 MIP 中枚举整数解决方案并非完全微不足道（可以通过一些努力 [link] 或使用 "solution pool" 中的技术来完成高级 MIP 求解器）。使用 Z3 这会更容易一些。使用约束规划 (CP) 求解器可能更简单：它们可以自动枚举解决方案。

开始吧：

from z3 import *
A = [[1, 2, 1], [3, 1, -1]]
b = [20, 12]
n = len(A[0]) # number of variables
m = len(b)    # number of constraints

X = [ Int('x%d' % i) for i in range(n) ]
s = Solver()
s.add(And([ X[i] >= 0 for i in range(n) ]))
for i in range(m):
    s.add( Sum([ A[i][j]*X[j] for j in range(n) ]) == b[i])

while s.check() == sat:
    print(s.model())
    sol = [s.model().evaluate(X[i]) for i in range(n)]
    forbid = Or([X[i] != sol[i] for i in range(n)])
    s.add(forbid)

解决了

x0+2x1+x2 = 20
3x0+x1-x2 = 12

解决方案如下：

[x2 = 2, x0 = 2, x1 = 8]
[x2 = 7, x1 = 4, x0 = 5]
[x2 = 12, x1 = 0, x0 = 8]

我们可以打印最终模型，这样我们就可以看到 "forbid" 约束是如何添加的：

[And(x0 >= 0, x1 >= 0, x2 >= 0),
 1*x0 + 2*x1 + 1*x2 == 20,
 3*x0 + 1*x1 + -1*x2 == 12,
 Or(x0 != 2, x1 != 8, x2 != 2),
 Or(x0 != 5, x1 != 4, x2 != 7),
 Or(x0 != 8, x1 != 0, x2 != 12)]

Answer 3

如果Ax=b的至少一个非负积分解存在，那么整数规划应该可以找到它。所有非负积分解的集合可以通过A.

的null space找到

例子

在 Erwin 的回答中使用 A 和 b：

>>> from sympy import *
>>> A = Matrix([[ 1, 2, 1],
                [ 3, 1,-1]])
>>> b = Matrix([20,12])

计算空 space:

>>> A.nullspace()
[Matrix([
[ 3/5],
[-4/5],
[   1]])]

空 space 是一维的，其基向量是有理值的。使用 Erwin 找到的特定解 (2,8,2)，所有实解的集合是行参数化为 (2,8,2) + t (3,-4,5)。由于我们只对非负积分解感兴趣，因此我们将直线与非负八分圆相交，然后与整数格相交，得到 t ∈ {0,1,2}。因此，如果：

t=1,得到解(5,4,7).
t=2，得到解(8,0,12).

请注意，这是 Erwin 使用 Z3 找到的 3 个解决方案。

然而，当null space 的维数大于1时，它就更难了。看看：

赫苏斯·德洛埃拉，The many aspects of counting lattice points in polytopes，2005 年。

Answer 4

参见 here 中 4ti2 包的 zsolve 方法。

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

How to solve a system of linear equations over the nonnegative integers?

python

matrix

linear-algebra

sympy

integer-programming

例子