What linear program characterizes non-infinitesimal perturbations of a linear program?

Question

Suppose that I possess the solution to

$$ \max_x\ c^\top x \textrm{ subject to } Ax \le b_1. $$

How can I use this to more efficiently solve

$$ \max_x\ c^\top x \textrm{ subject to } Ax \le b_2? $$

Where $b_2 - b_1$ may be zero in many coordinates, but nonnegligibly small in others. My inntuition says that there is some linear program that looks like the dual that tidily captures the differences between the argmaxes?

Answer 1

There's a technique called parametric linear programming that can be used to find optimal solutions to all of the problems

$\max c^{T}x$

subject to

$Ax \leq b(t)$,

for $0 \leq t \leq 1$, where

$b(t)=b_{1}+t(b_{2}-b_{1})$

Answer 2

If $b_2\ge b_1$, then the optimal solution to the first problem is feasible to the second one. You can use an optimal basis from the first problem as a starting basis for the second one. This technique is called warm start in the literature.