Parametric Programming: Tracing the Optimal Basis

Parametric programming examines how an LP's optimal solution evolves as a coefficient varies along a line. Consider a maximization LP whose objective coefficients are perturbed as $\mathbf{c}+\theta\mathbf{d}$ for a real parameter $\theta$. At $\theta=0$ the current basis is optimal, so every non-basic reduced cost satisfies $\bar{r}_j \le 0$.

As $\theta$ changes, each non-basic reduced cost moves linearly:

$$\bar{r}_j(\theta) \,=\, \bar{r}_j + \theta\,\bar{s}_j,$$

where $\bar{s}_j$ is the parametric reduced cost coefficient for variable $x_j$.

The basis remains optimal as long as $\bar{r}_j(\theta) \le 0$ for every non-basic $j$. Solving each inequality for $\theta$ yields the range of optimality $[\theta_{\min},\theta_{\max}]$, where

$$\theta_{\max} \,=\, \min_{\bar{s}_j>0}\,\dfrac{-\bar{r}_j}{\bar{s}_j}, \qquad \theta_{\min} \,=\, \max_{\bar{s}_j<0}\,\dfrac{-\bar{r}_j}{\bar{s}_j}.$$

If no $\bar{s}_j$ is positive, take $\theta_{\max}=+\infty$. If none is negative, take $\theta_{\min}=-\infty$.

For a tiny illustration, suppose a single non-basic variable has $\bar{r}_1=-4$ and $\bar{s}_1=2$. The optimality condition becomes

$$-4 + 2\theta \le 0 \quad\Longrightarrow\quad \theta \le 2,$$

so the basis stays optimal on $(-\infty,\,2]$.