Adding a New Constraint to an Optimal LP

Suppose we have already solved a linear program (LP) and obtained the optimal solution $\mathbf{x}^*$ with optimal objective value $z^*.$ What happens if we then add a brand-new constraint to the problem?

The procedure has two steps.

Step 1. Substitute $\mathbf{x}^*$ into the new constraint.

Step 2. Check whether the constraint is satisfied.

• If $\mathbf{x}^*$ satisfies the new constraint, then $\mathbf{x}^*$ remains feasible. Adding a constraint can only shrink the feasible region, so $\mathbf{x}^*$ is still optimal and $z^*$ is unchanged.

• If $\mathbf{x}^*$ violates the new constraint, then $\mathbf{x}^*$ is no longer feasible. The LP must be re-solved, and the new optimum will be no better than $z^*.$

For example, suppose a max LP has optimum $\mathbf{x}^* = (3, 4)$ with $z^* = 17,$ and we add the constraint $x_1 + x_2 \le 10.$ Substituting,

$$3 + 4 = 7 \le 10. \;\checkmark$$

The constraint is satisfied, so the optimum is unchanged: $\mathbf{x}^* = (3, 4),\; z^* = 17.$