Hochzeits-Tischordnung verständlich erklärt

Wer die Gäste einer Hochzeit so auf die Tische verteilt, dass die Summe aller Sympathien möglichst groß ist, lässt manchmal einen Gast zurück, bei dessen Tischnachbarn die Feindschaften überwiegen. Und kommt eine neue Feindschaft zwischen zwei Gästen am selben Tisch hinzu, wechselte in der Messung bei der Neuberechnung im Mittel knapp ein Fünftel der Gäste den Tisch. Die Seite zeigt das an erzeugten Gästelisten, stark vereinfacht.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Das Bild: Wer sitzt bei wem?

Stellen Sie sich eine Hochzeit vor. Die Gäste kennen sich unterschiedlich gut: Manche sind befreundet, manche können einander nicht ausstehen, bei vielen Paaren ist es egal. Jede Beziehung bekommt einen Punktwert. Freundschaften zählen plus, Feindschaften minus, und je stärker die Beziehung, desto größer der Betrag; die Skala reicht von minus fünf bis plus fünf. Die Gäste sollen auf mehrere Tische mit begrenzter Platzzahl verteilt werden. Zwei Gäste am selben Tisch bringen ihren Punktwert ein, zwei Gäste an verschiedenen Tischen zählen nichts.

Daraus lassen sich zwei Größen bilden. Das Glück eines Gastes ist die Summe der Punktwerte zu allen anderen Gästen an seinem Tisch. Die Gesamt-Summe zählt jedes Paar am selben Tisch einmal und sagt, wie harmonisch der ganze Saal sitzt. Das kleinste Glück unter allen Gästen heißt Mindest-Glück: der Gast, dem es am schlechtesten geht.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Die Gäste und ihre Beziehungen sind ausgedacht und zufällig erzeugt, es sind keine Daten von echten Hochzeiten. Die Zahlen zu Summe, Fairness und Änderung stammen aus einer Messreihe mit 30 solchen Gästelisten, jede mit 24 Gästen an 4 Tischen zu je 6 Plätzen. Tischzahl und Sitzfolge haben eigene Messreihen. Das vereinfachte Nachspielen nennen wir Rechenbild (Fachwort: Modell); alle Aussagen gelten nur für das Rechenbild.

Was passiert, wenn nur die Summe zählt?

Wer nur die Gesamt-Summe so groß wie möglich machen will, fragt nicht, wie sie sich auf die Gäste verteilt. Ein Beispiel, ausgedacht und nicht gemessen: Nehmen wir an, für einen Gast namens Erik gibt es zwei Möglichkeiten. Möglichkeit A: Er sitzt bei zwei Gästen, mit denen er verfeindet ist, jeweils mit minus 2. Das kostet die Gesamt-Summe 4 Punkte, und Eriks Glück ist minus 4. Möglichkeit B: Er sitzt bei Fremden, aber dafür muss ein befreundetes Paar mit dem Wert 5 getrennt werden. Das kostet die Gesamt-Summe 5 Punkte, Eriks Glück ist null. Wer nur die Summe zählt, wählt A und lässt Erik bei seinen Feinden sitzen, obwohl B nur einen Punkt mehr kostet.

Passiert das wirklich? In der Messreihe mit 30 erzeugten Gästelisten hatte der Schlechtestgestellte bei der besten gefundenen Aufteilung nach der Gesamt-Summe (der Summen-Lösung; bei gleicher Summe wurde die mit dem größeren Mindest-Glück genommen) in 2 von 30 Listen ein Glück unter null; bei anderer Behandlung gleicher Summen können es mehr sein. Beide gehören zur Art ohne feste Familien, bei der vier von fünf Paaren eine Beziehung haben. In den 15 Listen mit Familien kam es in keiner vor.

Was hilft: ein kleiner Verzicht

Man kann das Mindest-Glück gezielt heben, die Verteilung also gerechter machen (Fachwort: Fairness), indem man etwas Gesamt-Summe opfert. Die Regel: Die Gesamt-Summe darf höchstens 5 % unter dem besten bekannten Wert liegen, und innerhalb dieser Grenze wird das Mindest-Glück so groß wie möglich gemacht. Der beste bekannte Wert ist der beste aller Suchläufe, nicht bewiesen optimal. In der Messung stieg das größtmögliche Mindest-Glück mit dieser Regel in 15 von 25 Listen um mindestens 2 Punkte gegenüber der Summen-Lösung; gezählt werden nur die 25 Listen, in denen ein Rechenprogramm diesen Höchstwert sicher nachweisen konnte.

