公司间债务清算的一种新算法

为了确定SCC，必须在Kosaraju算法和Tarjan算法之间进行选择。如[18]所述，考虑到Kosaraju’salgorithm需要对图进行两次DFS遍历，而Tarjan的算法只涉及一次DFS遍历，因此考虑了后一次。Tarjan算法的时间复杂度为O（|V |+|E |）。Tarjan算法基于以下思想（详细描述见算法1）：o通过DFS搜索获得DFS树/林；oSCC代表DFS树的子树从子树的头开始，可以获得SCC中的所有其他节点从一个SCC到另一个SCC没有后缘。（可以有交叉边，但在处理图形时不会使用交叉边）。算法1 Tarjan确定强连通组件的算法1：函数StrongConnect（顶点V）2:num← 数字+13：顺序[V]← num4:链接[V]← 订单[V]5:在堆栈上按V键6:在vertexSuccesorsOfV do7:如果未定义或顺序[succesor]，则8:strong连接（成功）9:链接[succesor]← min（link[V]，link[succesor]）10:else11:如果V在堆栈上，那么12:link[V]← min（link[V]，order[succesor]）13：如果link[currentV]=order[currentV]，那么14：创建一个新的强连接组件15:repeat16:auxV-ertex← 堆栈拓扑17：将auxV ertex添加到强连接组件18：从堆栈弹出顶部19:Toll currentV=auxV ertex 20:function TARJAN（图G）21:num← 022：初始化堆栈23：对于图G do24中的顶点V：如果或der[V]未定义，则25:StrongConnect（V）2.2用于网络电路计算的约翰逊算法约翰逊算法首次发表在[12]中，是一种计算有向稀疏图中所有对最短路径问题的方法。

我们的问题需要约翰逊算法的一种特殊方法，考虑到所有权重都是非负的事实。对于有向稀疏图中的电路计数问题，Johnson提出的解决方案包括多项式时间算法。正如Leiserson在[5]中分析的那样，Johnson的算法与Floyd Warshall算法非常相似。在效率方面，Johnson的算法时间复杂度与图中的弧数直接相关，而FloydWarshall的方法不同（与图中的节点数直接相关）。这就是为什么Donald B.Johnson开发的算法更适用于稀疏图，而Loyd Warshall更适用于稠密图的原因。Johnson的算法在O（vlogv+|V | | E |）时间内运行，而Floyd Warshal在O（V）时间内运行。正如Leiserson在[5]中概述的那样，Johnson的算法基于两个众所周知的最短路径子程序。第一个是Bellman Ford，用于消除负边缘、识别负电路和重新加权初始图形。第二种是Dijkstra的最短路径算法，用于确定所有节点对之间的最短路径。

在我们的案例中，考虑到边缘的价值只能是正的，反映了发票的总额，贝尔曼-福特步骤是不必要的。算法2计算网状电路的约翰逊算法的变体1：功能电路（顶点V）2：电路F← 错误3：已获取电路组件的最大数量← false4:在堆栈中推V 5:阻塞的EDV rtxList[V]← true6:if sizeOf（堆栈）≥ maxNumberOf Circuit Components然后7:maxNumberOf Components已获取← true8:else9:对于VertexSuccessor或V do10:如果VertexSuccessor是startV ertex，则11:保存当前电路12:电路已找到← true13:else14:如果blockedV rtxList[VertexSuccessor]为false，则15:Circuitfound← CIRCU IT（顶点成功）16：如果发现电路或达到电路组件的最大数量，则17：取消阻塞（V）；18:else19：对于VertexSuccessor in Successor of Current V ertex do20：如果V不在blockedListF或V ertex[VertexSuccessor]中，则21：将V添加到blockedListF或V ertex[VertexSuccessor]22:pop from stack 23：返回回路F ound算法3解锁过程1：函数解锁（顶点V）2:blocked[V]← true3:while blockedListF or V ertex[V]不是空的do4:vertexT oU nblock← blockedListF或V ertex[V]5中的第一个元素：如果文本oU nblock位于blockedV ertex中，则在约翰逊算法的变体中，第6行可以注意到MaxNumberOfCircuitComponents的使用。这是我们根据原始约翰逊算法对网络问题进行的调整。如果堆栈超过此阈值，则停止回路搜索。他们的想法是，为了有效实施，网络电路必须得到所有成员的批准。电路越长，所有成员接受的概率越低。因此，搜索仅限于某个变量。

