Skip to content
All apps

Nebenbedingungen verschärfen (Tightening)

About this 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.

With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.

What it is about

In the preprocessing of integer programs, a constraint a₁x₁ + … + aₙxₙ ≤ b with binary variables can be tightened: coefficients and right-hand side are changed so that exactly the same binary points stay feasible while the LP relaxation gets smaller. The procedure: S is the sum of the positive coefficients. If some aⱼ ≠ 0 satisfies S < b + |aⱼ|, set aⱼ := S − b and b := S − aⱼ for aⱼ > 0, or aⱼ := b − S for aⱼ < 0, and repeat until no coefficient qualifies. Smaller relaxations give better bounds for branch and bound.

What the app shows

The constraint appears as a line in the unit square or as a plane in the unit cube, the binary points as filled (feasible) or hollow (infeasible) corners. Every step runs in four phases: test with numbers, choose the coefficient, rotate the constraint about a hinge on a face of the cube, and verify all binary points. The slack to the fullest binary point disappears, a wedge of fractional points falls away, and area or volume and the LP bound are shown before and after. Six examples in 2D and 3D, including the slide 2x₁ + 3x₂ ≤ 4 and a case where tightening does not reach the convex hull.

Try it yourself

In the slide example choose a₂ instead of a₁ first and compare the LP bounds on both paths: the end is the same, the path is not. Scrub the timeline into the rotation and watch aⱼ and b move together. In space, show the hull of the feasible binary points and see what is still missing after the last step. Enter your own coefficients; the app recognises redundant or fixing constraints.

Frequently asked questions

What does tightening a constraint mean?
A constraint with binary variables is replaced by another one that admits exactly the same 0-1 solutions but has a smaller LP relaxation. For 2x₁ + 3x₂ ≤ 4 the end result is x₁ + x₂ ≤ 1: in both cases only (1, 1) is forbidden, but the relaxation shrinks from 11/12 to 1/2 of the area.
Why does tightening never lose feasible solutions?
For aⱼ > 0 the constraint is unchanged on the face xⱼ = 1 of the cube, because b − aⱼ stays the same. On the face xⱼ = 0 it had slack: even the fullest binary point there stayed below b. The constraint turns about its trace on xⱼ = 1 until it touches that point, and cuts off only fractional points.
Is the tightened relaxation always the convex hull?
No. For 6x₁ + 3x₂ + 5x₃ ≤ 10 the procedure ends at 4x₁ + 3x₂ + 4x₃ ≤ 7. The region is smaller but still has fractional corners; the convex hull needs the cover cut x₁ + x₃ ≤ 1. That is what cutting planes are for.
Can I tighten my own constraints in the app?
Yes. In your own example you set integer coefficients, right-hand side and objective in 2D or 3D. Redundant constraints and constraints that fix a variable are shown as special cases with a hint.

Subject: Operations research

More from Operations research

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps