Algorithmus gesucht: Ausgleich für wechselseitig vorgestrecktes Geld mit möglichst wenigen Zahlungen

Hallo zusammen,

ich bin auf der Suche nach einem Algorithmus.
In meinem Projekt möchte ich ein Programm entwickeln, wo vorgestrecktes Geld möglichst effektiv unter allen Beteiligten verteilt wird.
D.h. eine bestimmte Anzahl von Personen legt untereinander unterschiedliche Beträge aus und am Ende des Tages soll jeder die gleiche Summe ausgegeben haben. Dazu müssen Ausgleichszahlungen zwischen den Personen fließen. Die Anzahl der Ausgleichszahlung soll dabei für die Personen möglichst gering gehalten werden (Ziel des Algorithmus).
Hier kurz ein Beispiel:
4 Personen (P1;…;P4) strecken Geld vor:
P1 und P2 legen insg. 6 EUR bzw. 2 EUR UNTER dem Durchschnitt aus
P3 und P4 legen insg. 5 EUR bzw 3 EUR ÜBER dem Durchschnitt aus
-> P1 zahlt 5 EUR an P3 und 1 EUR an P4
-> P2 zahlt 2 EUR an P4

Ich hoffe ihr habt ein paar Ideen wie ich dies möglichst effektiv lösen könnte.
Danke für die Unterstützung!

Gruß tom86

Hallo tom86,

dafür kannst du jeden Optimierungsalgorithmus hernehemen. Hier sind die Ausgleichszahlungen zu Minimieren.
Z.B. [Artikel] Simulated Annealing. Als Fitnessfunktion/Gütefunktion/Energie wäre hier die Ausgleichszahlung zu verwenden.

BTW: Mit Sortieren hat das nichts zu tun. Hab daher den Titel angepasst.

mfG Gü

Hallo tom86,

bei n Personen (die echte Nettoschuldner oder Nettogläubiger sind) sind mindestens n/2 und maximal n-1 Zahlungen erforderlich.

Die erste Teilaussage sollte sofort einleuchten, denn mit jeder Zahlung können maximal zwei Personen gleichzeitig ihre Schulden bzw. ihre Außenstände loswerden, nämlich dann, wenn der eine exakt so viel schuldet, wie der andere an Außenständen hat.

Die zweite Teilaussage ergibt sich aus folgender Überlegung: Zu jedem Zeitpunkt muss irgendwer die geringsten Schulden bzw. die geringsten Außenständen (jeweils ungleich 0) haben. Mit einer Zahlung kann er sie loswerden, denn einen entsprechenden Gegenpart, der komplementär mindestens so hohe Außenstände bzw. Schulden hat, muss es aufgrund der genannten Voraussetzung immer geben. Durch diese Zahlung wird mindestens die Person mit den geringsten Schulden bzw. den geringsten Außenständen diese los. Wenn nur noch zwei Personen übrig sind, werden sie automatisch beide ihre gegenseitigen Verpflichtungen los. Also reichen immer n-1 Zahlungen.

Soviel Optimierungspotenzial gibt es also gar nicht. Man kann also maximal knapp die Hälfte der Zahlungen gegenüber den naiven Ansatz, immer die Person mit den geringsten Außenständen bzw. Schulden durch eine Zahlung das Ungleichgewicht los werden zu lassen, einsparen.

Um in diese Richtung zu gehen, kann man z.B. vor Beginn der Zahlungen (und ggf. auch nach jeder Zahlung) Paare bilden, bei denen die Schulden der einen Person exakt so hoch sind, wie die Außenstände der anderen Person. Der Schuldner jedes Paars zahlt dann vor Beginn der weiteren Berechnungen seinen Partner aus.

Außerdem kann man beim eigentlichen Algorithmus bei der Wahl des Gegenparts, also der Person, die gerade die geringsten Schulden bzw. die geringsten Außenständen hat, versuchen, diesen so zu wählen, dass seine Restschulden bzw. Restaußenstände 0 oder zumindest komplementär exakt genauso hoch werden, wie die Außenstände oder Schulden einer dritten Person und wenn dieses gelingt, die beiden letzteren direkt im Anschluss aneinander zahlen zu lassen.

Damit bekommt man zwar vielleicht nicht immer das 100%ig optimale Ergebnis, aber man hat einen einfachen Algorithmus und wird vermutlich mindestens nah dran sein. Der Grund-Algorithmus ist sogar so einfach, dass man ihn nicht mal implementieren muss, sondern ihn sogar mit den Beteiligten in einer Kneipe auf gegenseitigen Zuruf leicht und schnell durchexerzieren kann.

herbivore

Mein Ansatz wäre gewesen, immer denjenigen Partner zu suchen, bei dem die Differenz aus Forderung und Verbindlichkeit am geringsten wäre.

Aber trotzdem:

Wie würde denn das Optimierungskalkül für eine ganzzahlige Programmierung aussehen?

Müsste ich nicht ohnehin alle Transfermöglichkeiten darstellen, damit ich die Restriktionen genau abbilden kann?

Das wäre dann ja bei hohen Anzahl von Personen ein großer Aufwand.

Hallo ProgrammierTroll,

ich vermute auch, dass Optimierungen hier in einer hohen Aufwandsklasse liegen. Schon das (naive) vergleichen jeder Person mit jeder anderen, um festzustellen, ob zwei Personen komplementäre Beträge haben, liegt bei O(n), wobei man das im Schnitt auf O(n*log(n)) drücken kann, wenn man die Personen nach ihren Beträgen sortiert und dann per binärer Suche nach dem Gegenpart sucht.

