Zum Inhalt
Alle Apps

Nebenbedingungen verschärfen (Tightening)

Über diese App

Vorverarbeitung für Binärprogramme Schritt für Schritt, in 2D und 3D: Eine Bedingung a·x ≤ b wird so umgeschrieben, dass genau dieselben Binärpunkte zulässig bleiben, die LP-Relaxation aber schrumpft. Jeder Schritt (Prüfen S < b + |aⱼ|, Wählen, Drehen, Kontrolle) dreht die Gerade bzw. Ebene um ein Scharnier auf einer Würfelseite, bis die Luft zum vollsten Binärpunkt weg ist; der abgeschnittene Keil enthält keinen Binärpunkt. Sechs Beispiele (Folie 2x₁ + 3x₂ ≤ 4, negative Koeffizienten, schon scharf, Ecke abschneiden, drei Schritte, „reicht nicht“ mit Hülle und Cover-Schnitt) und ein eigenes; Fläche, Volumen und LP-Schranke vorher und nachher.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Worum es geht

Beim Preprocessing ganzzahliger Programme lässt sich eine Bedingung a₁x₁ + … + aₙxₙ ≤ b mit binären Variablen verschärfen: Koeffizienten und rechte Seite werden so geändert, dass genau dieselben Binärpunkte zulässig bleiben, die LP-Relaxation aber kleiner wird. Das Verfahren: S ist die Summe der positiven Koeffizienten. Gilt für ein aⱼ ≠ 0 die Ungleichung S < b + |aⱼ|, setzt man bei aⱼ > 0 aⱼ := S − b und b := S − aⱼ, bei aⱼ < 0 aⱼ := b − S, und wiederholt das, bis kein Koeffizient mehr passt. Kleinere Relaxationen liefern bessere Schranken für Branch and Bound.

Was die App zeigt

Die Bedingung erscheint als Gerade im Einheitsquadrat oder als Ebene im Einheitswürfel, die Binärpunkte als gefüllte (zulässig) oder hohle (unzulässig) Ecken. Jeder Schritt läuft in vier Teilphasen: Prüfen mit Zahlen, Wählen des Koeffizienten, Drehen der Bedingung um ein Scharnier auf einer Würfelseite und Kontrolle aller Binärpunkte. Die Luft zum vollsten Binärpunkt verschwindet, ein Keil aus gebrochenen Punkten fällt weg, Fläche oder Volumen und LP-Schranke werden vorher und nachher angezeigt. Sechs Beispiele in 2D und 3D, darunter die Folie 2x₁ + 3x₂ ≤ 4 und ein Fall, in dem Verschärfen nicht bis zur konvexen Hülle reicht.

Selbst ausprobieren

Wähle im Folienbeispiel erst a₂ statt a₁ und vergleiche die LP-Schranken auf beiden Wegen: Das Ende ist gleich, der Weg nicht. Spring mit der Zeitleiste in die Drehung und beobachte, wie aⱼ und b gemeinsam laufen. Blende im Raum die Hülle der zulässigen Binärpunkte ein und sieh, was nach dem letzten Schritt noch fehlt. Gib eigene Koeffizienten ein; redundante oder fixierende Bedingungen erkennt die App.

Häufige Fragen

Was bedeutet es, eine Nebenbedingung zu verschärfen?
Man ersetzt eine Bedingung mit binären Variablen durch eine andere, die genau dieselben 0-1-Lösungen zulässt, deren LP-Relaxation aber kleiner ist. Für 2x₁ + 3x₂ ≤ 4 ist das am Ende x₁ + x₂ ≤ 1: In beiden Fällen ist nur (1, 1) verboten, die Relaxation schrumpft aber von 11/12 auf 1/2 der Fläche.
Warum gehen beim Verschärfen keine zulässigen Lösungen verloren?
Bei aⱼ > 0 bleibt die Bedingung auf der Würfelseite xⱼ = 1 unverändert, weil b − aⱼ gleich bleibt. Auf der Seite xⱼ = 0 hatte sie Luft: Selbst der vollste Binärpunkt dort lag unter b. Die Bedingung dreht sich um ihre Spur auf xⱼ = 1, bis sie diesen Punkt berührt, und schneidet nur gebrochene Punkte ab.
Ist die verschärfte Relaxation immer die konvexe Hülle?
Nein. Für 6x₁ + 3x₂ + 5x₃ ≤ 10 endet das Verfahren bei 4x₁ + 3x₂ + 4x₃ ≤ 7. Das Gebiet ist kleiner, hat aber noch gebrochene Ecken; zur konvexen Hülle fehlt der Cover-Schnitt x₁ + x₃ ≤ 1. Dafür gibt es Schnittebenen.
Kann ich in der App eigene Bedingungen verschärfen?
Ja. Im eigenen Beispiel stellst du ganzzahlige Koeffizienten, rechte Seite und Zielfunktion in 2D oder 3D ein. Redundante Bedingungen und solche, die eine Variable fixieren, zeigt die App als Sonderfall mit Hinweis.

Fach: Operations Research

Mehr aus Operations Research

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps