# Tag Info

As j_random_hacker suggested, we can reduce MAX-2-SAT to this problem. Given an instance of MAX-2-SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we can encode it as the following constraints: For each variable $x_i$, add $m$ identical constraints: $x_i\le 0$ (if identical constraints are not allowed, we can use $x_i\le 0,x_i\le 0.1,x_i\le 0.01,\... 0 Instead of having a constraint$C_j: \sum b_{ij}x_i ≤ c_j$, introduce another variable$y_j$, change the constraint to$\sum b_{ij}x_i ≤ y_jc_j$, add a constraint$y_j$≤ 1, maximise the sum of$y_j$(everything straightforward so far), then add a requirement that$y_j\$ must be an integer. If you fix all mistakes that I may have made :-) then checking that ...