2
$\begingroup$

Consider the set of all linear programs of the form:

maximize $c x$

subject to $A x \leq b$

$x \geq 0$

where there are $m$ variables, $n$ constraints, and all coefficients in $A, b, c$ are integers from a given finite set $K$.

Since the number of such programs is finite, the number of possible optimal values of these programs (those that have an optimal value, that is, are feasible and bounded) is finite.

My questions are:

  • Is there any non-trivial upper bound on the number of possible optimal values? (besides the number of possible programs).

  • Is there any simple representation for the set of all possible optimal values, as a function of $m, n$ and $K$?

$\endgroup$
8
  • $\begingroup$ @D.W. For my use-case, we can assume that $K = \{0,\ldots,k\}$ for some $k$. $\endgroup$ Nov 12, 2022 at 20:28
  • 1
    $\begingroup$ What's the best lower bound and best upper bound you have? A lower-bound is $\Omega(2^n)$, via a program like $x_0=1$, $x_{i+1}=2x_i$. (If $k=1$, instead use $t_i=x_i$, $x_{i+1}=x_i+t_i$.) By similar reasoning, there is $z=\Omega(2^n)$ such that all values in the set $\{0,1,2,\dots,z\}$ can occur as optimal values of some program. $\endgroup$
    – D.W.
    Nov 12, 2022 at 21:41
  • $\begingroup$ @D.W., with a small modification of your construction, I think we can get $\Omega(k^n)$ lower bound. (However, I don't think you can write $x_{i+1} = 2 x_{i}$ in this setup, since all coefficients are non-negative) $\endgroup$
    – Dmitry
    Nov 12, 2022 at 22:30
  • $\begingroup$ @ErelSegal-Halevi, what kind of result do you want? If for $m=\Theta(n)$ we show $k^{\Omega(n)}$ lower bound, does it suffice? What about $k^{\Omega(n^2)}$ (where the constant in $\Omega$ may be less than $1$)? Also, do you have any reason to suspect that there might be a non-trivial upper bound? $\endgroup$
    – Dmitry
    Nov 12, 2022 at 22:30
  • $\begingroup$ @D.W., $x_{i+1} = k x_i$ can be written $k x_i + (-1) x_{i+1} = 0$. The coefficient in front of $x_{i+1}$ is negative, while it should be in $0, \ldots, k$ (also, it should be an inequality, not equality, which in this setup might complicate matters). $\endgroup$
    – Dmitry
    Nov 12, 2022 at 23:37

1 Answer 1

2
$\begingroup$

For simplicity, assume $0 \in K$. It allows us to treat $x \geq 0$ constraints in the same way as other constraints. For an LP that has an optimal solution, there is an optimal solution in the basis. Therefore, it is sufficient to consider the set of possible solutions for systems of $m$ non-singular linear equations on $m$ variables.

By Cramer's rule, a solution of a system of linear equations $Ax = b$ can be represented by ratios of determinants $x_i = \frac{\det(A_i)}{\det(A)}$. Therefore, an optimal value of an LP can be represented by a ratio $\frac{\sum_i c_i \det(A_i)}{\det(A)}$.

If the maximum absolute value of the coefficients is small, say $k$, we can use Hadamard's theorem. The absolute value of the denominator is at most $\det(A)$ is $k^m m^{m/2}$. Similarly, the numerator has an absolute value at most $mk \cdot k^m m^{m/2}$. Because both the numerator and the denominator are integers, the number of possible values is $O(k^{2m+1} m^{m+1})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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