为了设置电路元件的最大数量，实现了无状态，以计算已实现电路的最可能大小。因此，变量设置为最可能电路长度值的两倍。2.3最大化联网实施第2.1小节和第2.2小节中概述的算法介绍了如何计算联网电路。一旦我们有了这些电路，另一个重要的问题是最大限度地实现网络的总价值。最大化可以通过选择合适的净额结算顺序来实现。例如，图3概述了三种网络电路。如果一个人成功地实现了电路ABCD，则获得的总金额为28.000（7000×4）。在这种情况下，第二个电路ABDEF无法实现，因为边缘AB的剩余值为0。此外，无法实现电路BCGH，因为边缘BCGH的剩余值为0。然而，如果先实现ABDEF电路，则会产生1000个（200×5）。此后，对于ABCD电路，产生27 200的量。考虑到这两个电路ABDEF和ABCD，按照这个顺序或实现，总共产生28200个。在这种情况下，无法实现电路BCGH。类似地，边BC的剩余值为0。最佳实施顺序为ABDEF、BCGH和ABCD。这项实施总共产生29000美元。前面提到的例子很简单，只考虑了三个电路。在现实生活中，数十万个电路必须以最佳的实现顺序放置。即使在前一个例子中，总增益似乎很小，但在其他情况下，增益明显更高。我们描述了电路实现优化的算法。上一节中计算的每个回路都代表一个图中的顶点。

在该图中，两个顶点之间的边表示两个回路相交的事实。边的值被视为交点中线段的最小值。因此，如果考虑顶点1和顶点2，如果它们之间的边的值为200，则意味着两个回路之间的最小交点为200。因此，如果通过使用电路1实现联网，并且如果每段的联网值为200，则无法实现第二个电路，因为200段已经被消耗。但是，如果通过使用回路1来实现联网，并且如果每段的联网值为150，则回路1和回路2之间的交点将减少到50。因此，考虑到电路2，在每个分段的网络中可以考虑的最大数量是电路2与电路1交叉口外的50和最小分段之间的最小值。图3概述了这一想法，其中我们将前面介绍的电路、ABCD（每边7000个）、ABDEF（每边200个）、BCGH（每边300个）作为节点。如前所述，算法流程是：创建发票图；计算强连接部件；计算每个强连接元件的电路；优化Netting的实施顺序。在这个优化阶段，算法运行在由强连接元件产生的每一组电路上。更准确地说，对于由强连接元件产生的每一组电路，我们选择一个任意顶点v，并在v上调用优化算法（参见算法4）。算法4详尽地尝试了电路的所有可能顺序，从而保证了其最优性。3实验在本节中，我们概述了有关实验的细节。

此外，我们还介绍了几个有趣的实现细节。我们的算法流程分为四个阶段：有向图创建、强连接组件计算、电路确定、电路实现顺序优化。算法流程根据管理与信息学研究所提供的原始数据进行测试，罗马尼亚算法部4电路解决方案优化1：功能优化算法（顶点V）2：将V添加到解决方案3：从图中删除因执行V4而排除的所有顶点：如果图中还有任何节点，则5：对于图中的下一个顶点do6：优化算法（下一个）7:else8：保存优化解决方案及其结果值9：从结算解决方案中删除当前节点10：将之前因实施当前节点而排除的节点重新加载到图表中图3：电路结算优化示例经济性。这些算法是用C#实现的。NET Core 3.0是微软的一项技术。实验中涉及的硬件由两台Dell PowerEdge R730服务器组成，具有128 GB的RAM。我们在罗马尼亚经济部提供的两个真实数据上测试了我们的算法，以便将我们的算法与2000-2017年期间手动获得的结果进行比较。此外，我们还使用了一些模拟数据，其中包含的实例比真实的实例大得多。因此，我们的目标是测试我们算法的鲁棒性。然后，在图4中，我们概述了一个计算示例，其中涉及15000家公司，它们之间有50000条不同的发票路径。考虑到2到8个元件之间电路的计算，我们进行了几个实验。根据管理与信息研究所提供的统计数据，超过90%的网络由最多4个元件的电路实现。

在我们的模拟中，我们的电路长度最多为8个元件，是最可能的电路长度（4）的两倍。计算最多8个元件电路的运行时间对于实际应用是可行的。正如我们从15000家公司和50000条不同路径的测试数据集中观察到的那样，包含6个以上组件的计算电路在计算时间上显著增加。图4：实验结果。在图5和图6中，我们将经济部IMI实施的联网电路数量与实施联网所用发票的算法流程（前三个阶段：有向图创建、强连接组件计算、电路确定）计算的电路数量进行比较。为了计算每年的电路数量，我们考虑了当年实现实际寿命净额的发票。例如，2004年，综管信息系统实施了49 863次净额结算。根据支持这些网络的发票，我们的算法确定了282 727条电路。请注意，计算电路的总数至少是已实现网络数的五倍。回想一下这样一个事实，即IMI根据业务代理的日常交互将电路作为一个请求来实现，电路不是由计算方法产生的。因此，这些图表概述了一个事实，即通过使用算法流程，网络解决方案集将显著增加。此外，通过登记越来越多的发票，计算出的联网电路将大大增加。在图5和图7中，我们概述了将算法FLOW（电路实现优化顺序）的第四步应用于IMI实现的网络电路以及计算电路集的结果。