Das ist keine Zauberformel. Verlangt man nur ein möglichst großes Mindest-Glück und gar keine Grenze für die Summe, behält die Lösung im Durchschnitt nur rund 82 % der besten Summe. Wie teuer Fairness wird, hängt also von der Regel ab: Gibt es mehrere gleich gute Lösungen (Gleichstände), kann man die fairste nehmen, und eine Grenze für die Summe ist ein Nebenziel, das den Preis begrenzt. Die Zahlen schwanken außerdem je Messlauf etwas.

Was kostet eine Änderung?

Nun ändert sich die Gästeliste: Zwei Gäste, die in der Summen-Lösung am selben Tisch sitzen, werden plötzlich zu Feinden, mit dem stärksten Wert minus fünf. Rechnet man die Tischordnung neu, müssen im Durchschnitt knapp ein Fünftel der Gäste den Tisch wechseln. Der mittlere Wert aller Fälle (Median) liegt bei 4 von 24 Gästen. Wie viele Gäste wechseln, nennen wir den Versatz.

Dabei wäre die alte Aufteilung, wenn man sie einfach behielte, in der Messung im Durchschnitt nur um einen kleinen Anteil der neuen Summe schlechter als die beste neue. Diesen Anteil nennen wir Verlust (genaue Werte im Fachteil). Man kann den Umzug auch bestrafen: etwa drei Strafpunkte für jeden Gast, der den Tisch wechselt. In der Messung wechselte dann im Durchschnitt praktisch niemand mehr, während der Verlust fast gleich blieb.

Erstens ist der Versatz eine Obergrenze des nötigen: Es kann mehrere gleich gute Aufteilungen geben, verglichen wird nur mit den gefundenen, und die Tische dürfen dabei beliebig umbenannt werden. Zweitens ist der Versatz meist nicht bloß Rauschen der Suche: In fast allen Listen fanden zwei unabhängige Läufe ohne jede Änderung mindestens eine gemeinsame beste Aufteilung, und der Versatz lag in den meisten Änderungen darüber.

Wie viele Tische braucht man?

Eine zweite Frage betrifft die Zahl der Tische, mit einer strengeren Regel: Bestimmte Paare dürfen unter keinen Umständen zusammensitzen (Fachwort: harte Feindpaare). Dann braucht man mindestens so viele Tische, wie die Platzzahl verlangt: bei 24 Gästen und 6 Plätzen je Tisch vier. In dieser eigenen Messreihe änderte ein einzelnes zusätzliches Feindpaar die Mindestzahl der Tische in keinem der geprüften Fälle (allgemein kann auch ein einzelnes Paar die Tischzahl ändern, etwa bei einem Tisch mit nur zwei Plätzen). Eine ganze Familienfehde, bei der sich alle Mitglieder zweier Familien nicht vertragen, änderte sie in einem kleinen Teil der Fälle; die Zählung steht im Fachteil.

Warum? Eine Deutung, nicht gemessen: Verfeindete Familien dürfen sich keinen Tisch teilen, die Familien haben unterschiedliche Größen, und die Tische lassen sich dann nicht immer lückenlos füllen, wie Kisten verschiedener Größe in Kartons. Dann wird ein Tisch zusätzlich gebraucht.

Erst die Tische, dann die Sitzfolge?

Ein anderes Ziel: Bisher zählte nur, wer am selben Tisch sitzt. Sitzen die Gäste an einem runden Tisch im Kreis und zählen nur die beiden Nachbarn, kommt es auch auf die Reihenfolge an. Man könnte erst die Tische festlegen und danach für jeden Tisch die beste Reihenfolge suchen. In der Messung war dieses zweistufige Vorgehen in mindestens 22 von 24 erzeugten Gästelisten schlechter, als Tische und Reihenfolge gemeinsam zu planen; die gemeinsame Planung ist selbst nur eine gefundene Lösung, der Verlust also mindestens so groß. Das gilt für dieses Nachbarschafts-Ziel, nicht für jede Bewertung.

Häufige Missverständnisse

• „Die größte Gesamt-Summe ist die gerechteste Tischordnung.“ Nicht unbedingt: In 2 von 30 Listen hatte der Schlechtestgestellte bei der Summen-Lösung ein Glück unter null.

