外汇订单简化算法
这是一个几乎与语言无关的问题，而不是家庭作业。理想情况下，我会使用 C# 和/或 SQL 服务器来解决。
假设我有一个函数 GetExchangeRate(buyCurrency, sellCurrency)。因此，如果 1 英镑价值 1.6 美元，则 GetExchangeRate('GBP', 'USD') = 1.6 和 GetExchangeRate('USD', 'GBP') = 0.625 。
系统中的订单将表示为以下三元组：(buyCurrency, SellCurrency, buyCurrencyAmount)。因此，('GBP', 'USD', 125.00) 意味着无论花费多少美元都可以购买 125 英镑。
我的目标是节省交易成本并取消订单，包括传递性。对同一货币对之间的买入和卖出进行净额结算很容易做到，也很容易证明其合理性。这么说吧，我可能有业务原因来简化订单，我用美元购买英镑，用英镑购买欧元，等等......
我想间接地简化这组订单。我正在考虑构建一个图形数据结构（节点是货币，边是 buyCurrencyAmounts），即使数据将存储在 SQL 表中，并对此应用正确的算法。我想到首先做一个简单的netting，然后在DAG上进行拓扑排序，然后从顶部开始，然后按照拓扑顺序行走并将顺序“压缩”下来，例如简化它们。
问题是我不一定会有 DAG。但是，当我执行算法时，我可能会简化图结构，无论是哪种算法。
我应该为此使用什么正确的数据结构/算法？我应该担心由此产生的精度吗？有没有一些好的方法可以让我在旅途中不损失金钱？您能推荐一个可以处理这个问题的优秀 C# 库吗？仅使用 SQL Server 2008 尝试此操作会疯狂/低效/太多工作吗？
编辑： 交易支付的费用全部包含在价格（汇率）中。没有固定的固定费用或类似费用。
This is an almost language-agnostic question, and not a homework. Ideally I would use C# and/or SQL server for solution.
Suppose that I have a function GetExchangeRate(buyCurrency, sellCurrency). So, if 1 GBP is worth 1.6 USD, then GetExchangeRate('GBP', 'USD') = 1.6 and GetExchangeRate('USD', 'GBP') = 0.625.
The orders in the system will be represented as the following triplets: (buyCurrency, SellCurrency, buyCurrencyAmount). So, ('GBP', 'USD', 125.00) means buy 125 GBP with however many dollars it costs.
My goal is to save on transaction costs and cancel out the orders, including transitivity. Netting the buys and the sells between the same pair of currencies is easy to do, and easy to justify. Let's just say that I might have a business reason to simplify an order where I am buying GBP with USD, and also buying EUR with GBP, and so on ...
I want to simplify this set of orders transitively. I was thinking of building out a graph data structure (nodes are currencies and edges are buyCurrencyAmounts), even though the data would be stored in SQL tables, and applying the right algorithm to this. I thought of first doing a simple netting, followed by a topological sort on a DAG, followed by starting from the top, then walking in the topological order and "squeezing" the orders down, e.g. simplifying them.
The problem is that I will not necessarily have a DAG. But then, I will be likely simplifying the graph structure as I execute the algorithm, whichever one that will be.
What is the right data structure / algorithm that I should use for this? Should I be worried about the resulting precision? Are there some good approaches to not losing cents as I go? Can you recommend a good C# library that can handle this? Would it be crazy/inefficient/too much work to attempt this using only SQL Server 2008?
EDIT: The fees paid for transactions are all built into the price (exchange rate). There is no fixed flat fee or anything like that.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一种可能的技术是最小成本流。
确定每种货币的买卖量。
制作一个有向图，其中节点是货币，弧是货币之间可能的转换，弧成本捕获点差的影响（我假设列出的汇率非常有效，因此任何转换周期都会成倍增加）到 1)。
使用所描述的多项式时间算法之一来计算最小成本流。
One possible technique is minimum-cost flows.
Determine how much of each currency to buy and sell.
Make a directed graph where the nodes are currencies, the arcs are possible conversions between currencies, and the arc costs capture the impact of spreads (I'm assuming that the listed rates are perfectly efficient and thus that any cycle of conversions multiplies to 1).
Use one of the polynomial-time algorithms described to compute a minimum-cost flow.
您需要实施多边支付净额结算。 “技巧”是创建一个名为净额结算中心的新实体，并通过它重新路由所有付款。请参阅我对类似问题的回答此处了解此方法的优点。
转变
我们的目标是从这种情况（净额结算前）：
为这种情况 (< strong>净额结算后）：
每个子公司最终应获得一笔金额（要么用于支付，要么用于接收）从净额清算中心以本国货币计算其欠集团中任何其他实体的所有单独发票的对价总和。
基本算法是：
由于您只转换总额，因此舍入误差将最小化。任何舍入误差的结果都将计入净额中心账户。净额结算中心账户将包含货币小计，应与外汇银行进行交易，将其转换为基础货币，例如美元。所处理的汇率应该是净额计算中使用的汇率，因此一旦与外汇银行达成一致，就应该重新进行计算（并且总数将发生很小的变化）。
（使用多边而不是双边净额结算的优点之一是，任何此类外汇要求都是由同一个实体“要求”的，即 >，净额结算中心。此外，如果您选择收取点差，即，买入价和卖出价不同，那么由此产生的任何“利润”也将最终存入净额结算中心的账户。
关于执行实际计算 - 它足够简单，可以直接在 SQL 中执行，但您可能会发现有足够的合法和/或配置选项来保证更抽象的方法。
（例如法律问题：有些政府不允许在跨境交易中兑换外币；有些政府不允许您抵消付款和收入；有些需要中央银行的许可。一些有特殊要求的国家包括巴西、中国、马来西亚、俄罗斯等）。
You need to implement multilateral payment netting. The 'trick' is to create a new entity called the netting centre and re-route all payments through it. See my answer to a similar question here for the benefits of this approach.
The goal is to move from this situation (before netting):
to this (after netting):
Each subsidiary should end up with a single amount (either to pay or to receive) from the netting centre in their home currency which is the total of the countervalues of all the individual invoices they owe to any other entity in the group.
The basic algorithm is:
Rounding errors will be minimised because you will only be converting the totals. Any results of the rounding errors will end up in the netting centre accounts. The netting centre accounts will contain the currency subtotals which should be traded with an FX bank to convert them to a base currency, e.g., USD. The rates dealt should be the ones used in the netting calculation, so once agreed with the FX bank, the calculation should be redone (and the totals will change very slightly).
(One of the advantages of using multilateral instead of bilateral netting is that any such FX requirements are all 'required' by the same single entity, i.e., the netting centre. Also, if you choose to charge a spread, i.e., the buy and the sell rate differ, then any resulting 'profit' will also end up in the netting centre's account).
With regard to performing the actual calculation - it is simple enough to perform directly in SQL, but you may find there are enough legal and/or configuration options to warrant a more abstracted approach.
(For examples of legal issues: some governments do not allow conversion of foreign currencies in cross border transactions; others do not allow you to offset payments and receipts; some require permission from the central bank. Some countries with special requirements include Brazil, China, Malaysia, Russia, etc).
在我看来，将交易集视为图表过于复杂。只需获取您集合中的每笔交易并添加货币（即添加所有英镑买入/卖出、所有美元买入/卖出、欧元买入/卖出）。
您最终会获得每种货币所需的净买入/卖出。然后开始根据最低点差选择交易（即，如果您的欧元点差最低，则选择欧元交易 - 这可能会拉平一些欧元或一些美元），继续...
Sounds to me like thinking of the set of transactions as a graph is over complex. Just take every transaction in your set and add the currencies (i.e. add all GBP buy/sells, all USD buy/sells, EUR buy/sells).
You end up with the net buy/sell you want in each currency. Then just start picking out transactions based on the lowest spread (i.e. if you have lowest spread on EUR$ then pick out a EUR$ transaction - which may level some EUR or some $), continue...