Are there known algorithms for the following problem that beat the naive algorithm?
Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.
Output: an optimal solution $x^*$ to $\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$.
This question is a refined version of my previous question Exact exponential-time algorithms for 0-1 programming.
if the number of non-zero coefficients in $A$ is linear in $n$, there is an algorithm that solves this problem in less than $2^n$ time.
Here's how it works. We use the standard connection between an optimization problem and its corresponding decision problem. To test whether there exists a solution $x$ where $Ax\le b$ and $c^T x \ge \alpha$, we will form a decision problem: we will adjoin the constraint $c^T x\ge \alpha$ to the matrix $A$, and test whether there exists any $x$ such that $Ax \le b$ and $-c^T x \le -\alpha$. In particular, we will form a new matrix $A'$ by taking $A$ and adding an extra row containing $-c^T$, and we will form $b'$ by taking $b$ and adjoining an extra row with $-\alpha$. We obtain a decision problem: does there exist $x \in \{0,1\}^n$ such that $A' x \le b'$? The answer to this decision problem tells us whether there exists a solution to the original optimization problem of value $\alpha$ or greater. Moreover, as explained in the answer to your prior question, this decision problem can be solved in less than $2^n$ time, if the number of non-zero coefficients in $A'$ is linear in $n$ (and thus if the number of non-zero coefficients in $A$ is linear in $n$). Now we can use binary search on $\alpha$ to solve your optimization problem in less than $2^n$ time.
My thanks to AustinBuchanan and Stefan Schneider for helping to debug an earlier version of this answer.
If we consider the minimization problem $\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \}$, then the following reduction shows that an algorithm running in time $O(2^{\delta n/2})$ for $\delta <1$ would disprove the SETH. A reformulation proves the same result for the intended problem (the maximization version).
Given an instance $\Phi = \wedge_{i=1}^m C_i$ of CNF-SAT with variables $\{x_j \}_{j=1}^n$, formulate a 0-1 IP with two variables $y_j, \overline{y}_j$ for each variable $x_j$ in the SAT instance. As usual, the clause $(x_1 \vee \overline{x}_2 \vee x_3)$ would be represented as $y_1 + \overline{y}_2 + y_3 \ge 1$. Then for every variable $x_j$ in the SAT instance, add a constraint $y_j + \overline{y}_j \ge 1$. The objective is to minimize $\sum_{j=1}^n (y_j + \overline{y}_j)$. The objective of the IP will be $n$ iff the SAT instance is satisfiable.
Thanks to Stefan Schneider for the correction.
Update: in On Problems as Hard as CNF-Sat the authors conjecture that SET COVER cannot be solved in time $O(2^{\delta n})$, $\delta <1$, where $n$ refers to the number of sets. If true, this would show that my problem cannot be solved in time $O(2^{\delta n})$ as well.
Update 2. As far as I can tell, assuming SETH, my problem cannot be solved in time $O(2^{\delta n})$, since it has been shown that Hitting Set (with a ground set of size $n$) cannot be solved in time $O(2^{\delta n})$.