Was Sie mitnehmen

• Eine große Gesamt-Summe sagt nichts darüber, wie es dem Schlechtestgestellten geht: Fragen Sie nach beidem.
• Eine Änderung kann viele Umzüge auslösen, obwohl die alte Aufteilung kaum schlechter wäre: Fragen Sie, was ein Umzug kostet.

Wie ernst ist das Modell zu nehmen?

Alle Beziehungen sind erzeugt; Punktwerte, Familien und Anteile sind Annahmen, die Zahlen gelten nur für diese erzeugten Listen, nicht für echte Gästelisten. In ihnen zeigt sich die Abwägung zwischen Summe, Mindest-Glück und Umzügen; eine Vorhersage für eine bestimmte Hochzeit ist das nicht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst das Modell der Demo zusammen, eines Programms zum Ausprobieren im Browser (Knopf unten). Alle Beziehungen sind erzeugt, es sind keine Hochzeitsdaten; Gewichte, Familien und Anteile sind Annahmen. „Rechnung dieser Seite“ kennzeichnet Zahlen, die hier nachgerechnet sind und nicht in der Beschreibung der Demo stehen.

• Modell: Gäste sind Knoten, \(W_{ij}\) ist ein ganzzahliges Kantengewicht beider Vorzeichen, gesucht ist eine Zerlegung der Gäste in höchstens \(k\) Gruppen (Tische) mit je höchstens \(C\) Gästen. Fachbegriffe dafür: kapazitiertes Clique-Partitioning (Clique-Partitioning: Grötschel und Wakabayashi 1989) und Korrelationsclustering mit Tischgröße (Korrelationsclustering: Bansal, Blum und Chawla 2004); die Aussagen dieser Arbeiten verwendet die Seite nicht. Der Bezug zur Clusteranalyse: Gruppen entstehen hier aus Beziehungen mit beiden Vorzeichen statt aus Abständen von Datenpunkten, Anziehung und Abstoßung wirken zugleich.
• Gewichte und Tische: \(n\) Gäste, höchstens \(k\) Tische zu je höchstens \(C\) Plätzen mit \(k = \lceil n / C \rceil\) plus einer einstellbaren Reserve. Das Gewicht ist ganzzahlig, symmetrisch, Freund 1 bis 5, Feind −1 bis −5; jedes Paar hat höchstens eine Beziehung.
• Erzeugung: Bei „Familien“ gibt es Gruppen von etwa 6 Gästen; innen hat ein Paar mit Wahrscheinlichkeit 0,8 eine Beziehung (überwiegend Freunde), zwischen den Familien mit der gewählten Dichte und einem gegenüber dem Reglerwert erhöhten Feindanteil. Weil innerhalb der Familien überwiegend Freunde stehen, liegt der Feindanteil über alle Beziehungen gerechnet im Mittel bei etwa 7 %, obwohl der Regler auf 10 % steht. Bei „strukturlos“ hat jedes Paar unabhängig von den anderen mit der Dichte eine Beziehung.
• Instanzmenge der Messung (Summe, Fairness, Änderung): 30 Instanzen mit 24 Gästen an 4 Tischen zu je 6, Zufalls-Seeds 1 bis 15, je 15 Instanzen „Familien“ (Regler Dichte 15 % und Feindanteil 10 %) und „strukturlos“ (Dichte 80 %, Feindanteil 40 %), ganzzahlige Gewichte −5 bis 5. Die Nenner wechseln, weil nicht überall dasselbe gezählt wird: 30 sind alle Instanzen, 25 die Instanzen, in denen CP-SAT bei einer Summen-Untergrenze von 95 % den Wert beweisen konnte. Die Tischzahl-Messung und die Sitzfolge-Messung sind eigene Reihen (siehe unten).
• Ziele: die Summe (Gesamt-Glück maximieren), die Fairness (Maximin: das kleinste Glück maximieren, mit der Summe als Untergrenze, die ein gewählter Anteil der besten bekannten Summe ist; Formel unten) und die Änderung (Neuberechnung nach einer neuen Feindschaft, mit Umzugsstrafe).
• Verfahren: Lokalsuche (wiederholt den besten Zug, einen Gast verschieben oder zwei Gäste tauschen, bis keiner die Summe erhöht; 30 Starts), Annealing (zufällige Züge, schlechtere werden mit sinkender Wahrscheinlichkeit angenommen), CP-SAT (ganzzahliger Löser mit Beweis-Status: OPTIMAL heißt bewiesen, FEASIBLE heißt Zeitgrenze erreicht) und für die Sitzfolge am runden Tisch Held-Karp (dynamische Programmierung, ausgeführt bis 12 Plätze). Bis 24 Gäste verbessert CP-SAT die Fairness-Lösung der Heuristik nach (Zeitgrenze 5 s bei der Nachbesserung in der App, 20 s im Tab Exakt, 30 s in der Messreihe); darüber ist die Fairness-Lösung eine Heuristik.

Die Formeln

Gäste \(i = 1,\dots,n\), Tische \(t = 1,\dots,k\) mit Platzzahl \(C\), Beziehungsgewicht \(W_{ij} = W_{ji} \in \{-5,\dots,5\}\); \(x_{it} = 1\), wenn Gast \(i\) an Tisch \(t\) sitzt. Jeder Gast sitzt an genau einem Tisch, kein Tisch hat mehr als \(C\) Gäste, und \(y_{ij}\) zeigt an, ob zwei Gäste am selben Tisch sitzen:

\[\sum_{t} x_{it} = 1 \;\; \forall i, \qquad \sum_{i} x_{it} \le C \;\; \forall t, \qquad y_{ij} = \sum_{t} x_{it}\, x_{jt}\]

Das Gesamt-Glück \(F\) zählt jedes Paar am selben Tisch einmal, das Glück \(h_i\) eines Gastes ist die Summe seiner Gewichte zu den Gästen am selben Tisch:

\[F = \sum_{i<j} W_{ij}\, y_{ij}, \qquad h_i = \sum_{j \ne i} W_{ij}\, y_{ij}\]

Die Summe maximiert \(F\). Die Fairness (Maximin) maximiert das kleinste Glück \(\min_i h_i\) mit der Summe als Untergrenze; \(F^{*}\) ist die beste bekannte Summe und \(s\) der Fairness-Anteil (in der App 0,8 bis 1). Die Untergrenze gilt gegen \(F^{*}\), nicht gegen ein bewiesenes Optimum der Summe; die Untergrenze \(s \cdot F^{*}\) ist für ein positives \(F^{*}\) gedacht.

\[\max z \quad \text{u. d. N.} \quad z \le h_i \;\; \forall i, \qquad F \ge s \cdot F^{*}\]

Bei der Änderung wird die neue Feindschaft \(W_{ab} \leftarrow -5\) gesetzt und mit der Umzugsstrafe \(p\) und der alten Aufteilung \(x^{0}\) neu gerechnet; der senkrechte Strich zählt die Elemente der Menge, also die Gäste, die den Tisch wechseln. Die Tische sind nicht unterscheidbar; die in der App gemeldete Zahl der Wechsler wird nach bester Zuordnung der neuen zu den alten Tischen gezählt, das Annealing der Strafe rechnet mit festen Tischnamen.

\[\max_x \; F(x) - p \cdot \bigl|\{ i : \text{Tisch}_x(i) \ne \text{Tisch}_{x^{0}}(i) \}\bigr|\]

Für die Sitzfolge am runden Tisch gilt Held-Karp: \(D(S, j)\) ist das größte Gewicht eines Weges von Gast 0 über alle Gäste der Menge \(S\), der bei \(j\) endet; das Kreisgewicht schließt zurück zu Gast 0. Genauer, wie die Demo es rechnet: \(S\) enthält nicht den Gast 0 (er ist der Startpunkt), der Anfangswert ist \(D(\{j\}, j) = W_{0j}\), und „alle“ sind alle Gäste des Tisches außer Gast 0; bei nur zwei Gästen am Tisch zählt der Kreis eine Kante. Das Nachbarschafts-Ziel zählt nur Gäste nebeneinander.

\[D(S, j) = \max_{i \in S \setminus \{j\}} \bigl( D(S \setminus \{j\}, i) + W_{ij} \bigr), \qquad \text{Kreisgewicht} = \max_{j} \bigl( D(\text{alle}, j) + W_{j0} \bigr)\]

Durchgerechnet: vier Gäste, zwei Tische

