Vom Bruchteil zur ganzen Zahl verständlich erklärt

Ein Planungsprogramm meldet: Frau Meier sitzt halb an einem Tisch und halb an einem anderen. Das lässt sich nicht aufstellen. Einfach zu runden geht nicht immer, und manchmal kommt man trotz aller Mühe nicht weiter. Diese Seite zeigt, wann Runden erlaubt ist und was man sonst tut, ohne alle Möglichkeiten durchzuprobieren.

Zuletzt aktualisiert: 11. November 2026

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

Ein Sitzplan mit halben Gästen

Stellen Sie sich vor, ein Programm plant die Sitzordnung einer Feier und soll möglichst viele Gäste neben Bekannte setzen (der bestmögliche Plan ist die beste Lösung). Zuerst rechnet es so, als dürfte man Gäste teilen, weil das die Aufgabe vereinfacht. Heraus kommt: Frau Meier sitzt halb am ersten Tisch und halb am zweiten. Das ist ein Plan mit Bruchteilen (Fachwort: LP-Lösung).

Gebraucht wird aber ein ganzer Plan, in dem jeder Gast an genau einem Tisch sitzt. Ein Suchbaum, der bei jedem Gast in die Möglichkeiten verzweigt und unpassende Äste streicht, führt dorthin, braucht bei großen Aufgaben aber sehr viele Schritte. Diese Seite zeigt Wege ohne Suchbaum: Runden, schrittweises Festlegen und Hin- und Herpendeln.

Nachgerechnet wird an zufällig erzeugten Aufgaben, den Instanzen, in einem vereinfachten Modell, nicht an einem echten Betrieb. Es gibt zwölf Arten von Aufgaben, je in kleiner und mittlerer Größe, mit je 100 Instanzen, zusammen 2 400. Eine Demo, ein Programm zum Ausprobieren, zeigt dieselben Rechnungen live.

Wann darf man runden?

Ob Runden erlaubt ist, steht in den Regeln der Aufgabe. Drei Beispiele, jeweils für Mengen, die nicht negativ sind:

• Obergrenze (ein Koffer mit Gewichtsgrenze): Lässt man einen halb eingepackten Gegenstand weg, wird der Koffer nicht zu schwer. Abrunden ist sicher, Aufrunden nicht.
• Untergrenze (jede Straße muss von mindestens einer Kamera gesehen werden): Aus einer halben Kamera eine ganze zu machen, verletzt keine Regel, sie wegzulassen kann es. Aufrunden ist sicher, Abrunden nicht.
• Genau einmal (jeder Gast an genau einem Tisch): Macht man aus den beiden halben Plätzen von Frau Meier zwei ganze, sitzt sie an zwei Tischen, streicht man beide, nirgends. Keine Richtung ist sicher. Dasselbe gilt, wenn eine Untergrenze auf eine gegenläufige Obergrenze trifft, etwa: jede Straße gesehen, aber nur wenige Kameras erlaubt.

Eine Richtung, die eine Regel verbietet, heißt gesperrt. Die Demo zählt je gebrochener Entscheidung die Regeln, die das Abrunden oder das Aufrunden sperren, und zeigt die freie Richtung. Wer nur in freie Richtungen rundet, bleibt regelgerecht (Fachwort: Runden nach Sperren). In der Demo gelang das bei jeder gemessenen Instanz mit nur Obergrenzen oder nur Untergrenzen, bei den Aufgabenarten, in denen die ganzen Entscheidungen selbst unter „genau einmal“ fallen (etwa Aufträge auf Maschinen verteilen), aber nur in 60 von 1 000 Instanzen. Auch schlichtes Runden auf die nächste ganze Zahl (ab einem halben Teil aufrunden) gelang über alle 2 400 Instanzen nur 665-mal.

Wenn Runden scheitert: mitrechnen

Man kann beim Runden gleich die Folgen mitrechnen. Setzt man Frau Meier an den ersten Tisch, ist sie am zweiten gestrichen, und am ersten ist ein Platz weniger frei. Ist dadurch ein Tisch voll, fallen für alle anderen die Plätze dort weg, und manchmal ist danach alles festgelegt (Fachwort: Propagation). Zeigt sich ein Widerspruch, probiert man die andere Richtung. Das hilft, wenn die Aufgabe Spielraum lässt: Bei Aufträgen auf Maschinen mit Kapazität klappte es in der Demo bei 94 von 100 Instanzen mittlerer Größe. Bei den beiden gemessenen Aufgabenarten, die nur aus „genau einmal“-Regeln bestehen, gelang es in keiner der 400 Instanzen.

Tauchen: festlegen und neu planen

Das zweite Mittel: nicht alles auf einmal runden. Man legt einen Gast fest, etwa Frau Meier an den ersten Tisch, und lässt das Programm den Rest neu planen, wieder mit Bruchteilen. Dann legt man den Nächsten fest, bis keine Bruchteile mehr übrig sind (Fachwort: Tauchen). Wird der Rest unlösbar, nimmt man die Festlegung zurück und probiert die andere (ein Rückschritt). Sind keine Rückschritte mehr erlaubt, steckt man in einer Sackgasse. Das kommt vor: Bei mittleren Aufgaben, in denen jede Straße gesehen werden muss, aber nur eine begrenzte Zahl Kameras erlaubt ist, löste das Tauchen mit Mitrechnen nur 64 von 100 Instanzen.

