Auditing a MIP Formulation for Correctness

Audit mixed-integer programming formulations by checking Big-M validity and tightness, using arc/plant capacity as the natural Big-M, verifying logical linearizations via truth tables, and preferring disaggregated activation constraints over aggregated ones for a stronger LP relaxation.

Step 1 of 157%

Tutorial

Validity and Tightness of a Big-M

After a MIP is written down, we audit it before sending it to the solver. The audit verifies that every feasible integer assignment encodes a feasible solution of the original problem, and vice versa. A formulation that is logically correct but uses loose Big-M values is still valid — it just has a weak LP relaxation and will solve slowly inside branch-and-cut.

For any constraint of the form

x \le M \cdot y, \qquad y \in \{0,1\}, \quad x \ge 0,

the audit asks two questions:

Validity. Is $M$ at least as large as the maximum value $x$ can take when $y = 1$ ? If $M$ is too small, legitimate solutions are cut off.
Tightness. Is $M$ as small as possible while remaining valid? Any slack inflates the LP relaxation and weakens the cuts that branch-and-cut can generate.

For example, if $0 \le x \le 12,$ every $M \ge 12$ is valid, and $M = 12$ is the tightest valid choice. Choosing $M = 1000$ is valid but extremely loose.