Rechnung dieser Seite, in der Demo nicht gemessen. Vier Gäste A bis D, zwei Tische zu je 2 Plätzen (\(n = 4\), \(k = 2\), \(C = 2\)). Gewichte: \(W_{AB} = 5\), \(W_{CD} = -1\), \(W_{AC} = 2\), \(W_{BD} = 2\), \(W_{AD} = W_{BC} = 0\). Es gibt genau drei Aufteilungen in zwei Paare; an jedem Tisch ist das Glück eines Gastes das Gewicht zu seinem Gegenüber:

• A B | C D: \(F = 5 + (-1) = 4\); Glück 5, 5, −1, −1, also Mindest-Glück −1.
• A C | B D: \(F = 2 + 2 = 4\); Glück 2, 2, 2, 2, also Mindest-Glück 2.
• A D | B C: \(F = 0 + 0 = 0\); Mindest-Glück 0.

Die ersten beiden Aufteilungen haben dieselbe Summe 4, sind also beide Summen-Lösungen; sie unterscheiden sich im Mindest-Glück (−1 gegen 2). Welche als Summen-Lösung gilt, hängt von der Behandlung der Gleichstände ab: Die Demo entscheidet bei gleicher Summe zugunsten des größeren Mindest-Glücks, nach dieser Regel also für A C | B D (am Beispiel gerechnet, nicht in der App ausgeführt). Hier kostet Fairness nichts.

Ein Zielkonflikt: Setzt man nur \(W_{AC} = 1\) statt 2 (alles andere gleich), hat A C | B D die Summe \(1 + 2 = 3\) und das Mindest-Glück 1, A B | C D bleibt bei Summe 4 und Mindest-Glück −1. Die beste bekannte Summe ist \(F^{*} = 4\). Bei einem Fairness-Anteil von 75 % (nur zur Rechnung; der Regler der Demo reicht von 80 bis 100 %) ist \(F \ge 3\) verlangt, und A C | B D ist zulässig: ein Viertel weniger Summe (3 statt 4), dafür Mindest-Glück 1 statt −1. Bei 80 % wäre \(F \ge 3{,}2\) verlangt, A C | B D wäre nicht zulässig, und die Summen-Lösung bliebe die einzige zulässige Aufteilung mit Mindest-Glück −1.

Wie groß ist der Suchraum?

Rechnung dieser Seite: 24 Gäste lassen sich auf \(24! / ((6!)^4 \cdot 4!)\) = 96.197.645.544 Arten in vier nicht unterscheidbare Tische zu je 6 Gästen aufteilen. Alles durchzuprobieren scheidet damit aus; die Tests der Demo zählen deshalb nur kleine Instanzen vollständig auf (8 Gäste) und vergleichen Lokalsuche, Annealing und CP-SAT mit dieser Aufzählung, dazu eine Mengenpartitionierung mit HiGHS (ein Löser für lineare und ganzzahlige Programme; jede zulässige Tischbelegung ist eine Spalte, 9 Gäste) als zweiten Rechenweg.

Befunde: Fairness

Alle Zahlen dieses und des nächsten Abschnitts stammen aus einer vorgerechneten Messreihe (Zeiten und Zufall fest, CP-SAT mit Zeitgrenze 30 s je Frage) über die oben beschriebene Instanzmenge: 30 Instanzen mit 24 Gästen an 4 Tischen zu je 6. Die Zahlen gelten für diese erzeugten Instanzen und die abgelegte Messreihe (zwei frühere Messläufe lagen etwas anders), nicht für echte Gästelisten. Die Summen-Lösung ist die der App (bei gleicher Summe das größere Mindest-Glück). „Bewiesen“ heißt: CP-SAT hat den Wert als größtmöglich ausgewiesen. Die Summen-Untergrenze von 95 % und 90 % bezieht sich auf die beste bekannte Summe, nicht auf ein bewiesenes Optimum.

