Die Schranke ohne Aufzählen verständlich erklärt

Wer Bauteile so auf Plätze legen will, dass die Verbindungen kurz bleiben, kann zunächst alle Anordnungen durchrechnen. Mit jedem Bauteil mehr wächst deren Zahl so stark, dass das irgendwann scheitert. Die Seite zeigt, wie man trotzdem eine Zahl beweist, unter die keine Anordnung fallen kann, und wo diese Zahl vom Besten abweicht.

Zuletzt aktualisiert: 11. November 2026

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

Wer sitzt an welchem Schreibtisch?

Stellen Sie sich ein Großraumbüro vor. Die Mitarbeiterinnen und Mitarbeiter sollen auf ebenso viele Schreibtische verteilt werden. Zwischen manchen Paaren laufen am Tag viele Gänge, zwischen anderen keine oder nur ein paar. Jeder Gang kostet Zeit, und zwar Zahl der Gänge mal Länge des Wegs. Gesucht ist die Verteilung, bei der alle Gänge zusammen am wenigsten kosten.

Dieselbe Aufgabe steckt hinter dem Anordnen von Bauteilen auf einer Platine: Verbindungen zwischen Bauteilen sollen kurz bleiben, und jeder Platz nimmt nur ein Bauteil auf.

Man könnte jede denkbare Verteilung durchrechnen und die billigste nehmen. Das klappt bei einer Handvoll Schreibtischen. Jeder zusätzliche Schreibtisch lässt die Zahl der Verteilungen aber nicht um eine wachsen, sondern auf ein Vielfaches: Jede bisherige Verteilung kann mit dem neuen Platz auf viele Arten ergänzt werden. Bei einem großen Büro schafft das kein Rechner in vernünftiger Zeit.

Die Alternative ist, eine Verteilung schrittweise zu verbessern: Zwei Leute tauschen die Plätze, wenn das Gänge spart. So kommt man zu guten Verteilungen. Ob es eine noch bessere gibt, weiß man danach nicht.

Eine Untergrenze statt Durchprobieren

Hier hilft eine Untergrenze (Fachleute sagen Schranke): eine Zahl, die man beweisen kann, ohne alle Verteilungen durchzurechnen, und unter die keine mögliche Verteilung fallen kann. Billiger als dieser Wert geht es nicht.

Wie man sie ohne Durchrechnen findet

Zuerst ein Bild vom Umzug. Sie tragen mehrere Möbelstücke an ein Ziel. Den kleinsten Gesamtaufwand haben Sie, wenn die schwersten Stücke die kürzesten Wege bekommen und die leichtesten die längsten.

Dasselbe gilt im Büro für eine einzelne Person. Nehmen wir Frau Berger an einem bestimmten Schreibtisch. Sie hat Gänge zu den Kollegen A, B und C: zu A die meisten, zu C die wenigsten. Von ihrem Schreibtisch aus gibt es einen nahen, einen mittleren und einen fernen Schreibtisch. Dann bekommt A den nahen, B den mittleren und C den fernen. Das sind die kleinsten Gangkosten (Gänge mal Weg), die Frau Berger an diesem Schreibtisch haben kann, solange jeder Kollege einen eigenen Schreibtisch bekommt.

Der Haken: Diese Rechnung fragt nur nach Frau Berger. Sie setzt A in Gedanken neben sie. A hat aber selbst Wünsche, etwa neben C zu sitzen, und C hat wieder eigene. Jede Person rechnet so, als würden ihre Kollegen nur für sie sitzen. Alle diese Wünsche zugleich lassen sich nicht in jedem Fall erfüllen.

Diese Rechnung macht man für jede Person an jedem Schreibtisch und trägt die Ergebnisse in eine Tabelle ein: Zeilen sind die Personen, Spalten die Schreibtische. Nun sucht man die Verteilung, bei der jede Person genau einen Schreibtisch und jeder Schreibtisch genau eine Person hat und die Summe der Tabellenwerte am kleinsten ist. Das klingt nach Durchprobieren, ist es aber nicht: Für diese Art Aufgabe gibt es ein bekanntes Rechenverfahren, das die beste Verteilung der Tabelle findet, ohne alle zu prüfen. Nebenbei fällt dabei eine konkrete Verteilung ab.

