5
$\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.

Improve this question
$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 0:33

0

Reset to default

Your Answer

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