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

Question

给定一个线性系统Ax = b,矩阵A和向量b具有整数值,我想找到解决这个方程的所有非负整数向量x.

到目前为止,我已经找到了一些技术,如Smith正规形式或Hermite正规形式的矩阵来找到整数解,我想我可以使用线性求解器来找到非负解.有没有一个可以让这更容易的图书馆？

Python解决方案是理想的,但如果一个库存在于另一种语言中我想知道它.

Answer 1

您可以使用整数编程来完成此操作,为您拥有的每个x值定义一个非负整数决策变量.然后你可以用约束Ax = b和objective 0来解决这个问题,它会为你的方程组搜索任何可行的整数解.

这可以使用python中的纸浆包轻松实现.例如,考虑解决以下系统:

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.