Auditing an LP Formulation for Correctness

Before solving an LP, audit it. The first and most mechanical check is dimensional consistency.

Every term inside a single sum must share the same units. Every comparison (LHS vs. RHS, or each term of the objective) must produce the same units. If the objective is in dollars, every term $c_j x_j$ must work out to dollars. If a constraint's RHS is in labor-hours, every term $a_{ij} x_j$ on the LHS must be in labor-hours.

The coefficient $a_{ij}$ on $x_j$ must carry the units of (RHS units) per (units of $x_j$).

For instance, suppose a bakery makes $x_1$ loaves of bread and $x_2$ cakes, where bread uses $0.5$ kg of flour per loaf, cake uses $0.3$ kg per cake, and $50$ kg of flour is available. The flour constraint is

$$0.5\, x_1 + 0.3\, x_2 \le 50.$$

Units check: $(\text{kg}/\text{loaf})(\text{loaves}) + (\text{kg}/\text{cake})(\text{cakes}) = \text{kg}$, and the RHS is in kg. ✓

Now consider a flawed version that someone wrote in a hurry:

$$0.5\, x_1 + 3\, x_2 \le 50,$$

where the $3$ was copied from a different data row meaning "minutes of oven time per cake." The LHS mixes kg and minutes — the audit catches this immediately.