<p>If $m$ is small enough, you can do better than the naive algorithm, i.e., better than $2^n$ time.  Here "small enough" means that $m$ is smaller than something like $n/\lg n$.  The running time will still be exponential -- e.g., it might be $2^{n/2}$ time -- but it'll be faster than the naive algorithm.</p>

<p>Incidentally, it looks like this does allow us to solve the problem in faster than $2^n$ time for some cases where the matrix $A$ has a super-linear number of entries.  I don't know how to square that with the other answer provided here.  Consequently, you should check my answer carefully: it might indicate that I have made a serious mistake somewhere.</p>

<hr>

<p>The basic approach: write $x=(x_0,x_1)$, where $x_0$ holds the first $n/2$ components of $x$ and $x_1$ holds the last $n/2$ components; and similarly $A=(A_0,A_1)$, where $A_0$ has the left $n/2$ columns of $A$ and $A_1$ the right $n/2$ columns.  Now $Ax \le b$ can be re-written in the form</p>

<p>$$A_0 x_0 + A_1 x_1 \le b,$$</p>

<p>or equivalently,</p>

<p>$$A_0 x_0 \le b - A_1 x_1.$$</p>

<p>Enumerate all $2^{n/2}$ possibilities for $A_0 x_0$, and let $S$ denote the set of possible values, i.e.,</p>

<p>$$S=\{A_0 x_0 : x_0 \in \{0,1\}^{n/2}\}.$$</p>

<p>Similarly, enumerate the set $T$ of all $2^{n/2}$ possibilities for $b - A_1 x_1$, i.e.,</p>

<p>$$T = \{b - A_1 x_1 : x_1 \in \{0,1\}^{n/2}\}.$$</p>

<p>Now the problem becomes</p>

<blockquote>
  <p>Given sets $S,T \subseteq \mathbb{Z}^{m}$ of size $2^{n/2}$, does there exist $s\in S$ and $t \in T$ such that $s\le t$?</p>
</blockquote>

<p>(Here $\le$ is taken pointwise, i.e., we require that $s_i \le t_i$ for all $i$.)</p>

<p>The latter problem is <a href="https://cs.stackexchange.com/q/13927/755">discussed on CS.StackExchange</a>, and there is apparently an algorithm for it that runs in time $O(2^{n/2} (n/2)^{m-1})$.  If $m$ is sufficiently small (say, smaller than $n/\lg n$), then it follows that the total running time will be less than $2^n$, as desired.</p>

<hr>

<p>To help make this result sound more plausible, here's some very crude intuition.  If we take the extreme case where $m=1$, of course this can be solved quickly.  (There's actually a much simpler algorithm for the special case where $m=1$: let $x_i=1$ if $A_{1,i}\le 0$, otherwise $x_i=0$; now if any feasible solution exists, then this $x$ will be one.)</p>

CC BY-SA 3.0
2013-08-30T00:10:22.117Z
The algorithm from my answer also reduces to the vector problem described in your answer using the same method, i.e. split the variables and list all their assignments.
Stefan Schneider
CC BY-SA 3.0
2013-08-31T05:04:36.227Z
There are algorithms for the general integer programming problem whose running time has a $2^{O(m)}$ dependence on dimension, and polynomial dependence on everything else. See http://dl.acm.org/citation.cfm?id=380857.
Sasho Nikolov
CC BY-SA 3.0
2013-08-29T23:40:33.573Z
2013-08-29T23:47:13.517Z
2017-04-13T12:48:30.830Z
D.W.
<p>If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.</p>

<p>However, there is an algorithm due to <a href="http://arxiv.org/abs/1212.4548">Impagliazzo, Paturi, and myself</a> that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.</p>

CC BY-SA 3.0
2013-07-27T06:12:46.667Z
2013-07-27T06:15:53.150Z
2013-07-27T06:15:53.150Z
Stefan Schneider
<p>Are there known algorithms for the following problem that beat the naive algorithm?</p>
<blockquote>
<p>Input: A system <span class="math-container">$Ax \le b$</span> of <span class="math-container">$m$</span> linear inequalities.</p>
<p>Output: A feasible solution <span class="math-container">$x^*\in \{0,1 \}^n$</span> if one exists.</p>
</blockquote>
<p>Assume that <span class="math-container">$A$</span> and <span class="math-container">$b$</span> have integer entries. I'm interested in worst-case bounds.</p>

