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

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《A novel algorithm for clearing financial obligations between companies
  -- an application within the Romanian Ministry of Economy》
---
作者：
Lucian-Ionut Gavrila and Alexandru Popa
---
最新提交年份：
2020
---
英文摘要：
  The concept of clearing or netting, as defined in the glossaries of European Central Bank, has a great impact on the economy of a country influencing the exchanges and the interactions between companies. On short, netting refers to an alternative to the usual way in which the companies make the payments to each other: it is an agreement in which each party sets off amounts it owes against amounts owed to it. Based on the amounts two or more parties owe between them, the payment is substituted by a direct settlement. In this paper we introduce a set of graph algorithms which provide optimal netting solutions for the scale of a country economy. The set of algorithms computes results in an efficient time and is tested on invoice data provided by the Romanian Ministry of Economy. Our results show that classical graph algorithms are still capable of solving very important modern problems.
---
中文摘要：
欧洲央行词汇中定义的清算或净额结算的概念对一个国家的经济有很大影响，影响着交易所和公司之间的互动。简言之，净额结算指的是公司之间相互支付款项的一种替代方式：它是一种协议，各方将其所欠金额与所欠金额进行抵销。根据双方或多方之间的欠款，付款由直接结算代替。在本文中，我们介绍了一套图形算法，为一个国家的经济规模提供最佳的网络解决方案。这套算法能够高效地计算结果，并在罗马尼亚经济部提供的发票数据上进行了测试。我们的结果表明，经典图算法仍然能够解决非常重要的现代问题。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Economics        经济学
二级分类：General Economics        一般经济学
分类描述：General methodological, applied, and empirical contributions to economics.
对经济学的一般方法、应用和经验贡献。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Economics        经济学
分类描述：q-fin.EC is an alias for econ.GN. Economics, including micro and macro economics, international economics, theory of the firm, labor economics, and other economic topics outside finance
q-fin.ec是econ.gn的别名。经济学，包括微观和宏观经济学、国际经济学、企业理论、劳动经济学和其他金融以外的经济专题
--

---
PDF下载：
--> A_novel_algorithm_for_clearing_financial_obligations_between_companies_--_an_app.pdf (1.01 MB)

2022-4-26 13:18:38 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：interactions Quantitative Contribution Alternative Internation

一种新的算法，用于清算公司之间的财务义务——罗马尼亚经济部、布加勒斯特数学和计算机科学大学、卢西亚罗马尼亚国家研究与开发研究所的Ionut Gavrila和Alexandru PopaFaculty的申请。伊奥努特。gavrila@drd.unibuc.ro，alexandru。popa@fmi.unibuc.roDecember2020年11月1日摘要欧洲中央银行词汇中定义的清算或净额结算概念对一个国家的经济产生了重大影响，影响着交易所和公司之间的互动。简言之，净额结算指的是公司向对方支付款项的常规方式之外的另一种选择：它是一种协议，其中各方将其所欠金额与所欠金额进行对比。根据双方或多方之间的欠款金额，付款由直接结算代替。本文介绍了一组为一个国家的经济规模提供最优网络解的图算法。这套算法在很短的时间内计算结果，并根据罗马尼亚经济部提供的发票数据进行测试。我们的结果表明，经典图算法仍然能够解决非常重要的现代问题。1简介根据《欧洲中央银行支付、清算和结算系统相关术语汇编》[2]，实体之间的净额结算（也称为清算）概念定义为“三方或多方之间的债务净额结算和多边净结算头寸结算安排”。在一个经济体中运作的公司通过相互开具发票来表达他们之间的互动。这些发票意味着付款义务，通常通过银行转账结算。净额结算提供了直接支付的替代方案。

例如，考虑到两家公司，一家是国家运输提供商，另一家是国家能源提供商，它们相互作用并相互开具发票。因此，他们的共同债务可以通过净额结算，而不是直接付款。在本文中，我们考虑一种特殊的净额结算方法，该方法涉及计算公司之间的债务回路并进行结算。例如，A公司必须向B公司支付32.000美元，B公司必须向C公司支付23.000美元，C公司必须向A公司支付25.000美元。通过清算系统，A公司、B公司和C公司之间确定了一个净额电路。向他们提供了清算最低金额23.000美元的选项。如果公司接受清算，最低金额将从支付义务中扣除。因此，公司A仍需向B支付9000美元，BHA不再向C支付任何款项，C仍需向A支付2000美元。剩余金额可在其他净额结算回路中考虑。净额结算带来了重要的优势，如减少银行转账隐含的延迟、减少转账交易数量、通过避免转账费用降低成本、提高信用风险[7]。根据[3]，“通过减少金融机构之间支付的数量和总价值，净额结算可以提高支付系统的效率”。在金融危机中，中小型公司，在某些情况下甚至大型公司都没有必要的流动性来承担其财务义务。

