0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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})$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.