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

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?

• You need to be a bit careful with the idea of "unique" solution. If the solution for a particular $b$ is degenerate, then the optimal value of $x$ for that $b$ may be unique but the basis is not. So perturbations in some directions, no matter how small, may change the basis. – prubin Oct 27 '20 at 19:11

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.
• Thanks @mtanneau. This is a nice discussion. – Arthur Oct 27 '20 at 19:53