the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side

Question

Consider a linear programming (LP) problem \begin{align} M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}. \end{align} Suppose the LP is feasible and bounded for all values of $b$. We know that $M(b)$ may not be a function, as $M(b)$ may not be unique. If at a given $b$, the LP has a unique solution, then "locally" M(b) is a linear function of $b$. This is because the basic feasible solution is $x_{B}=B^{-1}b$, where $B$ is the optimal basis. So, for sufficiently small changes in $b$, the optimal basis $B$ does not change, so the optimal solution will be $M(b+\hat{b})=B^{-1}b + B^{-1}\hat{b}$, where $\hat{b}$ is a small perturbation in $b$.

My question is what can be said for more global changes where the optimal basis changes? Does $M(b)$ have a piecewise linear behaviour?

Answer 1

In general, if the LP is bounded, the optimal set $M(b)$ is a face of the feasible set $P = \{ x | Ax = b, x \geq 0\}$ (which is a polyhedral set). In fact, $M$ is a function, but one that maps a vector $b \in \mathbb{R}^{m}$ to a set of points $M(b) \subseteq \mathbb{R}^{n}$.

Thus, in order to talk about piece-wise linearity of $M$, you must define what you mean by piece-wise linearity of such a function.

The objective function of an LP is a piece-wise linear function of $b$, though.

That being said, take the example \begin{align} \min_{x, y} \ \ \ & -x - y\\ \text{s.t.} \ \ \ & x + y = b\\ & x, y \geq 0 \end{align}

Here,

• If $b < 0$, the LP is infeasible.
• $M(0) = \{(0, 0)\}$ (a singleton)
• $M(b > 0) = \{(x, y) \geq 0 \ | \ x + y = b\}$ (a one-dimensional segment)

so the dimension of $M(b)$ may change for small variations in $b$.

Two side remarks:

• depending on the data $A, c$, there may exist values of $b$ for which the LP is unbounded or infeasible, so the assumption that $LP$ is bounded and feasible for all values of $b$ may not hold in practice.
• Changing the primal right-hand side corresponds to changing the dual objective. This perspective may simplify the analysis.