Algorithmus zur Bestimmung der Mindestzahlungen in einer Gruppe

Es genügt nicht, nur die Empfänger und Geber herauszufinden. Während ich denke, dass diese Strategie auf dem richtigen Weg ist, stellt sie auch keinen Algorithmus sicher, um die geringste Menge an Zahlungen zu finden.

Zum Beispiel

• Person A schuldet 25
• Person B schuldet 50
• Person C schuldet 75
• Person D ist 100 geschuldet
• Person E ist 50
geschuldet

Es ist zwar offensichtlich, dass dies in 3 Zahlen gemacht werden kann (A und C bis D, B bis E). Ich kann mir keinen effizienten Algorithmus vorstellen, der dies für alle Problemstellungen erfüllt.

Besseres Beispiel,

• Person A schuldet 10
• Person B hat 49
• Person C schuldet 50
• Person D schuldet 65
• Person E ist geschuldet 75
• Person F ist geschuldet 99

Wenn wir den gierigen Ansatz nehmen würden, die Person D für F bezahlen zu lassen, würden wir mit einer suboptimalen Lösung im Gegensatz zum Optimalen enden (A & amp; D bis E, B & amp; C bis F).

Dieses Problem hat eine große Ähnlichkeit mit dem Problem mit der Behälterfüllung , das sich als NP-schwer erwiesen hat. Der einzige Unterschied besteht darin, dass wir mehrere Behälter unterschiedlicher Größe und die Bedingung haben, dass der Gesamtplatz in allen Behältern gleich der Gesamtgröße aller Artikel ist. Dies führt mich zu der Annahme, dass das Problem wahrscheinlich NP-schwer ist, aber mit den zusätzlichen Einschränkungen, die es möglich ist, in polynomischer Zeit zu lösen.

Meine Meinung: Sie machen das zu kompliziert.

Anstelle von:

• Mike schuldet John 100
• John schuldet Rachel 200
• Mike schuldet Rachel 400

Der Algorithmus muss nur denken:

• Mike schuldet 100
• John ist 100 geschuldet
• John schuldet 200
• Rachel ist 200 geschuldet
• Mike schuldet 400
• Rachel ist 400 geschuldet

Dies vernetzen:

• Mike schuldet 500
• John schuldet 100
• Rachel ist 600 geschuldet

Trennen Sie dies in eine Liste von "Gebern" und "Empfängern". Jeder Geber auf der Liste wird die Liste der Empfänger durchgehen und jedem Empfänger geben, was sie brauchen, bis der Geber bezahlt hat. Wenn ein Empfänger alles erhält, was er braucht, gehen sie von der Liste.

Später bearbeiten

Wie andere Poster festgestellt haben, vereinfacht dies das Problem. Es könnte jedoch eine optimale Reihenfolge der "Geber" - und "Empfänger" -Listen geben, aber wir haben noch keinen direkten Weg gefunden, diese Reihenfolge zu bestimmen.

Sehen Sie sich diesen Blogartikel an, " Optimal Account Balancing ", geht genau auf dein Problem ein.

In der Welt des Corporate Treasury ist dies als Zahlung oder Settlement Netting bekannt.

Multinationale Unternehmen haben in der Regel jeden Monat viele Zahlungsströme zwischen ihren Tochtergesellschaften, oft in verschiedenen Währungen. Sie können erhebliche Beträge einsparen, indem sie die Abrechnung dieser Flüsse optimieren. Normalerweise wird ein Unternehmen einmal im Monat eine solche Optimierung (ein Netting-Zyklus ) durchführen. Wenn es mehrere Währungen gibt, gibt es drei Quellen für Einsparungen:

• Banktransaktionsgebühren (weniger Zahlungen bedeuten geringere Gebühren)
• niedrigeres Float- und Erfüllungsrisiko bei Zinsen aufgrund der gestrafften Verarbeitung durch die Bank (das Geld verbringt weniger Zeit im Bankensystem)
• FX-Matching (viel weniger Fremdwährung wird ausgetauscht, weil das meiste davon "verrechnet" wird)

Es gibt zwei Möglichkeiten, die optimierte Abrechnung tatsächlich zu berechnen.

Bilaterales Netting ist die von @AndrewShepherd auf dieser Seite gut beschriebene Lösung. Bei einer grenzüberschreitenden Umsetzung kann dieser Ansatz jedoch rechtliche und administrative Probleme mit sich bringen, da jeden Monat unterschiedliche Grenzen überschritten werden.

Multilaterales Netting löst das Netzwerk durch Hinzufügen einer neuen Tochtergesellschaft namens Netting Center und leitet alle Beträge durch es um. Vergleichen Sie die Vorher-Nachher-Diagramme unten:

Vor dem Netting

Nach dem Netting

Obwohl dies einen weiteren Fluss als nötig hinzufügt (im Vergleich zum bilateralen Netting), sind die Vorteile:

• die Berechnung ist einfacher und das Ergebnis ist leichter zu visualisieren (auch gibt es nur eine Lösung im Gegensatz zum bilateralen Ansatz)
• Das Netting-Center wird zu einer unschätzbaren Ressource in Bezug auf die Ströme und FX-Exposure innerhalb der gesamten Gruppe
• Wenn das Netting-Center zum Beispiel in Deutschland ist, dann werden alle Rechtsfragen mit grenzüberschreitenden Zahlungen ein für allemal im Land des Netting-Centers behandelt (Zentralbank-Reporting, etc.)
• alle Devisen, die für die optimierte Abwicklung benötigt werden, können vom Netting Center
gekauft oder verkauft werden

(Auf der Basisebene ist die Berechnung einfach, aber es kann viele rechtliche und administrative Komplikationen geben, so dass Unternehmen häufig ein Netting-System von einem Softwareanbieter oder Service Provider entwickeln oder erwerben.)

Obwohl ich mit @Andrew übereinstimme, dass die Umwandlung in ein Grafikproblem wahrscheinlich zu kompliziert ist, bin ich nicht sicher, ob sein Ansatz die minimale Anzahl an Transaktionen ergibt. So löst man das Problem im wirklichen Leben, um sich Kopfschmerzen zu ersparen; einfach das Geld zusammenlegen.

Ein paar Schritte, die "richtig" erscheinen:

• Entfernen Sie alle Personen mit null Schulden; Sie müssen kein Geld von irgendwem senden oder empfangen.
• Kopple alle Geber und Empfänger mit gleichen geschuldeten Beträgen. Da die minimale Konnektivität pro Knoten von Nicht-Null-Schulden 1 ist, sind ihre Transaktionen bereits minimal, wenn sie sich gegenseitig bezahlen. Entferne sie aus dem Diagramm.
• Beginnen Sie mit der Person mit dem größten zurückzuzahlenden Betrag und erstellen Sie eine Liste aller Empfänger mit weniger als diesem Betrag. Probieren Sie alle Zahlungskombinationen aus, bis eine gefunden wird, die die meisten Empfänger mit einer Transaktion zufriedenstellt. "Save" die verbleibende Restschuld.
• Gehe zum nächsten Geber, usw.
• Ordnen Sie den verbleibenden Empfängern alle überschüssigen Schulden zu.

Wenn A, B und C jeweils $ 1 an D, E und F schulden, erstellt die Lösung "Liste" oder "Zentralbank" fünf Transaktionen (zB A, B, C - $ 3- & gt; D, D - $ 3- & gt; E, F), während die naive Lösung zu neun Transaktionen führt. Wenn A jedoch nur D, B nur E und C nur F verdankt, erzeugt die Zentralbanklösung noch fünf Transaktionen (A, B, C - $ 1- & gt; D, D - $ 1- & gt; E, F), während die beste Lösung benötigt nur drei (A - $ 1- & gt; D, B - $ 1- & gt; E, C - $ 1- & gt; F). Dies zeigt, dass die Lösung "Liste" oder "Zentralbank" im Allgemeinen nicht optimal ist.

Der folgende Greedy-Algorithmus kann verwendet werden, um bessere Lösungen für das Problem zu erstellen, aber sie sind nicht immer optimal. Lassen Sie "Schuld [i, j]" den Geldbetrag bezeichnen, den ich der Person j schulde; Anfangs wird dieses Array je nach Situation initialisiert.

Der Schlüssel dieses Algorithmus ist die Beobachtung, dass, wenn sowohl A als auch B Geld sowohl an C als auch an D schulden, anstelle der vier Transaktionen, die für Direktzahlungen erforderlich sind, B die Nettoverschuldung an A bezahlen kann, der sich um die Rückzahlung kümmern kann beide Darlehen von A und B.

Um zu sehen, wie dieser Algorithmus funktioniert, betrachte man den Fall, in dem A, B und C $ 1 zu jedem von D, E, F besitzen:

1. A überträgt die Schulden von A an B und zahlt $ 3 an B (eine Transaktion)
2. B überträgt die Schulden von B an C und zahlt $ 6 an C (eine Transaktion)
3. Nur C hat Schulden mehr; C zahlt 3 $ an D, E und F (drei Transaktionen)

Aber in dem Fall, wo A D schuldet, B E und C F schuldet, fällt der Algorithmus sofort auf die Zahlungsschleife, was zu der optimalen Anzahl von Transaktionen (nur drei) anstelle von fünf Transaktionen führt, die sich ergeben würden "Zentralbank" -Ansatz.

Ein Beispiel für Nicht-Optimalität ist, wenn A D und E schuldet, B E und F schuldet und C und F D (nehmen Sie für jede Schuld $ 1 an). Der Algorithmus kann die Kredite nicht konsolidieren, da sich nicht zwei Zahler zwei gemeinsame Zahlungsempfänger teilen. Dies könnte durch Ändern von "& gt; = 2" in der zweiten Zeile zu "& gt; = 1" behoben werden, aber dann würde der Algorithmus höchstwahrscheinlich sehr empfindlich für die Reihenfolge werden, in der die Schulden besichert sind.

Wie ein @Edd Barret feststellte, kann dies in etwa durch lineare Programmierung gelöst werden.   Ich habe einen Blogbeitrag geschrieben , in dem dieser Ansatz beschrieben wird, zusammen mit einem kleines R-Paket, das es implementiert.