拍卖算法

第七章拍卖算法本章讨论最小费用流的第三类主要算法。1.3.3节介绍过分配问题的拍卖算法，4.2节指出过最小费用流问题可以转换为分配问题，因此本章描述的算法源于分配问题的拍卖算法，数学上也等价于分配问题的拍卖算法，在7.3.3节还将更详细地讨论这个问题。本章的算法不依赖于改善费用逻辑，这一点与上一章的算法正相反；在迭代的任何一步，初始费用和对偶费用都有可能同时变坏。另一方面，与7.1节讨论的分配问题和7.4节讨论的广义最小费用流问题类似，也可以将最小费用流拍卖算法视为近似同步上升方法。因为借助分配问题可以获得所有关于拍卖算法的主要理解，所以我们特别关注分配问题，7.1节详细研究了相应的收敛性和计算复杂度理论。7.2节开发了一类特殊分配问题的拍卖算法。7.3节分析了最大流问题中流前冲击算法的某些细节并导出该算法实施过程中的某些计算复杂度；这节还指出，从数学角度看，最小费用流拍卖算法相当于拍卖一类特定分配问题。最后分别在7.4节和7.5节分析了两种最小费用流拍卖算法的某些细节，这两种算法是松弛方法和拍卖／续贯最短路算法。一般来说，拍卖算法的实用性较好，特别是用于某些简单的最小费用流问题，比如分配问题和最大流问题。而且它们的计算复杂度明显低。它们的运行时间很有竞争力，通常比它们之前的算法和改善对偶费用算法优越，我们将在本章和第九章涉及凸可分网络流问题的地方指出这一点。7.1.分配问题的拍卖算法本节考虑分配问题，也就是n个投标人和n个物品的一对一问题。首先假定第i个投标人与第j个物品匹配的‘值’或者‘好处’是ija。我们希望以总‘好处’最大为目标，把人和物品匹配起来。可以分配给第i个投标人的物品集合是个非空集合，记为)(iA。所有可以分配给第个投标人的物品与第个投标人配对的二元组集合为A，{(,)|(),1,,}ijjAiinA=。注意：A是基分配图的弧集，A中的元素个数记为A。分配S是人与物品的二元对集合（可能是空集），它满足：对任意Sji),(都有)(iAj；对每个投标人i，至多存在一对Sji),(，对每个物品j，至多存在一对Sji),(。给定分配S，若存在一对Sji),(，则称第i个投标人被分配，否则称第i个投标人未被分配；用类似的术语形容物品。若分配包含n个二元对，使每个投标人和每个物品都被分配，则就称该分配为可行分配或者完全分配，否则称该分配为偏分配。前面描述的分配问题是对称分配问题，它与非对称分配问题不同。在非对称分配问题中，人数少于物品数。在后面的7.2节将结合拍卖算法讨论非对称分配问题。7.1.1.主拍卖算法回忆1.3.3节以不太严格的方式描述的拍卖算法，当初的动机比较简单、幼稚，难免有缺陷。算法可以正确运行的关键概念是补松弛（缩写为CS），它与偏分配S和价值向量),,,(21npppp联系在一起。若}{max)(kikiAkjijpapa，则称第j个物品在范围内是第i个投标人的最佳物品。若对任意Sji),(都有}{max)(kikiAkjijpapa，（7.1）则称S和p满足补松弛条件。拍卖算法不断跌代，直至获得完全分配才终止跌代。跌代从满足补松弛条件的偏分配和价值向量开始；初始价值向量只要与空分配满足平凡补松弛条件就可以。后面将会指出：跌代能够保持补松弛条件一直得到满足。整个跌代过程由两个阶段组成：投标阶段和分配阶段。下面描述这两个阶段。拍卖跌代的投标阶段设分配S中未被分配的人构成的集合为I；对任意Ii：1．寻找最佳物品ij，使}{maxarg)(jijiAjipaj，和对应值}{max)(jijiAjipav，（7.2）并寻找物品ij以外其它物品提供的最佳值}{max),(jijjjiAjipawi。（7.3）（如果ij是)(iA中的唯一物品，那么定义iw，或者为了便于计算，用一个比iv小得多的数定义iw。）2．用下式计算第i个投标人的‘标值’，iijiijijwawvpbiii。（7.4）（这里的用词不是很准确，应该说第i个投标人对第ij个物品投的标，并且第ij个物品收到第i个投标人的标。）拍卖跌代的分配阶段每个物品j有可能收到若干个投标人在投标阶段的投标，记这些人的集合为)(jP。如果)(jP非空，记最高投标为jp，即ijjPijbp)(max；（7.5）从分配S中去掉),(ji对（如果在S中，第j个物品被分配给第i个投标人），加上),(jij对，其中ji是)(jP中取得上述最大值的那个投标人。注意，允许选择参与投标人的集合I。一种选择是I只包括一个未被分配物品的人。因为这种选择类似于求解非线性方程组的Gauss-Seidel方法，所以称这种选择为Gauss-Seidel版，这种选择通常在串行计算环境下效果好。另一种选择是I只包括所有未被分配物品的人。这种选择适于并行计算环境，因为它类似于求解非线性方程组的Jacobi方法，所以称这种选择为Jacobi版。在跌代过程中，价格改变的物品就是收到投标的物品。每次价格变化至少增加。具体来看，如果第i个投标人根据方程（7.2）至（7.4）投标第j个物品，相应的标值为iiiijiijiijijpvawab，该值超过第j个物品的当前价格，至少超过。跌代结束时，会得到一个不同于先前分配的新分配。在这个新分配里面，每个收到投标的物品都会被分配给一个在跌代开始时未被分配到物品的人。然而，有可能所有收到投标的物品在开始迭代之前已经被分配给某个投标人，而到跌代结束时，这种分配未发生变化，此时跌代结束时的分配就与跌代开始时的分配有同样多的二元对。就如下述命题指出的那样，投标增量的选择［参见方程（7.4）］要保证算法中的补松弛条件得到满足（事实上，下面将会看到，这样选出的投标增量也最大）。命题7.1：在拍卖算法的整个执行过程中，算法都能保持补松弛条件得到满足。也就是说，如果跌代开始时使用的分配和价格向量满足补松弛条件，那么跌代结束时获得的分配和价格向量仍然满足补松弛条件。证明：设第j个物品在跌代前和跌代后的价格分别为jp和jp。又设第j个物品收到第i个投标人的投标，并且在跌代过程中被分配给第i个投标人，那么就有（见方程（7.4）和（7.5））iijjwap。由此式可得}{max),(jijjjiAjijijpawpa。因为对任意j都有jjpp，所以上式蕴含}{max)(jijiAjjijpapa，（7.6）这说明，在跌代过程的分配阶段之后，所有进入分配的二元对),(ji，一直满足补松弛条件（7.1）。考虑一个即属于跌代前之分配，又属于跌代后之分配的二元对),(ji。如果物品j在跌代期间没有收到投标，那么jjpp，此时对任意j仍然有jjpp，从而只要跌代前二元对),(ji因为满足补松弛条件，而有方程（7.6）成立，迭代后仍然有方程（7.6）成立。于是对于所有跌代后属于分配的二元对),(ji都有补松弛条件成立。证毕。下面的结果确立了算法的有效性。证明过程依赖于下述观察结果。（a）一旦物品被分配，它在算法的整个后续阶段就一直保持被分配状态。而且除非算法终止，总有至少一个物品一直未被分配过，该物品的价格仍然维持初始价格。原因是在投标和分配阶段，可能会将已分配物品再次分配给另一个投标人，但是已分配物品不会变成未被分配状态。（b）物品每收到一次投标，它的价格至少增长［见方程（7.4）和（7.5）］。因此，如果物品收到无限次投标，那么它的价格会增长到。（c）第i个投标人每|)(|iA次投标，由方程}{max)(jijiAjipav（7.7）定义的标量iv都会至少减小，其中|)(|iA为集合)(iA中物品个数。原因是第i个投标人的每次投标要么使iv至少减小，要么使iv值保持不变，当后一种情况发生时，必然有一个以上)(iA中物品已经达到方程（7.7）的最大值，此时接受投标的第ij个物品价格至少要增加，因此第ij个物品就不能接受第i个投标人的另一个投标，直至iv至少减小。结论就是：如果第i个投标人无限次投标，iv一定会减少至。命题7.2：如果存在至少一个可行分配，那么拍卖算法终止时获得的可行分配在误差不超过n范围内是最优分配（如果问题数据是整数，且n1，那么算法就终止于最优可行分配）。证明：下面用反证法证明。如果算法不中止，那么接受了无限个投标的物品子集J非空。同时，投标无数次的投标人子集I也非空。如上述（b）中所述，J中物品的价格必然趋近于。同时如上述（c）中所述，对任意Ii，}{max)(jijiAjipav必然减小至。从补松弛条件看，这就蕴含着JiA)(，Ii，（7.8）且在有限次跌代后，每个J中物品都将被分配给I中人。因为有限次跌代之后，至少有一个I中人分不到物品，所以I中人数严格大于J中物品数。而根据方程（7.8），I中人只能获得J中物品，故这不是一个可行分配，与可行分配的存在性矛盾。于是算法一定会终止。根据命题7.1，终止时获得的可行分配满足补松弛条件，再由1.3.3节的命题1.4可知最终获得的可行分配在误差不超过n范围内是最优分配。证毕。7.1.2.近似坐标下降解释因为在Gauss-Seidel版的拍卖算法跌代过程中，会出现单个物品的价格变化同时其它物品的价格保持不变这种现象，所以它类似于坐标下降算法，特别像第6章的松弛方法。然而，与松弛方法相反，这种价格变动很可能严重损害对偶函数njjnijijiAjppapq11)(}{max)(（7.9）的价值。1.3.3节命题1.3引入了这个对偶函数。一般来说，在迭代过程中，对于所有增加的价格坐标，可以将投标和分配阶段近似地看作同步坐标下降过程。坐标下降的目标是对偶函数的近似极小化。特别可以看到，如果第j个物品在分配阶段收到投标，那么其价格jp将会增加，增加量要么为)(pq的极小值，此时所有其它物品的价格保持不变，要么超过)(pq的极大值，但不大于。图7.1显示出这个性质，并且指出对偶费用的恶化程度不超过。图7.1提供的论据确实可以推出Gauss-Seidel版的拍卖算法，这一推导作为练习7.1留给读者。7.1.3.拍卖算法的变形拍卖算法有几种变形，它们相互之间略有不同。例如前面提到过，几个投标人同时竞标一个获奖物品，直至最高出价人出现，此时价格的增长方式可能与方程（7.5）有点差别。算法的核心要素是：（a）保持满足补松弛条件。（b）至少一位没有物品的人分到物品，该物品的价格至少增加，其中是正常数。而且，当一个投标人之前分到的物品收到投标时，这个投标人就变得没有物品了。（c）物品的价格不会下降，跌代开始时被分配了的物品到跌代结束时仍然处于被分配状态（尽管获得该物品的人可能改变）。容易明白，满足这三条规则的任何拍卖算法的变形都会具有命题7.2给出的终止性质。图7.1：沿着价格坐标jp，对偶费用的形态。根据对偶费用q的定义（7.9），q沿着jp的右方向导数是|}),(:{|1ijjjypiAjid，其中}{max),(kikjkiAkijijpaay是jp的水平线，只要jp在水平线ijy之下，投标人i就是物品j的最佳人选。对于所有的i，ijy是使)(iAj的间断点。设}{max)(jijiAjpay，投标人i使jiyy；又设}{maxˆˆ),(jijiiiAjpay，投标人iˆ使iiˆ且jiyyˆˆ。注意区间],ˆ[yy就是沿着坐标jp极小化q的点集。假设迭代前物品j的价格为jp，迭代中物品j收到投标，迭代后物品j的价格为jp，则可以断言ypyjˆ。事实上，如果投标人i在迭代期间出了价，而且赢得了物品j，那么ijjyp，进而可得ypj。下面证明ypjˆ。如果ypjˆ，那么因为jjpp，所以必有ypjˆ；如果y