4
$\begingroup$

It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou and Steiglitz' Combinatorial Optimization book (paraphrased):

Consider the ILP $$Ax \le b, \quad x \ge 0, \quad x \in \mathbb Z^n,$$ where $A$ is an $m\times n$ matrix. Let $r = \max |a_{ij}|$ be the largest value appearing in $A$, and let $s = \max |b_j|$. Then if the ILP has a feasible solution, then it has a feasible solution $x$ with $x_i \le (n+m)(mr)^{2m+3}(1+s)$ for each $i \in [n]$.

Via binary encoding, this implies that integer programming is contained in NP. (The intuition is that large coefficients are required to induce sharp angles in the polyhedron. Results like above can be found in many textbooks, but the following question never seems to be addressed.)

I wonder whether the upper bound given is actually attained. Are there examples of feasible integer programs where all coefficients are small (maybe even $|a_{ij}|, |b_j| \le 1$) and yet all feasible solutions contain exponentially large numbers?

Equivalently, I wonder whether feasible integer programs encoded in unary have a solution whose unary size is polynomially bounded in the input size.

$\endgroup$
  • 8
    $\begingroup$ Consider the ILP $x_0=1$ and $x_i \geq 2x_{i-1}$ for all $i$. This has small coefficients but only exponentially-large solutions i.e. $x_i \geq 2^i$. $\endgroup$ – Thomas Apr 14 '16 at 22:04
  • 1
    $\begingroup$ Ha! Thanks, that answers it. The same can be achieved using only $\pm 1$ coefficients, by copying values $y_i = x_i$ and requiring $x_{i+1} \ge x_i + y_i$. $\endgroup$ – Dominik Peters Apr 14 '16 at 22:08
  • $\begingroup$ I would guess that you can get tight bounds using sciencedirect.com/science/article/pii/S0097316597927801 $\endgroup$ – Sasho Nikolov Apr 14 '16 at 22:51
  • $\begingroup$ Why does it follow "that integer programming is contained in NP"? ​ (I only see "Is there a feasible solution?" being in NP, and integer programming being in NPO.) ​ ​ ​ ​ $\endgroup$ – user6973 Apr 15 '16 at 0:13
  • 3
    $\begingroup$ @RickyDemer I don't see the point of such comments on a research level website. It's a fairly common abuse of terminology to say "function problem X is in NP" when one means that some natural decision version of X is in NP. Yes, it's sloppy, but if the assumption is that researchers use this site to talk to other researchers, then we can trust each other to know what we mean. $\endgroup$ – Sasho Nikolov Apr 15 '16 at 0:33

Your Answer

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

Browse other questions tagged or ask your own question.