Der native Algorithmus ohne Optimierungen bzw. mit der beschriebenen Optimierung sollte sich ebenfalls im Schnitt in O(n*log(n)) implementieren lassen sollte. Wenn man also alles so implementiert, wie vorgeschlagen und binäre Suche verwendet, dann hat man auch für sehr große Personenzahlen vertretbare Laufzeiten.

herbivore

Hallo herbivore,

nur einmal zur Klärung der Fachbegriffe: Was genau ist für dich ein Nettoschuldner? Ist das jemand, der für sich nicht auf ein Nullsummenspiel von Auslagen / ausstehendem Geld kommt? Ich kann den Begriff nur so auslegen, da sonst deine Aussage mit mindestens n/2 Transaktionen falsch wäre (A schuldet B einen Betrag x, B schuldet C x und C schuldet A x liefe auf 0 Transaktionen hinaus).

m0rius

Hallo m0rius,

Was genau ist für dich ein Nettoschuldner?

jeder der Teilnehmer muss in der Summe einen bestimmten Betrag zahlen (mal egal an wen) oder hat in der Summe einen bestimmten Betrag zu bekommen (mal egal von wem). Ein Nettoschuldner bzw. Nettogläubiger ist jemand, bei dem dieser Betrag ungleich von 0 ist. Die Leute, die dagegen eh schon ausgeglichen sind, also genau so viel ausgelegt haben, wie der Durchschnitt, also kein Geld mehr bekommen müssen und auch keins zahlen, kann man von vorne herein aussortieren (in deinem Beispiel trifft das auf alle drei zu) und sich nur auf die verbleibenden konzentrieren. Und für die verbleibenden ergeben sich die genannten Mindest- und Höchstwerte. So wars gemeint.

herbivore

Da man zwei Mengen hat (Zahler und Empfänger) wäre das ja eine Art lineares Zuordnungsproblem, das in seiner Grundform wie im angehängten Bild aussieht.

Kosten wären ja dann wohl die Differenzen von Forderung und Verbindlichkeit und die Restriktion müsste man entsprechend den möglichen Transfers konfigurieren.

PS: Könnte man nicht TeX im Forum integrieren?

Funktioniert doch nicht so gut.

Beispiel:

Person 3 muss 7€ zahlen.
Person 4 muss 8€ zahlen.

Person 1 erhält 3€.
Person 2 erhält 4€.
Person 5 erhält 2€.
Person 6 erhält 6€.

Minimize p = 4a+3b+5c+1d+5e+4f+6g+2h subject to
// a bedeutet Zahlung von P3 an P1
// b -"-                             P3 an P2
...
// e -"-                             P4 an P1
...
// h -"-                             P4 an P6


//Nebenbedinungen Zahlseite:
a+b+c+d=7
e+f+g+h=8

//Nebenbedingungen Empfangsseite:
a+e=3
b+f=4
c+g=2
d+h=6

Optimal Solution: p = 48; a = 0, b = 0, c = 1, d = 6, e = 3, f = 4, g = 1, h = 0

Bedeutet:

P3 -> P5: 1€
P3 -> P6: 6€

P4 -> P1: 3€
P4 -> P2: 4€
P4 -> P5: 1€

Ganz großes Damentennis! 5 Transkationen finden statt, obwohl die Sache auch mit 4 zu meistern wäre.

Hi,

hier bietet sich natürlich ein ganzzahliges lineares Programm an, (man müsste dann natürlich in Cent rechnen) was Programmiertroll bereits angegangen ist. Aber die Zielfunktion ist falsch gewählt.

4a+3b+5c+1d+5e+4f+6g+2h

Schließlich soll ja keine gewichtete Summe der Werte der Ausgleichszahlungen minimiert werden, sondern die Anzahl der Ausgleichszahlungen.

Die Variablen a bis h stehen ja für die Ausgleichszahlungen. Wird eine Ausgleichszahlung getätigt, ist sie positiv, sonst 0. Die Anzahl der getätigten (also positiven) Ausgleichszahlungen lässt sich also mit der Signum-Funktion relativ gut beschreiben:

sgn(a) + sgn(b) + sgn(c) + ... + sgn(h)

Und das soll minimiert werden.

Nur ist diese Zielfunktion leider nicht mehr linear von den Variablen abhängig. Aber die Trickkiste der ganzzahligen Optimierungen ist groß; ein Blick lohnt sich. Wir führen für sgn(a) (und die anderen Variablen auch) einfach je eine neue Variable ein. Nennen wir sie sa, sb, ... sh. Und es soll gelten:

sa = sgn(a)

In der ganzzahligen Welt können wir dies mit 4 neuen Bedingungen garantieren:

sa >= 0
sa <= 1

µ*sa >= a  // µ ist das Maximum aller Ausgleichszahlungen, oder einfach nur ein ausreichend großer Wert
sa <= a

Die ersten beiden garantieren, dass sa eine binäre Variable ist, also nur 0 oder 1 annehmen kann. Die letzten beiden garantieren, dass wenn a positiv ist, **sa **auch positiv ist (also gerade 1) und wenn a verschwindet, dass dann **sa **ebenfalls 0 ist - und umgekehrt.
Einfach mal durch den Kopf gehen lassen... ich mag solche "Tricks" 😉

Und minimiert wird dann:

sa + sb + sc + ... + sh

Insgesamt kommen zu den von ProgrammierTroll aufgeführten Constraints der Zahl- und Empfängerseite noch 4 neuen Ungleichungen pro möglicher Ausgleichszahlung hinzu. Da die Zahl der möglichen Ausgleichszahlungen in O(n^2) liegt, liegt die Zahl der Variablen und Constraints in der selben Ordnung, also wirklich relativ viel.
Aber rein formal lässt sich so das Problem beschreiben und mit einem passenden Solver natürlich auch lösen.

beste Grüße
zommi