Return to 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.

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

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.

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.

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.

Now for the maximization problem. Replace every variable $y_j$ (resp. $\overline{y}_j$) from the minimization problem with its opposite variable $\overline{y}_j$ (resp. $y_j$). Change the $\ge$ constraints to $\le$ constraints, and change the right-hand-side to $(\#vars-1)$ where $\#vars$ is the number of variables in that constraint (or the number of literals in the clause). So the constraint $y_1 + \overline{y}_2 + y_3 \ge 1$ becomes $\overline{y}_1 + y_2 + \overline{y}_3 \le 2$. We will also have $y_j + \overline{y}_j \le 1$ constraints. The new objective is to maximize $\sum_{j=1}^n (y_j + \overline{y}_j)$. Again, the objective will be $n$ iff the SAT instance is satisfiable.

Thanks to Stefan Schneider for the correction.

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.