如何有效去除冗余线性约束进行优化？

Question

我的优化问题涉及数以千计的线性约束。我想通过找到冗余约束来降低我的问题的复杂性，例如3 * x + 4 * y < 10，如果我已经有一个约束是4 * x + 5 * y < 10（x并且y是>= 0，这就是我的问题的情况）。

所以，我有一个包含所有系数的 numpy 数组，它看起来像这样，例如：

[[0.1, 3.0, 4.8, 0.2],
 [1.0, 4.7, 5.3, 0.1],
 [2.2, 4.3, 5.2, 1.1]]

表示约束：

0.1 * w + 3.0 * x + 4.8 * y + 0.2 * z < 10
1.0 * w + 4.7 * x + 5.3 * y + 0.1 * z < 10
2.2 * w + 4.3 * x + 5.2 * y + 1.1 * z < 10

我如何有效地找出哪些是多余的？

我的常识告诉我做一个循环（伪代码）：

for i, row1 in enumerate(array):
    for j, row2 in enumerate(array):
        if j > i:
            if all(row1 > row2):
                delete row

但这对于数千个缓慢的约束。有什么办法可以加快速度？

Answer 1

我认为为了加快这个问题的速度，你可以使用backtracking例如，你可以一一检查数组中的系数！如果您发现一个索引小于其他索引，您可以停止检查并删除该行！