[4]中以类似的方式对银行系统概述了这一想法。Chen和Wu[4]指出，净额结算带来了网络依赖性和连通性的变化，通过减少银行间债务降低了金融冲击的影响。因此，高效的净额结算系统在降低公司破产风险方面产生了重要的帮助，并且在更广泛的范围内，在降低系统性风险和将经济从多米诺骨牌效应中拯救出来[7]。与图论的联系。网络系统可以用图论来表示。每个公司都可以表示为图中的一个节点。两个节点之间的有向边表示一家公司向另一家公司开具了一组发票。给定两个节点u和v，我们可能同时拥有边（u，v）和（v，u），考虑到每家公司都向另一家公司开具了发票。在这种情况下，这意味着一家公司不仅是一个客户，而且是该缔约方公司的供应商。动机本文的目标是提出改进罗马尼亚网络系统的算法。我们的测试使用了债务和信用清算系统提供的真实数据，该系统在罗马尼亚经济部管理和信息研究所的监督下运行。根据公开数据，从1999年到2017年，总共净赚了2400多亿欧元（600多亿欧元）。这一数额占罗马尼亚年GDP的重要百分比。人们必须反思这样一种观点，即清算金额基于以经验方式确定的电路。通过公司了解其合作伙伴和提出的清算解决方案，手动识别电路。因此，网络解决方案没有自动算法系统的帮助。

在整个国家的经济水平上运行的高效算法的实施为经济环境带来了巨大的好处。罗马尼亚管理与信息学研究所发布的公开结果表如图1所示，更多细节见[11]。从2020年1月1日起，罗马尼亚经济部管理与信息研究所（IMI）的网络平台升级为使用本文提出的算法，以实现电路计算过程的自动化。2020年1月，通过使用我们的计算模型，我们净赚了1亿多欧元。以前的工作和相关工作。净额结算的概念在许多与金融市场、商业和经济相关的论文中都有描述。一些最重要的结果发表在[17,14,10,19,13]上。净额结算主要涉及银行间支付和国际环境下公司分支机构的现金优化[10]，并产生最佳结果。G¨untzer，Jungnickeland Leclerc[10]概述了银行间支付代表了一个涉及大量参与者和大量资金的过程，其中一个例子集中在德国的银行间支付系统。斯里尼瓦桑和金[17]强调了跨国公司之间进行支付净额结算的重要性，并声称公司产生了越来越多的公司间资金流动。因此，通过实施高效的清算系统，人们可以在支付和利息成本方面获得显著节约。Csoka和听证会[6]阐述了清算与金融系统风险相关的重要性，并提出了基于清算支付矩阵的分散清算方法。

在金融网络文献中，Eisenberg和Noe[8]、Elliot[9]、Rogers和Veraart[15]概述了一组用于确定最大清算支付矩阵的算法。上述论文激发了银行间支付或大型公司等系统中净额结算的重要性。正如我们在本文中所展示的，净额结算的概念可以扩展到更大的范围。在罗马尼亚，只有在国家经济规模上应用清算系统才能发挥作用。在罗马尼亚制度中，每一个经济主体都代表着行动方，无论其规模大小。为了解决清除问题，已经提出了多种方法。例如，[10]提出了一些简单而有效的启发式算法来适应网络问题。根据[16]，ShapiroFigure 1：净额结算金额——罗马尼亚管理和信息学研究所，2000年至2017年，根据线性规划制定了跨国支付清算问题，而Srinivasanand Kim在[17]中提出了一种网络优化方法，该方法不仅在计算上有效，而且在直觉上也很有吸引力。对于基于公司间发票的净额结算问题，Kumlander[13]基于图论概述了一套实用的清算算法。根据[1]，对电路长度有界的清除问题是NP难的。因此，根据P6=NP的猜想，这个问题的多项式时间精确算法不太可能存在。我们的结果。在本文中，我们提出了一种计算高效网络解决方案的替代方法。考虑到发票联网的特殊性以及联网电路长度可能有上限的事实，我们提出了一套图论算法，以在发票图中找到精确的电路。