Pendeln: der Feasibility Pump

Das dritte Mittel ist ein Pendel. Man rundet den Plan mit Bruchteilen zu einem ganzen Plan, der vielleicht eine Regel verletzt, und fragt: Welcher regelgerechte Plan mit Bruchteilen liegt diesem am nächsten? Den rundet man wieder und wiederholt das. Dreht sich das Pendel im Kreis, rüttelt man mit etwas Zufall oder beginnt neu (Fachwort: Feasibility Pump). Er gibt auf, wenn er die erlaubte Zahl an Runden erreicht hat. Seine Lösungen, soweit er welche fand, lagen in der Demo bei jeder gemessenen Aufgabenart und Größe weiter von der besten Lösung entfernt als die des Tauchens mit Mitrechnen.

Alles nacheinander: die Kaskade

Man kann die Mittel hintereinanderschalten: erst Runden mit Mitrechnen, nur bei Scheitern Tauchen, nur dann der Pump (Fachwort: Kaskade). So löste die Demo 2 399 von 2 400 Instanzen. Sie hört aber bei der ersten ganzen Lösung auf, nicht bei der besten: Im Mittel über die jeweils gelösten Instanzen lag ihr Ergebnis weiter von der besten Lösung als das des Tauchens allein, nicht in jeder Aufgabenart.

Spart eine Startlösung dem Suchbaum Arbeit?

Naheliegend wäre: Wer schon eine ganze Lösung hat, lässt den Suchbaum weniger Äste prüfen. Die Demo hat das an einem einfachen Suchbaum nachgezählt, nach Abzug der Arbeit für die Startlösung selbst. Je nach Art der Suche sparte sie nur bei drei oder gar nur bei einer von zwölf Aufgabenarten gesichert Arbeit; bei mindestens sechs kostete sie gesichert mehr.

Häufige Missverständnisse

• „Kleine Bruchteile kann man einfach runden.“ Nicht unbedingt. Beim Runden nach Sperren entscheiden nur die Regeln, beim schlichten Runden die Schwelle, ab der man aufrundet; keine Schwelle passte in der Demo für alle Aufgaben.
• „Eine ganze Lösung ist eine gute Lösung.“ Nein, nur regelgerecht. In der Demo war der Wert erfolgreicher Rundungen bei den Aufgaben mit nur Obergrenzen im Mittel etwa um die Hälfte schlechter als die beste Lösung.
• „Tauchen und Pump finden immer etwas.“ In der Demo scheitern beide messbar: das Tauchen in Sackgassen, der Pump an seiner Grenze für die Zahl der Runden.

Woran Sie das im Alltag erkennen

• Jemand rundet Zahlen in einem Plan und merkt, dass ein Termin an zwei Personen vergeben ist oder eine Lieferung fehlt: Oft stand eine Regel „genau einmal“ oder eine gegenläufige Grenze im Weg.
• Bei „höchstens“-Regeln mit nicht negativen Mengen bleibt man beim Kürzen regelgerecht, bei „mindestens“-Regeln beim Aufstocken.
• Ein Planungsprogramm meldet nach einer Festlegung „keine zulässige Lösung“ und geht zurück: Es taucht und kann in einer Sackgasse enden.

Wie ernst sind die Zahlen zu nehmen?

Die Demo rechnet an erzeugten Aufgaben, nicht an Betriebsdaten; jede Entscheidung ist dort ein Ja oder Nein („Gast sitzt an diesem Tisch oder nicht“). Die Zahlen verschieben sich mit der Größe der Aufgaben.

Was Sie mitnehmen

• Die Regeln einer Aufgabe verraten, in welche Richtung gerundet werden darf.
• Wo Runden scheitert, hilft Mitrechnen bei Spielraum; sonst bleiben Tauchen und Pendeln, die auch scheitern können.
• Eine ganze Lösung ist noch keine beste, und eine Startlösung spart nicht jedem Suchbaum Arbeit.

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

Die LP-Relaxation eines ganzzahligen Programms (die Ganzzahligkeit wird fallen gelassen) ist schnell lösbar und liefert eine untere Schranke, aber meist gebrochene Werte. Primalheuristiken suchen daraus ohne Suchbaum eine zulässige ganzzahlige Lösung: durch Runden, durch Tauchen (Variablen festsetzen, das LP neu lösen) und durch den Feasibility Pump (zwischen LP-Lösung und Rundung pendeln).

Betrachtet werden ganzzahlige lineare Programme in Minimierungsform mit Ungleichungs- und Gleichungszeilen und Schranken \(0 \le x \le 1\); eine ≥-Zeile steht negiert in \(A\), eine Maximierung negiert in \(c\). Die ganzzahligen Variablen sind hier immer 0/1; die Standortplanung hat zusätzlich stetige Variablen (Zuordnung) mit Schranken 0 bis 1. Die Demo erzeugt zwölf Familien in vier Strukturklassen, je zwei Größen (klein: höchstens 25 ganzzahlige Variablen, bei der Standortplanung 6; mittel: 12 bis 120):

Klasse	Familie	Zeilen	ganzzahlige Variablen klein / mittel
≤	mkp, mehrdimensionaler Rucksack	nur ≤ (5)	12 / 20
≤	stable, gewichtete stabile Menge	nur ≤ (je Kante)	16 / 30
≤	mknap, Mehrfach-Rucksack	nur ≤	18 / 32
≥	setcover, Mengenüberdeckung	nur ≥	24 / 120
≥	vertexcover, Knotenüberdeckung	nur ≥	16 / 50
≥	cover_card, Überdeckung mit höchstens K Mengen	≥ und eine ≤-Zeile	24 / 120
=	gap, Aufträge auf Maschinen (Hauptfamilie)	= und ≤	18 / 64
=	assign_side, Zuordnung mit Zusatzgleichungen	nur =	25 / 100
=	setpart, Mengenpartitionierung	nur =	21 / 60
=	binpack, Bin Packing	= und ≤	im Mittel 21 / 42
=	seqprec, Reihenfolge mit Vorrang	= und ≤	25 / 81
gemischt	ufl, Standortplanung (Zuordnung stetig)	= und ≤	6 / 12

Die Instanzen kommen aus einem eigenen Zufallsgenerator (SplitMix64), sodass gleiche Zufalls-Seeds auf Windows und Linux gleiche Instanzen ergeben. Die Landkarte ist die vorberechnete Messung der Demo: je Familie und Größe die ersten 100 Instanzen mit gebrochener Wurzel-LP (der LP-Relaxation am Anfang; Zufalls-Seeds ab 0), zusammen 2 400 Instanzen, jede mit allen Verfahren. Eine Zelle ist eine Kombination aus Familie und Größe, es gibt 24. Zähleinheit überall: gelöste LPs (die Wurzel mitgezählt, bei der Kaskade einmal); Simplex-Iterationen werden nie mit LPs vermischt, ein Knoten des Vergleichsbaums ist ebenfalls ein LP. Erfolg ist der Anteil der Instanzen, für die ein unabhängiger Prüfer, der keine Heuristik kennt, die Lösung annimmt; Lücke ist die Abweichung vom Optimum in Prozent des Betrags des Optimums (Formel unten; nur für ein Optimum ungleich null erklärt), gemittelt über die erfolgreichen Läufe. Das Referenzoptimum liefert HiGHS-MILP.

Verglichen werden diese Verfahren:

• Runden nach Sperren: jede gebrochene Variable in einer ungesperrten Richtung runden.
• Runden mit Schwelle \(\theta \in \{0{,}3;\, 0{,}5;\, 0{,}7;\, 1/f\}\): aufrunden, wenn der Nachkommaanteil mindestens \(\theta\) beträgt, sonst abrunden; für \(\theta = 0{,}5\) ist das die Rundung auf die nächste ganze Zahl. \(f\) ist die Länge der längsten ≥-Zeile, also die Zahl ihrer Koeffizienten ungleich null (ohne ≥-Zeile gilt 0,5).
• Runden mit Propagation: die Variable mit dem kleinsten Abstand zur nächsten ganzen Zahl zuerst, zuerst in die Richtung, die \(\theta\) vorgibt (deshalb hängt das Ergebnis bei cover_card an \(\theta\)); Schranken propagieren; bei Widerspruch die andere Richtung, sonst Abbruch (ohne Rückschritt).
• Tauchen: eine Variable festsetzen, das LP neu lösen, wiederholen. Ist das LP unzulässig (oder zeigt die Propagation einen Widerspruch), folgt ein Rückschritt: Die gescheiterte Fixierung wird umgekehrt, bei erneutem Scheitern geht es eine Ebene zurück; jeder Versuch der anderen Richtung zählt als ein Rückschritt, erlaubt sind 0, 1, 5 oder 20. Das Ergebnis „Sackgasse“ entsteht, wenn kein Rückschritt mehr möglich ist oder die erlaubte Zahl aufgebraucht ist; „LP-Grenze“ heißt, dass ein Tauchgang die Grenze von 400 LPs erreicht hat. Regeln für die Wahl der Variable: Fractional (kleinster Abstand zur ganzen Zahl, gerundet zur nächsten), Coefficient (wenigste Sperren), Guided (die Variable, deren LP-Wert der Referenzlösung am nächsten liegt, wird auf den Wert der Referenz gesetzt; Referenz ist hier die Lösung von Runden mit Propagation, findet sie keine, läuft das Tauchen nicht). Mit oder ohne Propagation nach jedem Festsetzen.
• Feasibility Pump: \(T = 10\) Umkehrungen bei Stillstand, Zufallsstörung bei Zyklus, Neustart nach 15 Iterationen ohne kleineren Abstand (0, 3 oder 10 Neustarts), höchstens 300 Iterationen. Optional mit Zielgewicht: Startwert 1, je Iteration mal 0,9, bei jedem Neustart wieder auf 1.
• Kaskade: Stufe 0 ist Runden mit Propagation; nur bei Scheitern folgt Stufe 1, Tauchen mit Propagation (20 Rückschritte); nur dann Stufe 2, der Pump mit 10 Neustarts.
• Vergleichsbaum: ein einfacher Suchbaum, entweder Tiefensuche (immer der zuletzt erzeugte Knoten) oder beste Schranke zuerst (der Knoten mit dem kleinsten LP-Wert), ohne Schnitte (zusätzliche Ungleichungen, die das LP verschärfen), ohne Presolve (Vorverarbeitung der Aufgabe) und ohne Warmstart (jedes LP wird von Null an gelöst), Limit 1 000 LPs.

Die Formeln

Das Problem, mit \(x \in \mathbb{R}^n\) und der Menge \(I\) der ganzzahligen Variablen:

\[\min\; c^\top x\]

