<p>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 <a href="http://www.amazon.co.uk/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp/0486402584" rel="noreferrer">Papadimitriou and Steiglitz' Combinatorial Optimization book</a> (paraphrased): </p>

<blockquote>
  <p>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]$.</p>
</blockquote>

<p>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.)</p>

<p>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?</p>

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

CC BY-SA 3.0
2016-04-14T22:04:33.613Z
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$.
Thomas Steinke
CC BY-SA 3.0
2016-04-14T22:08:31.847Z
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$.
Dominik Peters
CC BY-SA 3.0
2016-04-14T22:51:34.683Z
I would guess that you can get tight bounds using http://www.sciencedirect.com/science/article/pii/S0097316597927801
Sasho Nikolov
CC BY-SA 3.0
2016-04-15T00:33:32.233Z
@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.
Sasho Nikolov
<linear-programming><integer-programming>
Are there integer programs with small coefficients that only have large solutions?
Dominik Peters
# Are there integer programs with small coefficients that only have large solutions?

(Asked by: username_0 on 2016-04-14)

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](http://www.amazon.co.uk/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp/0486402584) (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.

**Tags:** linear-programming, integer-programming
> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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$.  
> **username_2**: I would guess that you can get tight bounds using http://www.sciencedirect.com/science/article/pii/S0097316597927801  
> **username_2**: @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.  

---

## 0 answers