值得一提的是，我们的算法已经被罗马尼亚经济部管理和信息研究所（Institute of Management and Information）接受为债务和信用清算系统的升级版。自2020年1月1日起，这些算法被集成到网络平台中。三周内，处理的金额超过1亿欧元。我们的论文是唯一一篇在国家经济规模上提出债务和信用清算制度的论文。与银行间和公司间净额结算相比，发票净额结算的输入和输出数据集要大得多。因此，整数规划方法无法有效地处理如此大量的数据。在我们的算法中，最重要的部分是基于约翰逊算法的电路识别[12]。根据Leiserson在[5]中的分析，Johnson的算法是多项式算法。它基于两个广为人知的子程序，Bellman Ford（为了消除负反馈）和Dijkstra的最短路径算法。与启发式方法相比，我们的解决方案的效率来自这样一个事实，即发票图被拆分为强连接的组件，这些组件反映了经济中公司之间的相互作用。通过将主要问题分解为较小的相似问题，我们可以获得有效的运行时间。对于每个连接的元件，我们计算一组网络电路。我们的解决方案的另一个优点是，对于来自强连接组件的每一组联网电路，我们根据最大清算金额计算最佳清算顺序。我们的算法主要有以下几个步骤：1。表示基于发票信息的有向图；2.使用Tarjan算法计算图的强连通分量；3.用约翰逊算法确定每个强连通元件的基本电路；4.

计算电路的联网顺序，以最大化总清算金额。前三个步骤涉及的算法在研究论文[18,20,12,5]中有大量介绍。在本文中，上述算法适用于网络问题。以约翰逊算法为代表的第三步是本文首次提出的发票净额结算问题的可能计算框架。第四步是一种创新的算法解决方案，用于最大化总清算金额。我们知道我们的论文没有使用突破性的算法技术。尽管如此，当我们用经典教科书算法的巧妙应用解决现代日常生活问题时，我们还是感到兴奋。本文的其余部分组织如下：在第2节中，我们描述了计算模型的网格算法和实现细节。然后，在第3节中，我们根据罗马尼亚经济部提供的数据展示了我们的实验结果。最后，在第4节中，我们提出了结论和未来的研究方向。2.网络算法在本节中，我们将介绍与拟议网络算法相关的详细信息。首先，我们描述了invoicegraph表示和强连通分量计算。其次，我们描述了约翰逊算法在网络电路计算中的应用。最后，我们给出了网络数量最大化的算法。2.1表示基于发票数据的有向图并计算强连接组件有向图是有序对G=（V，E）（基本图形术语见[20]）。集合V代表一组顶点，也称为节点或点。集合E定义为一组有序的节点对，也称为有向边、弧或有向线。

考虑到网络模型，公司在图中被表示为节点。一家公司对另一家公司的付款义务在图中显示为一条边。例如，如果公司A向公司B开具一组发票，则从B到A的边具有发票总额的总权重。图中的一个简单回路（即，没有顶点或边可以重复）表示一组可以实施联网的公司。定义1（净额结算问题）问题的输入是一个有向图G=（V，E），成本为W:E→ R与每条边关联。解决电路的操作包括降低电路中所有边的值，使该电路中的边的值最小。也就是说，给定一个电路（v，v，…vk，v），设x是电路中边的最小值，即min（mink）-1i=1w（vi，vi+1），w（vk，v）），用w（vi，vi+1）=w（vi，vi+1）替换每个边w（vi，vi+1）的权重- x、 分别为w（vk，v）=w（vk，v）- x、 净额结算问题的目标是找到一组有序的电路，以便在处方中结算它们，使总净额最大化。根据[1]，上述净额结算问题是NP难问题。Johnson的算法，如[12]所述，代表了考虑有向稀疏图的所有对最短路径问题的计算方法。图形密度D定义为|D |=|E | V |（|V|-1).回想一下，在我们的例子中，发票图中的节点由公司表示，而EDGES表示公司之间的发票关系。在一个经济体中，一家公司与数量有限的对手进行互动，这让我们直观地知道为什么发票图是稀疏的。

考虑到graphdensity公式，我们对根据罗马尼亚管理和信息研究所提供的真实数据创建的发票图进行了模拟，事实上，我们观察到发票图是稀疏的。公司将发票上传到净额结算系统。定期更新图表，计算电路，并告知公司可能的网络。如果网络电路中的所有公司都批准和解，那么这些金额将从图表中删除。通过这种方式，公司减少了他们的共同义务。作为一个例子，图2概述了净额结算实施前后的净额结算场景。将四家公司（A、B、C、D）视为顶点，它们之间的负债标记在边上。ABCD回路中的边的最小值为600（介于A和D之间的边）。因此，所有这些公司之间可以实施600个净额结算。在nettingimplementation之后，从每条边的值中减去600。D对A的责任变为0。边缘AB、BC、CD上标记的可靠性为正值，可以参与其他网络电路。图2：联网实施示例计算联网电路的第一步包括识别发票图表中的强连接部件。本文中的方法是考虑Tarjan算法，该算法最初在[18]中介绍。如果所有顶点对之间都有一条路径，则有向图是强连通的（形式定义见[20]）。有向图的强连通分量（SCC）是最大强连通子图。因为发票图是一个稀疏图，为了有效地确定电路，我们必须首先找到图中的强连接组件，然后在每个组件上开始电路计算。