unter den Ungleichungszeilen, den Gleichungszeilen, den Schranken und der Ganzzahligkeit für \(j \in I\) (hier ist \(0 \le x_j \le 1\), also \(x_j \in \{0, 1\}\)):

\[A x \le b,\; A_{eq}\, x = b_{eq},\; \ell \le x \le u,\; x_j \in \mathbb{Z}\]

Die LP-Relaxation lässt \(x_j \in \mathbb{Z}\) fallen. Ihre Lösung ist \(x^*\), ihr Wert \(c^\top x^*\) eine untere Schranke des Optimums \(z^{opt}\). Die Lücke einer Lösung \(\hat{x}\) in Prozent:

\[100 \cdot (c^\top \hat{x} - z^{opt}) / |z^{opt}|\]

Sperren. Für \(j \in I\) zählt \(\mathrm{down}(j)\) die Zeilen, die ein Verkleinern, und \(\mathrm{up}(j)\) die Zeilen, die ein Vergrößern von \(x_j\) verletzen können (\(a_{ij}\) ist der Koeffizient von \(x_j\) in Ungleichungszeile \(i\), \(a^{eq}_{ij}\) in Gleichungszeile \(i\)):

\[\mathrm{down}(j) = |\{i : a_{ij} < 0\}| + |\{i : a^{eq}_{ij} \ne 0\}|\]

\[\mathrm{up}(j) = |\{i : a_{ij} > 0\}| + |\{i : a^{eq}_{ij} \ne 0\}|\]

Gilt \(\mathrm{down}(j) = 0\), kann Abrunden von \(x_j\) keine Zeile verletzen; gilt \(\mathrm{up}(j) = 0\), gilt das für Aufrunden (Begründung im nächsten Abschnitt). Runden nach Sperren gelingt genau dann, wenn jede gebrochene Variable \(\mathrm{down}(j) = 0\) oder \(\mathrm{up}(j) = 0\) hat. Beide Richtungen dieser Aussage wurden an 91 Instanzen mit gebrochener Wurzel geprüft (kleine Größe, Zufalls-Seeds 0 bis 11).

Rundung mit Schwelle \(\theta\): Der gerundete Punkt \(\tilde{x}\) setzt

\[\tilde{x}_j = \lceil x^*_j \rceil\]

falls der Nachkommaanteil \(x^*_j - \lfloor x^*_j \rfloor \ge \theta\) ist, sonst \(\tilde{x}_j = \lfloor x^*_j \rfloor\).

Propagation (aktivitätsbasiert). Für eine Zeile \(\sum_k a_k x_k \le b\) (hier ist \(b\) die rechte Seite dieser einen Zeile) ist die kleinste mögliche Aktivität

\[\mathrm{minact} = \sum_{a_k > 0} a_k \ell_k + \sum_{a_k < 0} a_k u_k\]

Für \(a_j > 0\) folgt

\[x_j \le \ell_j + (b - \mathrm{minact})/a_j\]

und für \(a_j < 0\) folgt

\[x_j \ge u_j + (b - \mathrm{minact})/a_j\]

bei ganzzahligen Variablen wird abgerundet bzw. aufgerundet. Gilt \(\mathrm{minact} > b\) oder \(\ell_j > u_j\), ist die Teilbelegung unzulässig. Gleichungen zählen als zwei Ungleichungen.

Feasibility Pump. Zu einem gerundeten Punkt \(\tilde{x}\) wird unter den Zeilen das LP gelöst, das den Abstand zur Rundung minimiert:

\[\min\; \Delta(x, \tilde{x}) = \sum_{j \in I:\, \tilde{x}_j = 0} x_j + \sum_{j \in I:\, \tilde{x}_j = 1} (1 - x_j)\]

Ist die Lösung dieses LPs ganzzahlig, ist sie zulässig, sonst wird neu gerundet. Mit Zielgewicht \(\alpha\) (Startwert 1) lautet die Zielfunktion

\[(1-\alpha)\,\Delta + \alpha\,\sqrt{|I|}\, c^\top x / \lVert c \rVert\]

wobei \(\alpha\) je Iteration um den Faktor 0,9 sinkt und \(\lVert c \rVert\) die Norm des Kostenvektors ist.

Vergleichsbaum. Knoten werden abgeschnitten, wenn (bei ganzzahligen Zielwerten) mit \(z^{inc}\), dem Wert der besten bekannten Lösung, gilt:

\[\lceil c^\top x^* \rceil \ge z^{inc}\]

Herleitung: Warum die Sperren das Runden entscheiden

Die vier Schritte sind ein Standardargument.