Jeder Gang taucht in der Tabelle zweimal auf: einmal bei der Person am einen Ende des Weges, einmal bei der am anderen. Darum nimmt man von der Gesamtsumme die Hälfte. Das ist die Untergrenze. Ein Computer braucht dafür Millisekunden, auch bei Büros, die man nicht mehr durchrechnen kann.

Wie nah kommt die Untergrenze dem Besten?

Weil die Rechnung die Wünsche der anderen ausblendet, liegt die Untergrenze unter dem tatsächlich Besten. In Beispielrechnungen mit erfundenen Aufgaben für sechs und acht Bauteile lag sie typischerweise sieben bis neun Prozent darunter. Genau auf dem Besten lag sie nur bei Aufgaben mit Paaren ganz ohne Gänge oder mit einzelnen stark verbundenen Paaren, und auch dort nur in einem Teil der Beispiele.

Die Verteilung, die bei der Tabellenrechnung abfällt, ist ein brauchbarer Plan, aber ein schlechter: Bei acht Bauteilen traf sie in keiner der Beispielaufgaben den besten Wert.

Bei zwölf bis zwanzig Bauteilen lässt sich das Beste nicht mehr durchrechnen. Dort vergleicht man mit der besten Verteilung, die das Tauschen findet. Der so gemessene Abstand zur Untergrenze ist deshalb eine Obergrenze: Der wahre Abstand ist höchstens so groß. Er wuchs mit der Größe, bis auf rund zwanzig Prozent bei zwanzig Bauteilen.

Woran Sie so ein Problem im Alltag erkennen

Sie müssen Dinge auf Plätze verteilen, zwischen den Dingen laufen Wege oder Verbindungen unterschiedlich oft, und jeder Platz nimmt nur eines auf: Maschinen in einer Halle, Artikel auf Lagerplätzen, Bauteile auf einer Platine. Verbessert ein Verfahren Ihre Verteilung und Sie wissen nicht, wann Sie aufhören sollen, hilft die Frage nach einer Untergrenze. Liegt Ihr Ergebnis dicht daran, ist weiteres Suchen kaum noch nötig. Liegt es weit darüber, kann noch etwas zu holen sein, oder die Untergrenze ist zu grob.

Was Sie mitnehmen

• Ein Suchverfahren liefert gute Verteilungen, aber keinen Beweis. Eine Untergrenze liefert den Beweis, aber keine gute Verteilung.
• Eine Untergrenze ist nur so nützlich, wie dicht sie am Besten liegt. Die hier beschriebene ist die einfachste ihrer Art; stärkere kosten mehr Rechenzeit.

Wie ernst ist die Beispielrechnung zu nehmen?

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Es rechnet an erfundenen Aufgaben mit sechs bis zwanzig Bauteilen auf einem Raster, nicht an echten Platinen, und zeigt, wie sich diese eine Untergrenze dort verhält, nicht, wie gut sie bei Ihrer Aufgabe wäre.

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

Gegeben sind \(n\) Bauteile und \(n\) Plätze auf einem Raster. Fluss \(F\) und Abstand \(D\) sind symmetrisch und ganzzahlig, beide mit Diagonale 0. Gesucht ist die Permutation \(p\) (Bauteil \(i\) auf Platz \(p_i\)) mit den kleinsten Kosten. Das ist die symmetrische Koopmans–Beckmann-Form des quadratischen Zuordnungsproblems (QAP); asymmetrische Flüsse und Abstände sind nicht umgesetzt.

• Instanzen: sechs Familien der Flussmatrix: Netzliste, gleichverteilt, dünn besetzt, zwei Cluster, Stern, wenige starke Flüsse. Sie sind eigene, einfache Erfindungen, keine echten Platinen und keine QAPLIB-Instanzen. Die Plätze liegen auf einem Raster (2×3, 2×4, 3×3, 3×4, 4×4, 4×5) mit Manhattan-Abstand.
• Vergleichswert: bis \(n = 9\) das aufgezählte Optimum (Lücke \((\mathrm{opt} - \mathrm{GLB})/\mathrm{opt}\)). Ab \(n = 12\) ersetzt die beste von 200 steilsten Abstiegen aus Zufallsstarts das Optimum; die Lücke ist dann eine obere Grenze der wahren Lücke (siehe unten).
• Feste Instanzen: für \(n = 6\) und \(8\) je Familie die Seeds 100000 bis 100019 (20 Instanzen), für \(n = 12, 16, 20\) die Seeds 100000 bis 100009 (10 Instanzen). \(n = 9\) gibt es nur als Einzelinstanz. Alle Aussagen laufen über feste Seeds, nie über einen einzelnen.

Die Formeln

Die Kosten einer Anordnung \(p\) sind die Summe über alle Paare von Fluss mal Abstand der beiden Plätze:

\[\mathrm{cost}(p) = \sum_{i<k} F_{ik}\, D_{p_i p_k}\]

Für Bauteil \(i\) und Platz \(k\) seien \(f^{(i)}_\uparrow\) die Flüsse von \(i\) zu den anderen Bauteilen, aufsteigend sortiert, und \(d^{(k)}_\downarrow\) die Abstände von \(k\) zu den anderen Plätzen, absteigend sortiert (beide ohne die Diagonale, Länge \(n-1\)). Die Matrix \(L\) ist ihr Skalarprodukt:

\[L_{ik} = \langle f^{(i)}_\uparrow,\; d^{(k)}_\downarrow \rangle\]

Nach der Umordnungsungleichung (Hardy, Littlewood, Pólya) ist das die kleinste Summe \(\sum_{j \ne i} F_{ij}\, D_{k\,q(j)}\) über alle Zuordnungen \(q\) der anderen Bauteile zu den anderen Plätzen. Weil \(q\) nicht mit den Plätzen der anderen Bauteile in \(p\) übereinstimmen muss, ist \(L_{ik}\) nur ein Mindestwert. Für jede Permutation \(p\) gilt daher:

\[\mathrm{cost}(p) = \tfrac12 \sum_i \sum_{j \ne i} F_{ij} D_{p_i p_j} \ge \tfrac12 \sum_i L_{i p_i}\]

Der Faktor \(\tfrac12\) steht da, weil jedes Paar in der Doppelsumme zweimal vorkommt. Die kleinste rechte Seite über alle Permutationen ist eine lineare Zuordnungsaufgabe, lösbar in \(O(n^3)\) mit der Ungarischen Methode (in der Demo eine eigene, ganzzahlige Umsetzung ohne scipy). Ihr halber Wert ist die Schranke:

\[\mathrm{GLB} = \tfrac12 \min_{p} \sum_i L_{i p_i}\]

Die Matrix \(L\) ist ganzzahlig, die Schranke daher halbzahlig. Die Zeilenminimum-Schranke \(\tfrac12 \sum_i \min_k L_{ik}\) lässt die Forderung weg, dass die Plätze verschieden sind. Sie minimiert über eine größere Menge und ist darum nie größer als \(\mathrm{GLB}\).

Runden: Die Zuordnung \(p^\ast\) der linearen Aufgabe ist selbst eine Anordnung, und \(\mathrm{cost}(p^\ast) \ge \mathrm{opt}\) ist eine obere Schranke. Bei mehreren gleich guten Zuordnungen liefert die Ungarische Methode eine davon; die Zahlen unten gelten für die gelieferte.

Lücke ohne bekanntes Optimum: Steht die beste gefundene Lösung \(U \ge \mathrm{opt}\) an der Stelle des Optimums, folgt aus \(\mathrm{GLB}/U \le \mathrm{GLB}/\mathrm{opt}\) (für \(\mathrm{GLB} \ge 0\)), dass \((U - \mathrm{GLB})/U \ge (\mathrm{opt} - \mathrm{GLB})/\mathrm{opt}\) ist. Die ausgewiesene Lücke ist also eine obere Grenze der wahren.

Warum die Schranke unter dem Optimum bleibt

In \(L_{ik}\) darf jedes Bauteil seine Partner unabhängig von den anderen auf die nächsten Plätze legen. Dieselben Plätze stehen den Partnern aber auch für ihre eigenen Mindestwerte zur Verfügung. Die lineare Zuordnung erzwingt nur, dass jedes Bauteil einen eigenen Platz bekommt, nicht, dass die unterstellten Plätze der Partner zusammenpassen.

Das Handbeispiel in der Demo zeigt den Effekt (Fluss A–C, A–D, B–C, B–D je 1, vier Bauteile auf einer Zeile): Die Schranke ist 5, das Optimum 6. Die Mindestwerte von A und B legen C und D jeweils an die nächsten Plätze, obwohl dieselben Plätze nicht beiden zugleich zur Verfügung stehen. Bei den beiden anderen Handbeispielen trifft die Schranke das Optimum (siehe Befunde).

Befunde

Alle Zahlen stehen in der README der Demo und werden von tests/test_claims.py nachgerechnet; sie sind deterministisch. Sie gelten für die sechs erfundenen Familien mit den dort gewählten Parametern und die festen Seeds, nicht für Instanzen im Allgemeinen. Reihenfolge der Familien in allen Zeilen: Netzliste, gleichverteilt, dünn besetzt, zwei Cluster, Stern, wenige starke Flüsse. Die Lücke ist (Vergleichswert − Schranke) / Vergleichswert in Prozent; „Median [Spanne]“ über je 20 Instanzen (\(n = 6, 8\)) bzw. 10 Instanzen (\(n \ge 12\)).

Frage	Befund und Voraussetzung
Handbeispiele (von Hand nachrechenbar)	Drei Bauteile auf einer Zeile (Fluss A–B 5, B–C 1): Schranke 6 gleich Optimum 6. Raster 2×2 (Fluss 3, 1, 2, 4): 10 gleich 10. Vier Bauteile auf einer Zeile (Fluss A–C, A–D, B–C, B–D je 1): Schranke 5, Optimum 6.
Eine einzelne Instanz	Netzliste, \(n = 8\), Seed 35: Schranke 27, Optimum 31 (Lücke 12,9 %); ohne Zuordnung 26 (16,1 %); die Anordnung aus der Zuordnung kostet 43 (38,7 % über dem Optimum). Eine Instanz belegt keinen Trend.
Lücke zum aufgezählten Optimum, \(n = 6\)	Median [Spanne] in %, je Familie 20 Instanzen: 7,3 [1,3; 18,8]; 5,2 [1,4; 8,0]; 10,3 [0,0; 19,4]; 17,0 [14,1; 19,7]; 7,7 [2,4; 12,5]; 3,4 [0,0; 10,8]. Über alle 120 Instanzen 7,3 %.
Lücke zum aufgezählten Optimum, \(n = 8\)	9,2 [4,0; 16,3]; 7,9 [5,3; 10,9]; 6,9 [0,0; 14,0]; 9,7 [8,2; 10,5]; 13,3 [8,8; 16,9]; 6,1 [2,9; 12,2]. Über alle 120 Instanzen 8,9 %.
Gültigkeit und scharfe Treffer	In allen 240 Instanzen (\(n = 6, 8\)) liegt die Schranke höchstens beim Optimum. Scharf (Lücke 0) war sie nur bei dünn besetzten Flüssen (\(n = 6\): 7 von 20; \(n = 8\): 3 von 20) und bei wenigen starken Flüssen (\(n = 6\): 3 von 20), sonst nie.
Was bringt die lineare Zuordnung? (Lücke ohne Zuordnung, Zeilenminimum, Median in %)	\(n = 6\): 15,2 / 14,2 / 10,3 / 20,9 / 11,2 / 7,7; \(n = 8\): 13,7 / 16,6 / 6,9 / 20,5 / 15,5 / 7,2. Bei \(n = 8\) halbiert die Zuordnung die Lücke bei gleichverteilten und Cluster-Flüssen (16,6 → 7,9 %, 20,5 → 9,7 %) und ändert bei dünn besetzten im Median nichts (6,9 % gegen 6,9 %; in 16 von 20 Instanzen kein Unterschied). Für \(n = 6\) nennt die README keine solche Aussage.
Hängt die Lücke am Fluss? (\(n = 6\) / \(n = 8\))	Rangkorrelation (Spearman) der Lücke, 120 Instanzen über alle Familien gepoolt, Unsicherheit grob ±0,19: mit der Dichte +0,07 / +0,05, mit der Flussdominanz −0,11 / −0,16, mit der Kostenlücke einer Zufallsanordnung −0,37 / −0,35. Kein nachweisbarer Zusammenhang mit der Dichte; die Vermutung „dichter Fluss, schwächere Schranke“ wird von der Messung nicht bestätigt.
Jenseits der Aufzählung: Lücke gegen die beste gefundene Lösung (obere Grenze), Median in %, je Familie 10 Instanzen	\(n = 12\): 12,1 / 10,2 / 16,4 / 11,6 / 15,3 / 12,8; \(n = 16\): 16,7 / 12,9 / 22,5 / 14,4 / 18,0 / 15,7; \(n = 20\): 20,1 / 15,1 / 28,5 / 14,6 / 19,9 / 22,5. Über alle Familien 12,3 / 16,0 / 19,8 %. Die ausgewiesene (obere) Grenze der Lücke wächst mit \(n\); die Schranke war in allen 180 Instanzen gültig.
Rangkorrelation bei großen Instanzen (\(n = 12\) / \(16\) / \(20\))	Je 60 Instanzen über alle sechs Familien gepoolt, Unsicherheit grob ±0,28: mit der Dichte −0,68 / −0,71 / −0,78 (dichterer Fluss, kleinere Lücke), mit der Flussdominanz +0,57 / +0,57 / +0,74. Innerhalb einer Familie nicht untersucht.
Wie gut ist die gerundete Anordnung? (Median der Kosten über dem Vergleichswert)	\(n = 8\): 26,2 / 16,6 / 81,1 / 41,2 / 18,8 / 39,0 %; \(n = 12\) / \(16\) / \(20\) über alle Familien: 31,8 / 33,0 / 34,9 %. Das Optimum trifft sie bei \(n = 6\) in 11 von 120 Instanzen, bei \(n = 8\) in 0 von 120, die beste gefundene Lösung bei \(n \ge 12\) nie.
Wie abgesichert ist die Rechnung?	Die Ungarische Methode stimmt auf Zufallsmatrizen und auf den Matrizen \(L\) aller Familien und Größen mit scipy.optimize.linear_sum_assignment überein, die Rangkorrelation mit scipy.stats.spearmanr; die Schranke lag nie über dem aufgezählten Optimum.