Frage	Befund
Ist das Mindest-Glück beweisbar?	CP-SAT beweist das größte Mindest-Glück ohne Nebenziel in 30 von 30 Instanzen. Unter einer Summen-Untergrenze von 95 % der besten bekannten Summe gelingt der Beweis in 25 von 30, bei 90 % in 30 von 30. Zwei frühere Messläufe bewiesen bei 95 % nur 21 und 23: Die Zahl der Beweise hängt an der Rechnerlast und der Zeitgrenze. In der App gelten kürzere Zeitgrenzen (5 s bei der Nachbesserung, 20 s im Tab Exakt); dort kann die Zahl der Beweise niedriger sein (nicht gezählt, nicht in den Tests).
Lässt die Summen-Lösung Gäste zurück?	In 2 von 30 Instanzen steht der Schlechtestgestellte der Summen-Lösung unter null (−9 und −3). Beide Instanzen sind „strukturlos“ (Zufalls-Seeds 2 und 5), in jeder steht genau ein Gast unter null; in den 15 Familien-Instanzen kommt es in keiner vor.
Was kostet Fairness?	Bei höchstens 5 % weniger Summe steigt das Mindest-Glück in 15 von 25 Instanzen mit bewiesenem Wert um mindestens 2 Punkte (größter Anstieg 13, ein Ausreißer; sonst höchstens 7). Der Nenner 25 zählt nur Instanzen, die CP-SAT bei 95 % beweisen konnte; die schwierigeren fehlen. Bei höchstens 10 % sind es 22 von 30 (Nenner 30: bei 90 % gelang der Beweis in allen; größter Anstieg 13); die Brüche haben verschiedene Grundgesamtheiten. In den früheren Messläufen waren es 12 von 21 und 14 von 23, rund 60 % der bewiesenen Instanzen.
Hängt das am Nebenziel?	Ja. Maximiert man das Mindest-Glück ohne Nebenziel, behält die Lösung im Mittel rund 82 % der besten Summe (kleinster Wert 64 bis 66 % je nach Messlauf, größter 96 %; welches von mehreren gleich guten Optima CP-SAT liefert, ist zufällig). Mit einer Summen-Untergrenze von 90 % bleibt sie per Konstruktion darüber. Das Ergebnis hängt also an der Behandlung der Gleichstände und Nebenziele.
Trifft die Heuristik den bewiesenen Wert?	Nur teilweise. Die Heuristik allein (ohne CP-SAT) liegt bei 95 % in 16 von 25 und bei 90 % in 13 von 30 bewiesenen Instanzen auf dem CP-SAT-Wert, sonst darunter (9 bzw. 17). Deshalb verbessert CP-SAT die Fairness-Lösung bis 24 Gäste.

Befunde: Änderung, Tischzahl, Sitzfolge

Die Änderung rechnet auf derselben Instanzmenge (30 Instanzen mit 24 Gästen). Die Tischzahl-Messung ist eine eigene Reihe mit harten Feindpaaren, also Paaren, die nie am selben Tisch sitzen dürfen (n = 24 mit 6 Plätzen und n = 48 mit 8 Plätzen, volle und nicht ganz volle Tische, Zeitgrenze 5 s je Zulässigkeitsfrage; gemeint ist die Frage, ob sich alle Gäste auf die gegebene Zahl Tische verteilen lassen, ohne ein hartes Paar zusammenzusetzen). Jedes zusätzliche Paar wird einzeln zur Ausgangsinstanz hinzugefügt und für sich gegen deren Mindesttischzahl geprüft; je Instanz sind das nach dem Skript der Demo bis zu 20 einzelne Paare bzw. bis zu 15 einzelne Fehden, daher 1440 (72 mal 20) und 1333 (weniger als 96 mal 15; nicht für jede Instanz standen 15 Fehden zur Wahl oder wurden gelöst). Der Fehde-Anteil ist laut dem Skript der Anteil der Familienpaare, die verfeindet sind. Die Sitzfolge rechnet auf 24 Instanzen mit 24 Gästen an 4 Tischen zu je 6, vier Beziehungs-Einstellungen mit je 6 Zufalls-Seeds; zwei der vier Einstellungen (Familien mit Dichte 15 % und Feindanteil 10 %, strukturlos mit Dichte 80 % und Feindanteil 40 %; Seeds 1 bis 6) sind dieselben Gästelisten wie in der Messreihe oben (Abgleich der gespeicherten Summen durch die Prüfung dieser Seite, nicht in der Beschreibung der Demo).

