Algorithmus zur Bestimmung der Mindestzahlungen in einer Gruppe

8

Das Problem

Ich wurde vor kurzem gebeten, das geschuldete Geld unter einer Gruppe von Leuten zu berechnen, die zusammen eine Reise machten und auf ein interessantes Problem stießen: Da Sie die Beträge kennen, die jeder andere schuldet, ist ein allgemeiner Algorithmus zur Konsolidierung des Schulden zwischen Menschen, so dass nur die Mindestanzahl von Zahlungen vorgenommen werden muss? Nehmen Sie dies als Beispiel:

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

Wir können eine Zahlung zwischen Mike und John entfernen, indem wir die Schulden so umformulieren:

  • Mike schuldet John 0
  • John schuldet Rachel 100
  • Mike schuldet Rachel 500

Ich habe die Mathematik mit der Hand gemacht, weil es einfach genug war, aber dann hat es der Programmierer in mir gejagt, einen allgemeinen Algorithmus zu finden, um es für eine beliebig große Gruppe zu tun. Das scheint mir ein Graphalgorithmus zu sein, also fasse ich das als Graph um:

Wird als Diagramm angezeigt

  • Die Scheitelpunkte sind die Personen in der Gruppe
  • Die Kanten sind gerichtet und gewichtet nach dem geschuldeten Betrag. Zum Beispiel bedeutet eine Kante von Mike zu Rachel mit einem Gewicht von 500, dass Mike Rachel 500 schuldet.
  • Einschränkung: Die Nettosumme der Gewichte für jeden Knoten muss unverändert bleiben.
  • Das Ziel besteht darin, einen Graphen mit der Mindestanzahl von Kanten zu finden, die die Bedingung noch erfüllen.
alanlcode 22.07.2009, 04:48
quelle

7 Antworten

7

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.

    
ccipriano 22.07.2009, 05:28
quelle
15

Meine Meinung: Sie machen das zu kompliziert.

Denken Sie daran, wie ein "Pool" von Geld, und verlieren Sie die Beziehungen insgesamt:

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.

    
Andrew Shepherd 22.07.2009 04:58
quelle
5

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

    
nlucaroni 22.07.2009 13:39
quelle
4

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.)

    
shamp00 27.12.2011 09:57
quelle
4

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.
Wie immer habe ich Angst, dass ich mir bei den ersten beiden Schritten ziemlich sicher bin, bei den anderen weniger sicher. Auf jeden Fall klingt es wie ein Lehrbuchproblem; Ich bin sicher, da draußen gibt es eine "richtige" Antwort.

    
Michiel Buddingh 22.07.2009 05:28
quelle
1

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.

%Vor%

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.

    
Antti Huima 22.07.2009 07:00
quelle
0

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.

    
mbiron 16.02.2018 12:57
quelle

Tags und Links