LAPJVsp 在增加行缩减期间产生不可行的结果

Question

在 R. Jonker 和 A. Volgenant 中，A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems (doi: 10.1007/BF02278710)，作者展示了一个实现他们的 LAPJV 算法适用于稀疏图并称为 LAPJVsp，在各种问题上表现良好。

LAPJVsp 的 Pascal 实现是 currently available here。该算法的增广行缩减步骤基本没有变化，与已发表论文中提供的代码不同之处仅在于使用图的双邻接矩阵的压缩稀疏行表示，其行索引、列索引和权重均参考分别为 first、kk 和 cc：

tel:=0;
repeat
  h:=1; l0:=l; l:=0;
  while h<=l0 do
  begin
     i:=free[h]; h:=h+1; v0:=inf; vj:=inf;
     for t:=first[i] to first[i+1]-1 do
     begin
        j:=kk[t]; dj:=cc[t]-v[j];
        if dj<vj then if dj>=v0 then begin vj:=dj; j1:=j end
        else begin vj:=v0; v0:=dj; j1:=j0; j0:=j end;
     end;
     i0:=y[j0]; u[i]:=vj;
     if v0<vj then v[j0]:=v[j0]-vj+v0
              else if i0>0 then begin j0:=j1; i0:=y[j0] end;
     x[i]:=j0; y[j0]:=i;
     if i0>0 then
        if v0<vj then begin h:=h-1; free[h]:=i0 end
                 else begin l:=l+1; free[l]:=i0 end
  end;
  tel:=tel+1
until tel=2;

现在，对于稀疏输入，甚至不能保证线性分配问题的可行解存在，而且在许多情况下，这种不可行性可以在过程中被发现，但上面给出的行减少步骤忽略了这个问题，在某些情况下输出不可行的结果，然后一直存活到函数结束。

例如，考虑双邻接矩阵为[[1, 1, 1], [*, *, 1], [*, *, 1]]的二分图，其中*表示缺失边。这可以通过 Pascal 实现运行如下：

n:=3;
first[1]:=1; first[2]:=4; first[3]:=5; first[4]:=6;
kk[1]:=1; kk[2]:=2; kk[3]:=3; kk[4]:=3; kk[5]:=3;
cc[1]:=1; cc[2]:=1; cc[3]:=1; cc[4]:=1; cc[5]:=1;
zlap:=lap(x, y, u, v);

行减少后，列分配 x 变为 [1, 3, 2]，这也最终成为函数的最终结果，尽管该解决方案显然不可行，因为没有边缘从第三行到第二列。

这引出了几个问题：这是一个众所周知的错误吗？假设存在可行的解决方案，是否可以信任该算法提供正确的结果，以便人们可以假设可行性并争辩说这不是错误？是否可以挽救行减少步骤并提供正确的结果或检测不可行性？

Answer 1

发生这种情况是因为对于给定行具有第二高降低成本的列的索引，即 j1，永远不会在不同行之间取消设置。我们通过显式取消设置索引来消除错误：

...
tel:=0;
repeat
   h:=1; l0:=l; l:=0;
   while h<=l0 do
   begin
      j0:=0; j1:=0;  {<-- This is new}
      i:=free[h]; h:=h+1; v0:=inf; vj:=inf;
...

在这一点上，给定行的 dj 的值可能不小于 inf，这意味着 j0 在扩充之前保持为零。明确检查这一点提供了不可行性测试。

LAPJVsp 在增加行缩减期间产生不可行的结果

LAPJVsp produces infeasible results during augmenting row reduction

optimization

graph-theory

mathematical-optimization

pascal

bipartite