Frage	Befund
Was kostet eine Änderung?	Eine neue Feindschaft (−5) zwischen zwei Gästen am selben Tisch versetzt bei Neuberechnung im Mittel 19,6 % der Gäste. 180 Änderungen, sechs je Instanz; Median 4 von 24, größter Versatz 14. Die alte Aufteilung zu behalten kostet im Mittel 2,9 % der neuen Summe (größter Wert 7,8 %). Der Versatz ist eine Obergrenze des nötigen: Es kann mehrere gleich gute Aufteilungen geben, und nur die gefundenen werden verglichen.
Was bringt eine Umzugsstrafe?	Sie senkt den Versatz fast auf null, der Verlust sinkt kaum. Mit Umzugsstrafe 3 wechseln im Mittel 0,4 % der Gäste bei 2,7 % Verlust gegen die beste neue Summe (ohne Strafe 2,9 %); in 172 von 180 Änderungen wechselt niemand, in den übrigen 8 wechseln zwei Gäste (Zählung dieser Seite, nicht in den Tests der Demo). Bei Summen um 145 Punkten (Mittel der Messreihe) kostet das Behalten im Mittel etwa 4 Punkte (2,9 % von 145), also etwas mehr als die Strafe von 3 Punkten für einen einzigen Wechsler.
Wie weit liegt der Versatz über dem Suchrauschen?	Meist darüber. Das Suchrauschen (zwei unabhängige Läufe ohne Änderung; 0 heißt, dass beide mindestens eine beste Aufteilung gemeinsam haben) ist in 29 von 30 Instanzen 0, in einer 8 Gäste; der Versatz liegt in 148 von 180 Änderungen darüber. Das gilt für 24 Gäste, für kleinere Größen gibt es keine Messung; bei 48 Gästen zeigte die Vormessung 13 bis 26 Gäste Suchrauschen in 9 von 10 Instanzen (nicht in den Tests der Demo).
Ändert ein Feindpaar die Tischzahl?	Bei den zufälligen Instanzen änderte ein einzelnes Feindpaar die Tischzahl nie, eine Familienfehde kann es. Einzelne zufällige Feindpaare: In 72 von 72 Instanzen ist die Mindesttischzahl das Aufgerundete von \(n\) durch Plätze, und 0 von 1440 zusätzlichen Feindpaaren ändern sie. Ganze Familienfehden: 7 von 96 Instanzen brauchen mehr Tische, 18 von 1333 zusätzlichen Fehden ändern die Tischzahl (9 von 217 bei vollen Tischen und Fehde-Anteil 0,5). Dass das Aufrunden die Ursache ist, ist eine Deutung, nicht gemessen. Als allgemeine Regel gilt „ein Feindpaar ändert die Tischzahl nie“ nicht: Bei zwei Gästen und einem Tisch mit 2 Plätzen genügt schon ein einziges Paar für einen zweiten Tisch.
Ist erst Tische, dann Reihenfolge schlechter?	In mindestens 22 von 24 Instanzen, beim Nachbarschafts-Ziel. Zweistufig (Tische nach „am selben Tisch“, dann beste Reihenfolge) ist in 22 von 24 Instanzen schlechter als die gemeinsame Optimierung, im Mittel um 6,3 % (0 bis 16,2 %). Die gemeinsame Lösung ist die beste von 7 Lokalsuchen (die zweistufige Lösung als Start und sechs zufällige), also selbst nur eine gefundene Lösung: In den übrigen 2 Instanzen fand die Suche nichts Besseres, und der wahre Verlust ist mindestens so groß wie gemessen.

Was die Messung zeigt und was nicht

Belegt:

• Der Kern der Rechnung ist gegen unabhängige Wege geprüft: eine Handrechnung an einer Mini-Instanz (6 Gäste, 2 Tische zu 3; Summe 17, Mindest-Glück 3), die Vollaufzählung aller Aufteilungen für 8 Gäste gegen Lokalsuche, Annealing und CP-SAT (Summe, Maximin und Maximin unter Summen-Untergrenze), die Mengenpartitionierung mit HiGHS und Held-Karp gegen alle Reihenfolgen.
• Die Tests der Demo zählen die Zahlen der Tabellen aus der gespeicherten Messreihe nach, mit festen Zufalls-Seeds; Prozente und Mittel gelten als Bänder. Ausgenommen sind die Werte früherer Messläufe, die Zeitgrenzen der App, die Vormessung und „sonst höchstens 7“ sowie „Summen um 145 Punkten“: Sie stehen nicht in den Tests. Nicht in der Demo stehen die Beispiele mit vier Gästen, die Zahl der Aufteilungen und die Zählung 172 von 180, die diese Seite selbst rechnet.
• Im Messaufbau (24 Gäste, erzeugte Beziehungen) lässt die Summen-Lösung in 2 von 30 Instanzen (beide „strukturlos“) einen Gast unter null zurück, ein kleiner Verzicht auf Summe hebt das Mindest-Glück in 15 von 25 bewiesenen Instanzen um mindestens 2 Punkte, und eine neue Feindschaft versetzt im Mittel 19,6 % der Gäste.

