用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.]

这有效,但使用浮点数.有没有办法只用整数解决系统？我尝试了一些方法

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

[0, 1]

为了将解决方案转换为一组int,期待[1, 1],但显然我错过了一些东西.有人能指出我正确的方向吗？

Answer 1

您应该使用专门的整数问题求解器(请注意整数问题甚至不易解决).openopt是一个包,例如应该为整数二次优化提供良好的包装,就像你正在做的那样.尝试使用线性代数根本无法直接为您提供正确的解决方案.

您的问题可以像二次程序一样编写,但它是一个整数,所以请使用openopt或其他模块.由于它是一个非常简单,不受约束的,也许还有其他方法.但对于初学者来说,它起初并不是一个简单的问题,而且还有openopt等程序可以有效地解决这类问题.

Answer 2

您正在查看一个线性丢番图方程组。快速谷歌搜索就会出现\n Felix Lazebnik 的线性丢番图方程组。在那篇论文中，作者考虑了以下问题：

\n\n

\n

给定线性方程组 Ax = b，其中 A = a(i,j) 是具有整数项的 m \xc3\x97 n 矩阵\n，b 是具有整数分量的 m \xc3\x97 1 列向量，系统\n 是否有整数解，即具有整数分量的 n \xc3\x97 1 解向量 x ？

\n

\n