Big M: Nebenbedingungen an- und ausschalten
About this app
Hilfs-Binärvariable mit großem M: Either-or (3x₁ + 2x₂ ≤ 18 oder x₁ + 4x₂ ≤ 16) als nicht-konvexe Vereinigung und Fixkosten mit Sprung. Die LP-Relaxation bläht sich mit M auf, Schranke über M logarithmisch, zu kleines M schneidet echte Lösungen ab. Mₘᵢₙ markiert, getrennte M₁/M₂, y-Schnitt, alle Werte exakt.
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
Many models are almost linear programs until a yes-or-no condition appears: only one of two constraints has to hold, or an activity causes a setup cost as soon as it is used at all. The trick is a binary variable y and a large constant M. The constraint a·x ≤ b + M·y is satisfied by every reasonable solution when y = 1, so it is switched off. M must be large enough not to cut off any feasible solution, and as small as possible otherwise. Too large an M makes the LP relaxation weak and the solver slow. (Not to be confused with the big M method of the simplex algorithm, which penalises artificial variables.)
What the app shows
In the either-or case, 3x₁ + 2x₂ ≤ 18 or x₁ + 4x₂ ≤ 16 must hold. On the left are the two regions, whose union is not convex, with the LP relaxation as a veil on top, cut-off parts hatched and the optima of MIP and relaxation. On the right the value of the relaxation over M on a logarithmic axis: from M = 30 on the MIP stays at 16, while the relaxation grows to 23.5 at M = 60 and 258.5 at M = 1000. In the fixed-charge case (€1000 setup cost, €20 per unit, capacity 50) the app shows the true cost function with its jump and the relaxed line (20 + 1000/M)·x.
Try it yourself
Drag M in the right card from 10 to 1000. Below 30 a piece of B is missing and the MIP returns a wrong optimum, for example 13 instead of 16 at M = 20. Above it the true region stays the same; only the relaxation inflates. Switch to separate M₁ and M₂: with 30 and 20 the relaxation is exactly the convex hull of both triangles. The slider for a continuous y shows single slices of the relaxation. For the fixed charge you choose the quantity x and see how much the relaxation underestimates the setup cost.
Frequently asked questions
- What is a big M constraint?
- A constraint of the form a·x ≤ b + M·y with a binary variable y and a large constant M. For y = 0 the original constraint a·x ≤ b holds; for y = 1 it is relaxed so far that every reasonable solution satisfies it. This is how either-or conditions, K-out-of-N conditions and fixed charges are written in a mixed integer program.
- How large must M be?
- M must be at least as large as the largest violation of the switched-off constraint over the remaining feasible solutions. In the example 3x₁ + 2x₂ ≤ 18 or x₁ + 4x₂ ≤ 16, 3x₁ + 2x₂ reaches at most 48 on the second region, so M₁ ≥ 30; conversely M₂ ≥ 20. For a fixed charge with x ≤ M·y the largest possible quantity, such as the capacity, is enough.
- Why does a very large M like 10⁹ hurt?
- The model stays correct, but the LP relaxation, in which y is continuous between 0 and 1, becomes very weak. Its bound lies far above the true optimum, branch and bound can hardly prune branches and needs much longer. On top of that come numerical problems when 10⁹ sits next to coefficients like 0.3. If M is too small instead, the model cuts off feasible solutions and returns a wrong optimum.
- What can I adjust in the app?
- The case (either-or or fixed charge), one common M or separate M₁ and M₂ between 10 and 1000, a slice of the relaxation for a continuous y and, for the fixed charge, the quantity x. M can be dragged directly in the right card. The Model panel shows the formulas with M substituted and all optima exactly as fractions.
Subject: Operations research
More from Operations research
- Dijkstra's algorithm
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Linear problems made visual
- Nebenbedingungen verschärfen (Tightening)
- Simplex in space
- Simplex algorithm
- Tabu search on a small TSP
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps