Skip to content
All apps

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

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