Grenzen

• Erfundene Familien: keine echten Platinen, keine QAPLIB-Instanzen. Eine andere Wahl der Parameter kann die Rangfolge der Familien ändern.
• Optimum nur bis \(n = 9\): Ab \(n = 12\) steht die beste von 200 Abstiegen an seiner Stelle. Die Lücken sind obere Grenzen, die wahre Lücke ist höchstens so groß. Dass die Schranke dort „gültig“ war, ist nur gegen diese obere Schranke des Optimums geprüft und damit ein schwächerer Test als bei \(n \le 8\).
• Wenige Instanzen: 20 je Familie (\(n = 6, 8\)) und 10 (\(n \ge 12\)); die Rangkorrelationen schwanken um grob ±0,19 bzw. ±0,28. Unterschiede von wenigen Prozentpunkten zwischen Familien sind nicht belastbar.
• Gepoolte Rangkorrelationen: Die Zusammenhänge mit Dichte und Flussdominanz sind über alle Familien gepoolt. Ob die negative Rangkorrelation bei großen Instanzen innerhalb einer Familie bestehen bleibt und warum die dünn besetzte Familie dort die größte Lücke hat, wurde nicht untersucht.
• Die gröbste Schranke: Stärkere Schranken (Eigenwerte, Linearisierung, semidefinit) kosten mehr Rechenzeit und stehen in anderen Demos dieser Linie; ein Vergleich mit ihnen ist hier nicht gemessen.
• Runden ist keine Suche: Die Anordnung aus der Zuordnung ist nur eine obere Schranke, weit über dem Optimum. Metaheuristiken sind hier nicht gemessen.
• Nur die symmetrische Koopmans–Beckmann-Form mit ganzzahligen Flüssen und Abständen.

Quellen

• P. C. Gilmore (1962) und E. L. Lawler (1963): die Schranke.
• G. H. Hardy, J. E. Littlewood, G. Pólya: die Umordnungsungleichung.
• R. E. Burkard, E. Çela, P. M. Pardalos, L. S. Pitsoulis: Überblick über das quadratische Zuordnungsproblem.

Die Literaturangaben stammen aus der README der Demo und sind aus der Fachliteratur übernommen, aber nicht nachgelesen. Die Formeln sind die gängige Darstellung und werden in der Demo durch Tests (Aufzählung an kleinen Instanzen, scipy für die Zuordnung) geprüft. Die Zahlen sind eigene Rechnungen an eigenen, erfundenen Familien.