Belegt nicht:

• Eine Aussage über echte Hochzeiten. Gewichte, Familiengröße, Dichten und Feindanteile sind Annahmen; ob echte Listen dichter oder dünner sind, ist offen. Keine Sitznähe zum Brautpaar, keine Alters- oder Familienstruktur über die erzeugten Familien hinaus, keine Tischformen, kein Einlesen eigener Listen.
• Ein bewiesenes Optimum der Summe. Sie ist der beste Wert aller Läufe; bewiesen wird sie nur im Tab Exakt der Demo und nur bis 24 Gäste, und dort oft nicht (eine Zählung gibt es nicht); das Mindest-Glück der Fairness-Lösung weist die Demo bis 24 Gäste mit Beweis-Status aus. Standard-Ganzzahlmodelle enden früh (so ein SAS-Blogbeitrag von 2014, den die Beschreibung der Demo nennt; er ist kein Fachaufsatz und wurde hier nicht nachgeschlagen). Spaltenerzeugung (Branch-and-Price) ist nicht umgesetzt.
• Die Fairness über 24 Gäste hinaus. Sie ist dort eine Heuristik und liegt bei einem Teil der Instanzen unter dem bewiesenen Wert; die Prozentzahlen hängen von der Behandlung der Gleichstände ab, und sie sind je Messlauf etwas verschieden (Spannen in der Tabelle).
• Eine feste Größe für „was Fairness kostet“. Die Zählung 15 von 25 ist eine Eigenschaft dieser Instanzmenge mit nur 30 Instanzen; die Vormessung ergab 4 von 10 Instanzen mit mindestens 2 Punkten bei höchstens 5 % Verzicht (nicht in den Tests). Beide Messungen zeigen Instanzen mit Gewinn, der Anteil unterscheidet sich.
• Den nötigen Versatz. „Gäste versetzt“ ist eine Obergrenze und bei 24 Gästen gemessen; für kleinere Größen liegt keine Messung vor, bei 48 Gästen streute die Suche in der Vormessung selbst (nicht in den Tests der Demo).
• Eine allgemeine Aussage „ein Feindpaar ändert die Tischzahl nie“ (sie gilt nur für die zufälligen Instanzen der Messung), die Ursache der Tischzahl-Befunde (Aufrunden) und die Wirkung harter Feinde auf das Summenziel: Die Kombination aus harten Feinden und Summenziel ist nicht gemessen; harte Feindpaare stehen nur in der Tischzahl-Messung.
• Eine Bewertung echter Sitzordnungen am runden Tisch. Das Nachbarschafts-Ziel ist ein Modell; der Verlust der zweistufigen Lösung hängt an diesem Ziel, und die zweistufige Lösung nimmt die Tische der Summen-Lösung.

Quellen

• Bansal, N., Blum, A., Chawla, S. (2004): Correlation clustering. Machine Learning.
• Grötschel, M., Wakabayashi, Y. (1989): A cutting plane algorithm for a clustering problem. Mathematical Programming.
• Lewis, R., Carroll, F. (2016): Creating seating plans: a practical application. Journal of the Operational Research Society.
• Sørensen und Letchford (2024): als Quelle in der Beschreibung der Demo genannt, dort ohne Titel; hier nur Autoren und Jahr.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/tischordnung-demo.

Laut der Beschreibung der Demo wurden alle vier Arbeiten nur nach Titel oder Abstract gesehen; die Demo stützt keine Aussage auf ihren Volltext, und diese Seite tut es ebenso nicht. Autoren, Titel und Zeitschrift der ersten drei Arbeiten wurden für diese Seite per Websuche bestätigt; zu Sørensen und Letchford wurde kein Titel bestätigt. Die Aussage zur Spaltenerzeugung stammt aus einem SAS-Blogbeitrag von 2014 und nicht aus diesen Arbeiten; er wurde nicht nachgeschlagen. Alle Zahlen der Seite stammen aus der Beschreibung der Demo, außer den als Rechnung dieser Seite gekennzeichneten.