Complexity of a constrain-modified $0$-$1$-knapsack problem

91 Views Asked by At

If the constrain of a $0$-$1$-knapsack problem was replaced with a 2-SAT formula, e.g.

$\begin{align}\textrm{maximize} && \sum_{i = 1}^{n} x_i p_i \\ \textrm{s. t.} && (x_1 \lor \lnot x_4) \land (x_3 \lor \lnot x_2) \land \dots \textbf{= 1} \\ \\ x_i \in \{0,1\} \; , \; p_i \in \mathbb{Z} \quad \forall \; 1 \leq i \leq n\\ \end{align}$

will this problem still be NP-hard?

Basically I am optimizing among the solutions of a propositional 2-SAT-formula. (Solving the formula itself is in $\mathcal{P}$, obviously)

1

There are 1 best solutions below

1
On BEST ANSWER

The problem you describe is 0-1 integer programming slightly disguised. This is a known NP-hard optimization problem.

Maximizing $\sum_{i = 1}^{n} x_i p_i$ translates directly to the maximizing $c^Tx$ with the $p_i$'s appearing in the $c$ vector. The 2-SAT clauses can be reduced to a series of linear inequalities. E.g. $(x_3 \lor \lnot x_2)$ translates to $x_3 + (1 - x_2) \geq 1$. Each positive $x_i$ variable appears as itself and each negated $x_i$ is written as $1 - x_i$.