New answers tagged linear-programming
2
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 ...
Top 50 recent answers are included