• Schritt 1, Wirkung einer Änderung: Eine Ungleichungszeile \(\sum_k a_k x_k \le b\) ist an \(x^*\) erfüllt. Ändert man \(x_j\) um \(\delta\), ändert sich ihre Aktivität um \(a_j \delta\). Sie steigt nicht, wenn \(a_j \delta \le 0\): bei Aufrunden (\(\delta > 0\)) genau für \(a_j \le 0\), bei Abrunden (\(\delta < 0\)) genau für \(a_j \ge 0\).
• Schritt 2, freie Richtung: Gilt \(\mathrm{down}(j) = 0\), hat \(x_j\) in jeder Ungleichungszeile einen Koeffizienten \(a_{ij} \ge 0\) und kommt in keiner Gleichung vor. Abrunden senkt dann jede Aktivität oder lässt sie gleich. Für \(\mathrm{up}(j) = 0\) gilt dasselbe mit Aufrunden. Eine ≥-Zeile steht negiert in \(A\): Mit nicht negativen Koeffizienten in der ≥-Form sperrt sie das Abrunden, erlaubt also nur Aufrunden. Bei einer ≤-Zeile mit nicht negativen Koeffizienten ist es umgekehrt. Wegen des Vorzeichens gibt es Ausnahmen: Bei der Standortplanung steht eine Zeile \(x_{ij} \le y_i\) als \(x_{ij} - y_i \le 0\), die ≤-Zeile sperrt dort das Abrunden von \(y_i\), und die Gleichungen enthalten nur stetige Variablen; Runden nach Sperren gelingt dort trotz der Gleichungen.
• Schritt 3, alle zugleich: Rundet man jede gebrochene Variable in eine freie Richtung, wirkt jede einzelne Änderung in jeder Zeile nicht steigernd, also auch ihre Summe. Die Schranken 0 und 1 bleiben erhalten, die Gleichungen sind unberührt (Variablen in Gleichungen sind beidseitig gesperrt), stetige Variablen bleiben in dieser Überlegung fest. Das Ergebnis ist zulässig. Ist eine gebrochene Variable in beiden Richtungen gesperrt, bricht das Verfahren ab.
• Schritt 4, was die Sperren nicht sagen: Sie entscheiden nur über diese Rundungsregel, nicht darüber, ob irgendeine zulässige Rundung existiert. Runden mit Propagation fand über alle 2 400 Instanzen 1 779 Lösungen, Runden nach Sperren nur 1 260 (siehe Befunde).

Durchgerechnetes Beispiel: zwei Aufträge, zwei Maschinen

Zwei Aufträge \(t = 1, 2\) laufen auf zwei Maschinen \(m = 1, 2\); \(x_{mt} = 1\), wenn Auftrag \(t\) auf Maschine \(m\) läuft. Kosten: \(c_{11} = 1\), \(c_{12} = 2\), \(c_{21} = 3\), \(c_{22} = 3\). Jeder Auftrag läuft genau einmal (\(x_{1t} + x_{2t} = 1\)), jeder Auftrag belegt 2 Einheiten, jede Maschine hat die Kapazität 3 (\(2 x_{m1} + 2 x_{m2} \le 3\)).

Schritt	Ergebnis
LP-Lösung	\((x_{11}, x_{12}, x_{21}, x_{22}) = (1, \tfrac{1}{2}, 0, \tfrac{1}{2})\) mit Wert \(\tfrac{7}{2}\); das ganzzahlige Optimum ist 4 mit \((1, 0, 0, 1)\)
Sperren	Jede Variable hat \(\mathrm{down} = 1\) (nur die Gleichung) und \(\mathrm{up} = 2\) (Gleichung und Kapazitätszeile); die gebrochenen Variablen \(x_{12}\) und \(x_{22}\) sind in beiden Richtungen gesperrt, Runden nach Sperren bricht ab
Nächste ganze Zahl, \(\theta = 0{,}5\)	beide \(\tfrac{1}{2}\) werden aufgerundet: \((1, 1, 0, 1)\), Auftrag 2 läuft zweimal, und Maschine 1 ist mit \(2 + 2 > 3\) überlastet: unzulässig
Mit Propagation	kleinster Abstand zuerst: \(x_{11} = 1\). Die Kapazitätszeile von Maschine 1 gibt \(2 \cdot 1 + 2 x_{12} \le 3\), also \(x_{12} \le \tfrac{1}{2}\), abgerundet \(x_{12} = 0\); die Gleichung von Auftrag 2 gibt \(x_{22} = 1\), die von Auftrag 1 gibt \(x_{21} = 0\). Ergebnis \((1, 0, 0, 1)\) mit Wert 4 = Optimum, ohne weiteres LP (nur die Wurzel)
Tauchen (Fractional, mit Propagation, 20 Rückschritte)	setzt \(x_{12}\) auf 1 (der LP-Wert \(\tfrac{1}{2}\) wird aufgerundet); die Propagation fixiert \(x_{11} = 0\), \(x_{21} = 1\), \(x_{22} = 0\). Ein weiteres LP bestätigt den Punkt: zulässig, aber nicht optimal, \((0, 1, 1, 0)\) mit Wert 5 nach 2 LPs

Beim Rucksack mit drei Gegenständen (Werte 5, 4, 3, Gewicht je 2, Limit 3) lautet die LP-Lösung \((1, \tfrac{1}{2}, 0)\) mit Wert 7. Abrunden ergibt \((1, 0, 0)\) mit Wert 5, das Optimum; Aufrunden ab \(\theta = 0{,}5\) verletzt das Limit (\(2 + 2 > 3\)). Aus zwei Beispielen folgt keine Rangfolge der Verfahren; dafür stehen die Befunde.

Befunde

Alle Zahlen stammen aus der Landkarte und den weiteren gespeicherten Messungen der Demo (2 400 Instanzen mit gebrochener Wurzel, je Zelle 100); abweichende Instanzzahlen stehen in der jeweiligen Zeile. Die Lücken gelten nur für die erfolgreichen Läufe. Die Hauptaussagen:

• Ob Runden nach Sperren gelingt, entscheidet die Zeilenstruktur: bei nur ≤- oder nur ≥-Zeilen und bei der Standortplanung immer, bei den Gleichungsfamilien (außer binpack) und bei cover_card nie. Die Lücke der gelungenen Rundungen ist groß.
• Die Propagation rettet das Runden bei Gleichungen mit Kapazitätsspielraum (gap), nicht bei reinen Gleichungssystemen (assign_side, setpart).
• Tauchen und Pump scheitern messbar, das Tauchen in Sackgassen, der Pump an seiner Iterationsgrenze. Das Zielgewicht des Pumps senkt die Lücke vor allem durch die Auswahl leichterer Instanzen.
• Die Kaskade löst 2 399 von 2 400 Instanzen, hört aber bei der ersten zulässigen Lösung auf. Eine Startlösung spart dem einfachen Vergleichsbaum nur bei wenigen Familien netto Arbeit.

Runden. Erfolge je Verfahren und Familie:

Frage	Befund
Wann gelingt Runden nach Sperren? (je Zelle 100 Instanzen)	≤-Familien (mkp, stable, mknap) 600 von 600; ≥-Familien setcover und vertexcover 400 von 400; cover_card (≥ und eine ≤-Zeile) 0 von 200; Gleichungsfamilien gap, assign_side, setpart, seqprec 0 von 800; binpack 43 von 100 (klein), 17 von 100 (mittel); ufl (gemischt) 200 von 200. Klassenweise (Instanzen): ≤ 600 von 600, ≥ 400 von 600, = 60 von 1 000, gemischt 200 von 200
Wie gut sind die so gerundeten Lösungen? (Lücke der erfolgreichen Rundungen)	im Mittel 49,8 % bei den ≤-Familien, 74,1 % bei den ≥-Familien; bei ufl 52,3 % (klein) und 60,4 % (mittel), obwohl das Runden dort gelingt
Wo rettet die Propagation das Runden? (klein und mittel, je 100 Instanzen)	Runden mit Propagation gelingt bei allen ≤-Familien, setcover, vertexcover und ufl in jeder Instanz, bei gap in 83 und 94, bei binpack in 99 und 98, bei seqprec in 77 und 47, bei cover_card in 77 und 4 von 100; bei assign_side und setpart in 0 von 400. Über alle 2 400 Instanzen: Runden nach Sperren 1 260, auf die nächste ganze Zahl (θ = 0,5) 665, mit Propagation 1 779 Erfolge
Gibt es eine beste Rundungsschwelle θ? (beide Größen, 200 Instanzen je Familie)	Nein. Erfolge von Runden mit Schwelle bei θ = 0,3 / 0,5 / 0,7 / 1/f: stable 0 / 0 / 200 / 0, setcover 184 / 120 / 0 / 200, vertexcover 200 / 200 / 0 / 200, ufl 200 / 177 / 1 / 177, mkp 4 / 59 / 160 / 59, assign_side und setpart bei keiner Schwelle ein Erfolg. Bei setcover steigt von θ = 0,3 auf 1/f der Erfolg von 184 auf 200 von 200 und die Lücke der Erfolgreichen von 45,9 % auf 72,6 %, vor allem bei mittel (46,0 % → 97,6 %; klein 45,9 % → 47,6 %). Runden mit Propagation hängt bei gap, binpack und seqprec nicht an θ, bei cover_card ja (Erfolge 77 / 81 / 103 / 73 von 200)

Tauchen und Pump. Erfolge und LPs über alle 2 400 Instanzen, dazu die Sackgassen:

Frage	Befund
Erfolge und LPs	Fractional ohne Propagation 2 319 (13,4 LPs im Mittel), mit Propagation 2 342 (9,3 LPs), Coefficient mit Propagation 2 369 (8,0 LPs); Pump mit Neustarts 2 294 (22,0 LPs, Lücke 33,1 %), mit Zielgewicht 2 193 (38,0 LPs, Lücke 12,6 %). Das Tauchen mit Propagation braucht bei sieben der zehn Gleichungszellen weniger LPs als der Pump; teurer ist es bei gap mittel und bei seqprec klein und mittel
Wo scheitern Tauchen und Pump?	Das Tauchen scheitert in Sackgassen (Ergebnis „Sackgasse“, nicht an der LP-Grenze): Tauchen mit Propagation löst cover_card mittel nur in 64, setpart mittel in 91, seqprec mittel in 90 von 100 Instanzen; der Pump bei binpack mittel in 79, bei mknap mittel in 63 (mit Zielgewicht 29) von 100. Der Pump scheitert an der Iterationsgrenze, nicht in Sackgassen (geprüft an binpack mittel mit 40 Instanzen)
Was bringt das Zielgewicht des Pumps?	Es senkt die Lücke der erfolgreichen Läufe in 22 von 24 Zellen, bei teils deutlich geringerer Erfolgsrate (mknap klein 75 → 28, mittel 63 → 29 von 100, mkp klein 100 → 87). Dieser Vergleich mittelt über verschiedene Instanzen und enthält deshalb einen Auswahleffekt. Gepaart, nur auf Instanzen, die beide Varianten lösen, senkt es die Lücke in 21 von 24 Zellen; nicht bei binpack mittel (20,8 → 21,9 %), seqprec klein (2,2 → 2,9 %) und mknap mittel (14,4 → 21,3 %). Bei mknap klein ist der größte Teil des scheinbaren Vorteils Auswahl (gepaart 11,6 → 10,3 %, ungepaart 20,3 → 10,3 %).

