# Exact exponential-time algorithms for 0-1 programming

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.

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 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)}}$.

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, 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.)

• 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 Aug 30 '13 at 0:10
• 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 dl.acm.org/citation.cfm?id=380857. – Sasho Nikolov Aug 31 '13 at 5:04