求一组方程的整数解，其中未知数多于方程
Find integer solutions to a set of equations with more unknowns than equations
我正在尝试构建一个系统，我需要为其找到一组线性方程的解，其中变量比方程多（多）。
问题归结为：
想象一组方程式：
A = A1*X1 + A2*X2 + ... + AnXn
B = B1*X1 + B2*X2 + ... + BnXn
如何找到这个系统的一个或多个（正）整数解？
注意：我一直在查看 apache-commons-math 库，但我找不到任何关于如何 solve/find 具有自由变量的系统的解决方案的说明。
我会尝试以下方法（请注意，我从来没有处理过那个问题，所以将此答案视为与您一起解决问题的尝试，而不是真正的分析性答案）。
你只是找到解决方案，就像它是一个常规系统一样，所以你可能会找到无限多的解决方案：
示例：
y = x + 3
那么实数对 (2,5) 是该系统的一个可能的实数解，一旦你有无限多的解，你只需限制由整数组成的解的一个子集。
当然你有限制，在我们的例子中，解决方案只有 1 个自由变量，所以我们可以这样写所有的解决方案：
(x, x+3)
惊喜：
如果某处有无理数，则无整数解：
(x, x+pi) => neither 1st or 2nd number here can be whole at same time
因此，当且仅当您的 "infinitely many solutions" 受整数或有理数约束时，您才可能找到整数解。
假设您有以下向量：
( 3x, (2/5)y, y, x, x+y)
那么一个完整的解决方案可以是：
x=3
y=10/2
如果您觉得答案不令您满意，请告诉：我会删除它，以免获得赏金积分
使用 Lenstra–Lenstra–Lovász 格基约简算法找到系统的 Hermite 范式。
在matlab中很简单http://fr.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html
检查 C++ 的 NTL http://www.shoup.net/ntl/index.html
您可能想看看约束求解器，例如 Z3. There's also a JavaExample。
可以找到解释 Z3 某些功能的有用教程 here。
编辑：另请参阅 Algorithm for solving systems of linear inequalities
这取自relevent Wikipedia section。
- 用矩阵符号重写方程
AX=C。
- 计算
A 的 Smith normal form。粗略地说，就是找到 B=UAV where B[i][j] == 0 if i != j.
B(inverse(V))X=UC- 因为
B[i][j] == 0 如果 i != j，找到 (inverse(V))X 的值很简单，因此 X.
按照这个例子：假设方程是：
7 = x + 3y + 4z + 9w
12 = 4x + 2y + 3z + 7w
有 2 个方程和 4 个未知数。你可以设置2个未知数作为参数，这样系统就会有和未知数一样多的方程：
7 - (4z + 9w) = x + 3y
12 - (3z + 7w) = 4x + 2y
我们将使用 x 和 y 作为未知数。可以求解，在线性求解中留下w和z作为参数：
x = (22 - 3w - z)/10
y = (16 - 29w - 13z)/10
现在，您需要使分子能被分母 10 整除。如果有解决办法，可以测试1到10的所有参数
一般来说，你这样做：
- 选择参数，使未知数与方程式一样多。尝试保留为行列式生成最小绝对值的未知数（在示例中，它是 10，但选择 y 和 z 会更好，因为它会是 |det|=3）
- 求解线性系统并根据参数生成答案
- 测试参数值从1到det的绝对值（如果有解，此时会找到），直到所有未知数都有整数解（这就是为什么你选择之前最小的行列式绝对值）并检查它是否为正（示例中没有说明）。
抱歉如果最后一步是暴力破解，但至少有缩小测试范围的可能。也许，有更好的方法来解决最终的丢番图方程组，但我不知道有什么方法。
编辑1
有一种方法可以避免暴力破解最后一部分。同样，在示例中，您必须：
22 = 3w + z (congruent, mod 10)
16 = 29w + 13z (congruent, mod 10)
应用模数：
2 = 3w + z (congruent, mod 10)
6 = 9w + 3z (congruent, mod 10)
您可以使同余系统成为三角形（高斯消元法），将同余乘以模数 10 的倒数，然后求和到其他同余。模10中9的倒数为-1，所以我们乘以最后的同余：
2 = 3w + z (congruent, mod 10)
-6 = -9w + -3z (congruent, mod 10)
相当于：
2 = 3w + z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
然后，乘以-3，再加上第一个：
2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
相当于：
-10 = -20z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
然后，你从上到下求解（这个例子似乎适用于任何 z 值）。如果参数多于同余，则可以有一定的自由度，但它们是等价的，您可以将多余的参数设置为任意值，最好是最小的 1。
如果还有什么不清楚的地方，请告诉我！
如果我没理解错的话，您有多个包裹，每个包裹的邮费都不同。您想从可用的邮票池中支付这些邮资费用。可以用整数规划来解决这个问题。下面的解决方案一次解决了所有包。您将有许多变量等于 numPackages*numStampDenominations（对于大量包裹可能不方便）。
等式约束看起来像 Aeqx = beq。具有 4 个邮票面额 (numVarsnumPackages) 的两个包裹的矩阵 Aeq 如下所示：
.21 .68 .47 .01 .00 .00 .00 .00 .89
* x =
.00 .00 .00 .00 .21 .68 .47 .01 .50
第一行是包 1 的约束系数（标记值）。非零系数是标记值。与其他包相关的零系数变量不关心。
第二组约束（不等式）涉及我可用的邮票池。不等式约束看起来像 A*x = b。 4 个邮票面额和 8 个变量 (numPackages * numStampDenominations) 的矩阵 A 看起来像：
1 0 0 0 1 0 0 0 10
0 1 0 0 0 1 0 0 10
* x <=
0 0 1 0 0 0 1 0 10
0 0 0 1 0 0 0 1 20
代价函数是f'*x，也就是邮票总数。它的系数只是列向量形式的系数。
下面是matlab中的一个脚本运行，它以描述的方式解决了这个问题。它可能会以八度的形式大致相同，这是一个类似于 matlab 的 GNU 产品。 Matlab 或 Octave 可能不是适合您的解决方案，但它们至少会告诉您什么可行，并为您提供一个沙盒来制定解决方案。
% The value of each stamp available as a 4x1 matrix
sv = [.21; .68; .47; .01];
% The number of each stamp available as a 4x1 matrix
sq = [10;10;10;40];
% Number of demominations
m = size(sv, 1);
% The postage required for each package as a 4x1 matrix
% -- probably read from a file
postage = [.89;.50;1.01;.47;.47];
% Number of packages -- just a count of the postage rows
packageCount = size(postage, 1);
% Number of variables is m*packageCount
numVar = m*packageCount;
% lower bound -- zero stamps of a given denomination
lb = zeros(numVar,1);
% upper bound -- use constraints for upper bound
ub = [];
% The cost function -- minimize the number of stamps used
% min(f'*x)
f = ones(numVar,1);
% integer constraints
intcon = 1:numVar;
% Construct postage constraint matrix
Aeq = zeros(numVar, packageCount);
for i = 1:packageCount
first = i*m - 3;
last = first + 3;
Aeq(first:last,i) = sv(:);
end
% Construct stamp count constraint matrix
A = zeros(numVar, m);
for r = 1:m
for j = 1:m
c = (j-1)*m + 1;
A(c,r) = 1;
end
end
x = intlinprog(f, intcon, A', b, Aeq', beq, lb, ub)
我正在尝试构建一个系统，我需要为其找到一组线性方程的解，其中变量比方程多（多）。
问题归结为：
想象一组方程式：
A = A1*X1 + A2*X2 + ... + AnXn
B = B1*X1 + B2*X2 + ... + BnXn
如何找到这个系统的一个或多个（正）整数解？
注意：我一直在查看 apache-commons-math 库，但我找不到任何关于如何 solve/find 具有自由变量的系统的解决方案的说明。
我会尝试以下方法（请注意，我从来没有处理过那个问题，所以将此答案视为与您一起解决问题的尝试，而不是真正的分析性答案）。
你只是找到解决方案，就像它是一个常规系统一样，所以你可能会找到无限多的解决方案：
示例：
y = x + 3
那么实数对 (2,5) 是该系统的一个可能的实数解，一旦你有无限多的解，你只需限制由整数组成的解的一个子集。
当然你有限制，在我们的例子中，解决方案只有 1 个自由变量，所以我们可以这样写所有的解决方案：
(x, x+3)
惊喜：
如果某处有无理数，则无整数解：
(x, x+pi) => neither 1st or 2nd number here can be whole at same time
因此，当且仅当您的 "infinitely many solutions" 受整数或有理数约束时，您才可能找到整数解。
假设您有以下向量：
( 3x, (2/5)y, y, x, x+y)
那么一个完整的解决方案可以是：
x=3
y=10/2
如果您觉得答案不令您满意，请告诉：我会删除它，以免获得赏金积分
使用 Lenstra–Lenstra–Lovász 格基约简算法找到系统的 Hermite 范式。
在matlab中很简单http://fr.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html
检查 C++ 的 NTL http://www.shoup.net/ntl/index.html
您可能想看看约束求解器，例如 Z3. There's also a JavaExample。
可以找到解释 Z3 某些功能的有用教程 here。
编辑：另请参阅 Algorithm for solving systems of linear inequalities
这取自relevent Wikipedia section。
- 用矩阵符号重写方程
AX=C。 - 计算
A的 Smith normal form。粗略地说，就是找到B=UAVwhereB[i][j] == 0ifi != j. B(inverse(V))X=UC- 因为
B[i][j] == 0如果i != j，找到(inverse(V))X的值很简单，因此X.
按照这个例子：假设方程是：
7 = x + 3y + 4z + 9w
12 = 4x + 2y + 3z + 7w
有 2 个方程和 4 个未知数。你可以设置2个未知数作为参数，这样系统就会有和未知数一样多的方程：
7 - (4z + 9w) = x + 3y
12 - (3z + 7w) = 4x + 2y
我们将使用 x 和 y 作为未知数。可以求解，在线性求解中留下w和z作为参数：
x = (22 - 3w - z)/10
y = (16 - 29w - 13z)/10
现在，您需要使分子能被分母 10 整除。如果有解决办法，可以测试1到10的所有参数
一般来说，你这样做：
- 选择参数，使未知数与方程式一样多。尝试保留为行列式生成最小绝对值的未知数（在示例中，它是 10，但选择 y 和 z 会更好，因为它会是 |det|=3）
- 求解线性系统并根据参数生成答案
- 测试参数值从1到det的绝对值（如果有解，此时会找到），直到所有未知数都有整数解（这就是为什么你选择之前最小的行列式绝对值）并检查它是否为正（示例中没有说明）。
抱歉如果最后一步是暴力破解，但至少有缩小测试范围的可能。也许，有更好的方法来解决最终的丢番图方程组，但我不知道有什么方法。
编辑1
有一种方法可以避免暴力破解最后一部分。同样，在示例中，您必须：
22 = 3w + z (congruent, mod 10)
16 = 29w + 13z (congruent, mod 10)
应用模数：
2 = 3w + z (congruent, mod 10)
6 = 9w + 3z (congruent, mod 10)
您可以使同余系统成为三角形（高斯消元法），将同余乘以模数 10 的倒数，然后求和到其他同余。模10中9的倒数为-1，所以我们乘以最后的同余：
2 = 3w + z (congruent, mod 10)
-6 = -9w + -3z (congruent, mod 10)
相当于：
2 = 3w + z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
然后，乘以-3，再加上第一个：
2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
相当于：
-10 = -20z (congruent, mod 10)
4 = w + 7z (congruent, mod 10)
然后，你从上到下求解（这个例子似乎适用于任何 z 值）。如果参数多于同余，则可以有一定的自由度，但它们是等价的，您可以将多余的参数设置为任意值，最好是最小的 1。
如果还有什么不清楚的地方，请告诉我！
如果我没理解错的话，您有多个包裹，每个包裹的邮费都不同。您想从可用的邮票池中支付这些邮资费用。可以用整数规划来解决这个问题。下面的解决方案一次解决了所有包。您将有许多变量等于 numPackages*numStampDenominations（对于大量包裹可能不方便）。
等式约束看起来像 Aeqx = beq。具有 4 个邮票面额 (numVarsnumPackages) 的两个包裹的矩阵 Aeq 如下所示：
.21 .68 .47 .01 .00 .00 .00 .00 .89
* x =
.00 .00 .00 .00 .21 .68 .47 .01 .50
第一行是包 1 的约束系数（标记值）。非零系数是标记值。与其他包相关的零系数变量不关心。
第二组约束（不等式）涉及我可用的邮票池。不等式约束看起来像 A*x = b。 4 个邮票面额和 8 个变量 (numPackages * numStampDenominations) 的矩阵 A 看起来像：
1 0 0 0 1 0 0 0 10
0 1 0 0 0 1 0 0 10
* x <=
0 0 1 0 0 0 1 0 10
0 0 0 1 0 0 0 1 20
代价函数是f'*x，也就是邮票总数。它的系数只是列向量形式的系数。
下面是matlab中的一个脚本运行，它以描述的方式解决了这个问题。它可能会以八度的形式大致相同，这是一个类似于 matlab 的 GNU 产品。 Matlab 或 Octave 可能不是适合您的解决方案，但它们至少会告诉您什么可行，并为您提供一个沙盒来制定解决方案。
% The value of each stamp available as a 4x1 matrix
sv = [.21; .68; .47; .01];
% The number of each stamp available as a 4x1 matrix
sq = [10;10;10;40];
% Number of demominations
m = size(sv, 1);
% The postage required for each package as a 4x1 matrix
% -- probably read from a file
postage = [.89;.50;1.01;.47;.47];
% Number of packages -- just a count of the postage rows
packageCount = size(postage, 1);
% Number of variables is m*packageCount
numVar = m*packageCount;
% lower bound -- zero stamps of a given denomination
lb = zeros(numVar,1);
% upper bound -- use constraints for upper bound
ub = [];
% The cost function -- minimize the number of stamps used
% min(f'*x)
f = ones(numVar,1);
% integer constraints
intcon = 1:numVar;
% Construct postage constraint matrix
Aeq = zeros(numVar, packageCount);
for i = 1:packageCount
first = i*m - 3;
last = first + 3;
Aeq(first:last,i) = sv(:);
end
% Construct stamp count constraint matrix
A = zeros(numVar, m);
for r = 1:m
for j = 1:m
c = (j-1)*m + 1;
A(c,r) = 1;
end
end
x = intlinprog(f, intcon, A', b, Aeq', beq, lb, ub)