最大化矩阵最小对角线元素的算法

Question

最大化矩阵最小对角线元素的算法

algorithmoptimizationmatrixdistancelinear-programming

3

假设我们有一个方阵A。我们的目标是通过行置换来最大化最小对角线元素。换句话说，对于给定的矩阵A，我们有n个对角线元素，因此我们有最小值$min{d_i}$。我们的目的是通过行置换达到可能具有最大最小对角线元素的矩阵。

这就像在所有行置换中的$max min{d_i}$。

例如，假设A = [4 3 2 1; 1 4 3 2; 2 1 4 3; 2.5 3.5 4.5 1.5]。对角线为[4, 4, 4, 1.5]。对角线的最小值是1.5。我们可以交换第3行和第4行以得到新矩阵$\tilde_A$ = [4 3 2 1; 1 4 3 2; 2.5 3.5 4.5 1.5; 2 1 4 3]。新的对角线为[4, 4, 4.5, 3]，具有新的最小值3。理论上，这似乎是我可以获得的最佳结果，因为似乎没有更好的选择：3似乎是$max min{d_i}$。

在我的问题中，n要大得多，如1000。我知道有n！种行置换，因此从理论上讲，我无法遍历每个置换。我知道贪心算法会有帮助-我们从第一行开始。如果a_11不是第一列中最小的元素，则通过行置换将a_11与第一列中最大的元素交换。然后，通过将a_22与第二列中所有剩余元素（除了a_12）进行比较，我们查看第二行。如果它不是最小值，则交换a_22。... ...等。我们一直这样做，直到最后一行。

是否有更好的算法来完成它？

这类似于最小欧几里得匹配，但它们并不相同。

- Appalachian Math

我不确定我理解了。你能举个例子吗？根据我的理解，你不能只是在矩阵中找到最小的元素，比如a_xy，并交换行x和行y吗？这将把矩阵中的最小元素放在行y，列y处。 - user1952500

@user1952500 非常感谢您及时的回复。我添加了一个示例，希望能有所帮助。 - Appalachian Math

2个回答

2

假设 $x_{ij}$ 在 i 行被移动到 j 行时为 1，否则为 0。

你对以下整数规划感兴趣：

最大化 z

$\sum_{i=0}^n x_{ij} = 1 \forall j$

$\sum_{j=0}^n x_{ij} = 1 \forall i$

A[j,j]x_{ij} >= z

然后将其插入 GLPK、Gurobi 或 CPLEX 进行求解。或者使用自己的分支定界方法求解 IP。

- Tom Swifty

1

好的观点......如果您正在使用开源软件，这个问题规模肯定可能是一个问题。然而，商业求解器通常可以解决1000^2甚至更大的问题。 - Tom Swifty

那我会尝试使用MATLAB来解决它。那是我现在唯一知道的软件。如果MATLAB不起作用，我会接触你提到的另外三个软件。 - Appalachian Math

但这是一个整数问题，它是否是#P难的？ - Appalachian Math

我明白了。你说如果交换行i和j，x_{ij}将为1。这是否意味着x_{ij}必须等于x_{ji}，即1？因此，对于所有的j来说，A_{j,j}x_{ij}应该大于z，是吗？ - Appalachian Math

我会尝试使用Ford-Fulkerson算法，因为这是一个整数线性规划问题。这应该不是一件容易的事情。但是我真的非常感谢你的帮助兄弟。 - Appalachian Math

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

假设您想知道是否有比3更好的解决方案。将您的矩阵更改为每个严格大于3的元素都为1：

4    3   2   1     1 0 0 0
1    4   3   2     0 1 0 0
2.5 3.5 4.5 1.5 -> 0 1 1 0
2    1   4   3     0 0 1 0

你的问题可以理解为在双分图中寻找完美匹配，该双分图具有这个二进制矩阵作为其双向邻接图。

在这种情况下，很容易看出没有办法改善您的结果，因为没有办法重新排列行以使得最后一列的对角线条目大于3。

对于一个更大的矩阵，有有效的算法来确定双分图中的最大匹配。

这提示了一种算法：

使用二分法找到生成图具有完美匹配的最大值
与最大值相对应的分配将等于行的最佳排列

编辑

这段Python代码演示了如何使用networkx库来确定图在特定截止值下是否具有完美匹配。

import networkx as nx

A = [[4,3,2,1],
     [1,4,3,2],
     [2,1,4,3],
     [2.5,3.5,4.5,1.5]]

cutoff = 3
G=nx.DiGraph()
for i,row in enumerate(A):
    G.add_edge('start','row'+str(i),capacity=1.0)
    G.add_edge('col'+str(i),'end',capacity=1.0)
    for j,e in enumerate(row):
        if e>cutoff:
            G.add_edge('row'+str(i),'col'+str(j),capacity=1.0)

if nx.max_flow(G,'start','end')<len(A):
    print 'No perfect matching'
else:
    print 'Has a perfect matching'

对于一个大小为1000*1000的随机矩阵，在我的电脑上大约需要1秒钟。