1
$\begingroup$

If $f(A,b,c)$ is the optimal value of a linear program

$\min c.x$

subject to $A.x \leq b ; x \geq 0.$

Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of points in which the optimal value is well-defined/finite? Here, we assume that the matrix $A$ is an $m \times n$ matrix.

Improve this question
$\endgroup$
3
  • $\begingroup$ Not sure if this is correct, but isn't this answered by "Hoffmann constants"? $\endgroup$
    – Dirk
    Commented Sep 24, 2023 at 15:34
  • $\begingroup$ @Dirk Perhaps a math textbook reference or theorem would be good. Please feel free to share any formal argument for a proof regarding the above mathematical statement. $\endgroup$
    – Pathikrit Basu
    Commented Sep 24, 2023 at 23:50
  • $\begingroup$ That's not really my area of math… However, I think that Hoffmann constants are not the right thing to look at. You may find some (local) results under "sensitivity analysis of LPs", though. $\endgroup$
    – Dirk
    Commented Sep 25, 2023 at 7:46

0

Reset to default

You must log in to answer this question.