<np-hardness><integer-programming><exp-time-algorithms>
Exact exponential-time algorithms for 0-1 programming
Austin Buchanan
# Exact exponential-time algorithms for 0-1 programming

(Asked by: username_0 on 2013-07-27)

Are there known algorithms for the following problem that beat the naive algorithm?

> Input: A system $Ax \le b$ of $m$ linear inequalities.
>
> Output: A feasible solution $x^\*\in \{0,1 \}^n$ if one exists.

Assume that $A$ and $b$ have integer entries. I'm interested in worst-case bounds.

**Tags:** np-hardness, integer-programming, exp-time-algorithms

---

## 2 answers

### Answer by username_2 on 2013-07-27. Score: 14 | Accepted answer

If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.

However, there is an algorithm due to [Impagliazzo, Paturi, and myself](http://arxiv.org/abs/1212.4548) that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.


---

### Answer by username_1 on 2013-08-29. Score: 1

If $m$ is small enough, you can do better than the naive algorithm, i.e., better than $2^n$ time. Here "small enough" means that $m$ is smaller than something like $n/\lg n$. The running time will still be exponential -- e.g., it might be $2^{n/2}$ time -- but it'll be faster than the naive algorithm.

Incidentally, it looks like this does allow us to solve the problem in faster than $2^n$ time for some cases where the matrix $A$ has a super-linear number of entries. I don't know how to square that with the other answer provided here. Consequently, you should check my answer carefully: it might indicate that I have made a serious mistake somewhere.

---

The basic approach: write $x=(x\_0,x\_1)$, where $x\_0$ holds the first $n/2$ components of $x$ and $x\_1$ holds the last $n/2$ components; and similarly $A=(A\_0,A\_1)$, where $A\_0$ has the left $n/2$ columns of $A$ and $A\_1$ the right $n/2$ columns. Now $Ax \le b$ can be re-written in the form

$$A\_0 x\_0 + A\_1 x\_1 \le b,$$

or equivalently,

$$A\_0 x\_0 \le b - A\_1 x\_1.$$

Enumerate all $2^{n/2}$ possibilities for $A\_0 x\_0$, and let $S$ denote the set of possible values, i.e.,

$$S=\{A\_0 x\_0 : x\_0 \in \{0,1\}^{n/2}\}.$$

Similarly, enumerate the set $T$ of all $2^{n/2}$ possibilities for $b - A\_1 x\_1$, i.e.,

$$T = \{b - A\_1 x\_1 : x\_1 \in \{0,1\}^{n/2}\}.$$

Now the problem becomes

> Given sets $S,T \subseteq \mathbb{Z}^{m}$ of size $2^{n/2}$, does there exist $s\in S$ and $t \in T$ such that $s\le t$?

(Here $\le$ is taken pointwise, i.e., we require that $s\_i \le t\_i$ for all $i$.)

The latter problem is [discussed on CS.StackExchange](https://cs.stackexchange.com/q/13927/755), and there is apparently an algorithm for it that runs in time $O(2^{n/2} (n/2)^{m-1})$. If $m$ is sufficiently small (say, smaller than $n/\lg n$), then it follows that the total running time will be less than $2^n$, as desired.

---

To help make this result sound more plausible, here's some very crude intuition. If we take the extreme case where $m=1$, of course this can be solved quickly. (There's actually a much simpler algorithm for the special case where $m=1$: let $x\_i=1$ if $A\_{1,i}\le 0$, otherwise $x\_i=0$; now if any feasible solution exists, then this $x$ will be one.)

> **Comments:**
> **username_2**: The algorithm from my answer also reduces to the vector problem described in your answer using the same method, i.e. split the variables and list all their assignments.  
> **username_3**: There are algorithms for the general integer programming problem whose running time has a $2^{O(m)}$ dependence on dimension, and polynomial dependence on everything else. See http://dl.acm.org/citation.cfm?id=380857.  

---