人们可以注意到，如果IMI实现的结算使用适当的执行顺序（增加超过60%），净额总额将从2430亿美元左右增加到3970亿美元左右。此外，如果计算出的电路按正确的顺序实现，那么总共将实现约9070亿RON。与IMI实施的2430亿美元相比，这一数字增加了约270%。4结论清算是改善经济中公司之间互动的重要机制。它包括一项协议行为，其中各方根据其应得的金额确定其所欠的金额。在本文中，我们提出了一组图算法，以计算一个国家的经济规模的网络解决方案。分析和实验是基于罗马尼亚经济部提供的真实数据实现的。作为未来的工作，我们的目标是考虑一种额外的优化类型，以最大限度地增加净额结算过程中的参与者总数。在本文中，我们优化了最大净负荷。然而，另一个对经济有益的方面是让尽可能多的公司参与进来，以便从清算带来的优势中获益。通过最大化净额，我们注意到图5：IMI净额与应用最大化算法的结果之间的比较，在某些情况下，与大公司互动的中小型公司处于不利地位，因为为了使金额最大化，拟议的电路往往对大公司有利。Weplan设计了一个优化算法，用于平衡净金额和参与者数量。参考文献[1]D·J·亚伯拉罕、A·布鲁姆和T·桑德霍姆。

易货交易市场的清算算法：启用全国肾脏交易。2007年6月11日至15日，美国加利福尼亚州圣地亚哥，第八届ACM电子商务会议（EC-2007）筹备工作编辑J.K.MacKie Mason，D.C.Parkes和P.Resnick。ACM，2007年。[2] E.C.银行。欧洲央行词汇表。https://www.ecb.europa.eu，2009年12月。[3] M·L·贝奇、B·马德森和L·纳托普。丹麦银行间净额结算系统中的系统性风险。技术报告，丹麦国家银行工作文件，2002年。图6:IMI实现的电路数量与已实现电路[4]S.Chen和D.Wu隐含的发票算法流计算的电路数量的对比图。支付系统的连通性、净额结算和系统性风险。IEEE SystemsJournal，13（2）：1658–16682019年。[5] T·H·科尔曼、C·E·莱瑟森、R·L·里维斯特和C·斯坦。算法导论，第三版。麻省理工学院出版社，第三版，2009年。[6] P.Cs\'oka和P.J.Herings。金融网络中的分散清算。《管理科学》，64（10）：4681–46992018年。[7] 胡马尔。国际结算中的系统性风险。ESRC剑桥大学商业研究中心，第152号工作文件，1999年。[8] 艾森伯格和T·H·诺。金融系统中的系统性风险。管理科学，47（2）：236-2492001。[9] M.埃利奥特、B.戈卢布和M.O.杰克逊。金融网络和传染。《美国经济评论》，104（10）：3115–3153，2014年10月。[10] M.M.G–untzer、D.Jungnickel和M.Leclerc。银行间支付清算的高效算法。《欧洲运筹学杂志》，106（1）：212–219，1998年。[11] http://gama.imi.ro/.罗马尼亚经济部长，赔偿服务，2020年。访问：202002-10。[12] D·B·约翰逊。稀疏网络中最短路径的高效算法。J.ACM，24（1）：1-131977年。[13] D.库姆兰德。

一些实用的支付清算算法。K.M.Ellethy，《计算科学和软件工程高级技术》编辑，2008年会议录第二卷图7：IMI实现的净额比较图，IMI实现的净额电路最大化算法阶段的结果，《计算机、信息和系统科学与工程国际联合会议国际系统、计算科学和软件工程会议（SCSS）》中计算电路设置的最大化算法阶段的结果，CISSE 2008，美国康涅狄格州布里奇波特，第307–312页。斯普林格，2008年。[14] D.库姆兰德。关于优化支付清算业务流程——一种进化方法。2012年欧洲计算机大会。[15] L.C.G.罗杰斯和L.A.M.维拉特。银行间网络的故障与救援。《管理科学》，59（4）：882-8981013。[16] 夏皮罗。国际现金管理中的付款净额结算。《国际商业研究杂志》，9（2）：51-58，1978年6月。[17] V.斯里尼瓦桑和Y.金。国际现金管理中的支付净额结算：一种网络优化方法。国际商业研究杂志，17:1-20061986。[18] R·E·塔扬。深度优先搜索和线性图算法。暹罗J.计算机。，1(2):146–160, 1972.[19] 汤普金斯先生和奥利瓦雷斯先生。来自世界各地的清算和结算系统：定性分析。技术报告，加拿大银行Staff讨论文件，2016年。[20] D.B.韦斯特。图论导论。普伦蒂斯大厅，第二版，2000年9月。