Kaskade. Stufe 0 ist Runden mit Propagation, Stufe 1 Tauchen, Stufe 2 der Pump:

Frage	Befund
Was löst die Kaskade? (alle 2 400 Instanzen)	2 399 von 2 400 Instanzen mit im Mittel 5,79 LPs (Tauchen mit Propagation allein: 2 342, 9,27 LPs). Stufe 0 löst 1 779 Instanzen, Stufe 1 566, Stufe 2 54; eine Instanz löst keine Stufe (setpart mittel)
Wie gut sind die Lösungen der Kaskade?	Sie hört bei der ersten zulässigen Lösung auf, nicht bei der besten: im Mittel über die jeweils gelösten Instanzen 22,0 % Lücke gegen 7,1 % beim Tauchen mit Propagation. In 15 von 24 Zellen ist die Lücke der Kaskade größer als die des Tauchens, in 3 gleich (assign_side klein und mittel, setpart klein: Stufe 0 gelingt dort nie, die Kaskade ist dort das Tauchen) und in 6 kleiner (mkp und gap klein und mittel, setpart mittel, seqprec mittel). Mehr LPs als das Tauchen allein braucht sie in 2 Zellen (setpart mittel 28,6 gegen 21,4, cover_card mittel 56,7 gegen 54,5); der Pump braucht in 13 von 24 Zellen gleich viele oder weniger LPs als das Tauchen

Rückschritt und frühere Messung. Der Rückschritt der gescheiterten Fixierung ist eine Korrektur: Die frühere Messung, die der Bau ersetzt, kehrte bei einem unzulässigen LP die vorletzte erfolgreiche Fixierung um. Gegenmessung auf denselben 2 400 Instanzen mit 20 Rückschritten:

Frage	Befund
Was bringt der Rückschritt der gescheiterten Fixierung?	Fractional ohne Propagation 2 319 (13,4 LPs im Mittel) gegen 2 091 (14,3 LPs) beim früheren Verhalten; Fractional mit Propagation 2 342 (9,3 LPs) gegen 2 256 (9,5 LPs); Coefficient mit Propagation 2 369 (8,0 LPs) gegen 2 297. Der Rückschritt ist nicht überall ein Vorteil: Fractional ohne Propagation bei gap mittel 89 gegen 92 und Fractional mit Propagation bei seqprec mittel 90 gegen 95 von 100
Was verschob sich gegenüber der früheren Messung? (deren Zahlen liegen nicht im Repo, sie sind nur aus der README übernommen und nicht neu geprüft)	Tauchen mit Propagation: Erfolg 97,6 % mit 9,3 LPs statt 92,4 % mit 11,7 LPs; Kaskade 99,96 % mit 5,8 LPs statt 99,7 % mit 8,05 LPs. Die Propagation spart im Tauchen knapp ein Drittel der LPs (31 %), hebt den Erfolg aber nur von 96,6 % auf 97,6 %. Der Rückschritt erklärt beim Tauchen mit Propagation 3,6 von 5,2 Punkten Abstand; was vom Rest auf den anderen Zufallsgenerator und die anderen Instanzen entfällt, wurde nicht getrennt gemessen und bleibt offen

Startlösung und Suchbaum. Gemessen an 60 Instanzen je Familie und Größe (also 120 je Familie, ab Seed 0, Limit 1 000 LPs), gepaart über die Instanzen, in denen der Beweis ohne und mit Startlösung im Limit gelang. Die Startlösung stammt von der Kaskade. Brutto ist die Ersparnis in Prozent der LPs ohne Startlösung, netto nach Abzug aller LPs der Kaskade; das Band ist das 95-%-Band der Nettoersparnis (Bootstrap über die gepaarten Instanzen, 2 000 Ziehungen). „Gesichert“ heißt: Das Band liegt ganz über oder ganz unter null; „offen“: Es enthält null. Angaben in der Form brutto / netto; bei den offenen Familien nennt die Messung nur eine Zahl (−0,8; −4,2; −4,1), hier mit ihrem Band.

Suchart und Ergebnis	Familien: brutto / netto in %, Band der Nettoersparnis
Tiefensuche, netto gesichert positiv	gap 45,9 / 43,9, Band 33,4 bis 55,3; binpack 16,1 / 12,9, Band 7,0 bis 20,8; mkp 16,3 / 15,9, Band 11,5 bis 20,8
Tiefensuche, netto gesichert negativ	assign_side, setpart (12,8 / −76,5), stable, mknap, vertexcover und ufl
Tiefensuche, offen (Band enthält null)	seqprec −0,8, Band −16,1 bis 13,7; setcover −4,2, Band −9,3 bis 1,7; cover_card −4,1, Band −14,8 bis 8,2
Beste Schranke zuerst, netto gesichert positiv	nur binpack 22,8 / 21,9, Band 11,9 bis 33,7
Beste Schranke zuerst, offen	gap 4,3 / −1,6, Band −4,6 bis 1,6
Beste Schranke zuerst, netto gesichert negativ	die übrigen zehn Familien, brutto jeweils unter 5

Mit 30 Instanzen je Zelle (erste Fassung dieser Messung; die Messdatei enthält nur die spätere Fassung) waren es netto gap 34,7, binpack 21,2 und mkp 15,5: Die Zahlen schwanken mit der Stichprobe, das positive Vorzeichen dieser drei blieb.

Was die Messung zeigt und was nicht (Grenzen)

Was sie belegt:

• In diesen erzeugten Instanzen entscheidet die Zeilenstruktur, ob Runden nach Sperren gelingt: bei den ≤-Familien, setcover, vertexcover und ufl in allen gemessenen Instanzen, bei den Gleichungsfamilien außer binpack und bei cover_card in keiner.
• Die Propagation rettet das Runden bei gap (83 und 94 von 100 Instanzen, klein und mittel), nicht bei assign_side und setpart (0 von 400).
• Tauchen und Pump scheitern messbar: das Tauchen mit Propagation in Sackgassen (cover_card, setpart und seqprec mittel), der Pump an seiner Iterationsgrenze (geprüft an binpack mittel mit 40 Instanzen).
• Die Kaskade löst 2 399 von 2 400 Instanzen, hört aber bei der ersten zulässigen Lösung auf: im Mittel über die jeweils gelösten Instanzen 22,0 % Lücke gegen 7,1 % beim Tauchen, in 15 von 24 Zellen größer.

Was sie nicht belegt:

• Andere Instanzen: Es sind erzeugte Instanzen mit 6 bis 120 ganzzahligen Variablen, nur 0/1. Die Zahlen verschieben sich mit der Größe (seqprec Runden mit Propagation 77 → 47 von 100, cover_card 77 → 4, Tauchen bei cover_card 100 → 64). Allgemeine ganzzahlige Variablen sind nicht gemessen. Die Parameter der Instanzerzeuger (Kostenbereiche, Dichte, Enge der Kapazitäten) sind hier nicht genannt.
• Die Methodenklasse: Gemessen ist die benannte Regel. „Tauchen“ ist hier Fractional, Coefficient oder Guided mit chronologischem Rückschritt, „Pump“ der Pump nach Fischetti, Glover und Lodi mit den genannten Einstellungen (Zielgewicht nach Achterberg und Berthold).
• Die Ursache der Sackgassen in anderen Zellen: Tauchgänge sind auf 400 LPs begrenzt; in cover_card, setpart und seqprec mittel war jeder Fehlschlag eine Sackgasse, in anderen Zellen ist das nicht untersucht.
• Eine Abstimmung: Die Einstellungen (20 Rückschritte, T = 10, Abnahmefaktor 0,9 des Zielgewichts, 15 Iterationen Wartezeit, 10 Neustarts) stammen aus der früheren Messung (die Neustarts dort auf getrennten Zufalls-Seeds abgestimmt) und wurden im Bau nicht neu abgestimmt; Rundungsschwelle, Rückschritte und Neustarts sind über alle Werte gemessen, nicht abgestimmt.
• Den Wert einer Startlösung für andere Löser: Der Vergleichsbaum ist einfach (ohne Schnitte, Presolve und Warmstart, höchstens 1 000 LPs). Instanzen ohne Beweis im Limit fehlen in den gepaarten Zahlen: bei der Tiefensuche mkp 7, cover_card 6, mknap 4 und binpack 4 von je 120, bei der Suche nach bester Schranke binpack 22 und mknap 4 von 120. Gerade die schweren Instanzen fehlen also, wo eine Startlösung am meisten bringen könnte.
• Eine Wirkung des Zielgewichts allein: Die kleinere Lücke mit Zielgewicht ist zum größten Teil eine Auswahl der leichteren Instanzen (gepaart bei mknap mittel größer statt kleiner).
• Optimalität: Eine Heuristik allein beweist keine; ein Beweis entsteht nur, wenn ihre obere Schranke die untere (etwa den aufgerundeten LP-Wert) erreicht. Die Lücke kennt, wer das Optimum separat berechnet (HiGHS-MILP; in der Landkarte nur Instanzen mit bewiesenem Optimum).
• Rechenzeit, Familien mit mehr als 150 ganzzahligen Variablen, Schnitte und Presolve im Vergleichsbaum, Relax-and-Fix, RINS und Local Branching: nicht gemessen; gezählt werden LPs.
• Plattformunabhängigkeit der Einzelzahlen: Welche LP-Ecke HiGHS bei Mehrdeutigkeit liefert, kann zwischen Windows und Linux abweichen; einzelne LP-Zahlen können sich um wenige verschieben.

Verweise

Der Vorgänger in dieser Reihe rechnet am Rucksack mit einer einzigen ≤-Zeile, in der Runden trivial zulässig ist:

• Mit Schnitten: die branch-cut-demo kombiniert Verzweigen mit Schnitten, ohne die Frage, wann man einen LP-Wert runden darf.
• Mit Suchbaum: die branch-bound-demo beweist am Rucksack die beste Auswahl mit einem Suchbaum.

Quellen

• Fischetti, M., Glover, F., Lodi, A. (2005): The feasibility pump. Mathematical Programming 104, 91–104 (der Pump).
• Achterberg, T., Berthold, T. (2007): Improving the feasibility pump. Discrete Optimization 4, 77–86 (das Zielgewicht).
• Quelltext, Messungen und Tests der Demo: github.com/sebastian-hanisch/primalheuristiken-demo.

Die beiden Aufsätze sind so in der README und in der Demo genannt und nicht nachgeschlagen. Herleitung, Beispielrechnung und die gepaarte Nachrechnung beim Zielgewicht sind Rechnungen dieser Seite aus Programmtext und gespeicherter Messung der Demo, keine Zitate; die Tauchrechnung des Beispiels ist ein Lauf des Demo-Programms.