python - 使用 numpy 求解整数线性系统

Question

我正在尝试用 numpy 求解一个超定线性方程组。目前，我正在做这样的事情(作为一个简单的例子):

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

print np.linalg.lstsq(a,b)[0]

[ 1.  1.]

This works, but uses floats. Is there any way to solve the system over integers only? I've tried something along the lines of

print map(int, np.linalg.lstsq(a,b)[0])

[0, 1]

为了将解决方案转换为整数数组，需要 [1, 1]，但显然我遗漏了一些东西。谁能指出我正确的方向？

Answer 1

您应该使用专门的整数问题求解器(请注意，整数问题甚至都不容易求解)。 openopt 是一个包，例如应该为您正在做的整数二次优化提供良好的包装。尝试使用线性代数不会直接为您提供正确的解决方案。

你的问题可以写成 quadratic program , 但它是一个 integer一个，因此使用 openopt 或其他一些模块。由于这是一个非常简单、不受约束的方法，也许还有其他方法。但是对于初学者来说，并不是一开始看起来那么简单的问题，openopt等已经有程序可以高效的解决这类问题。