On the hardness of satisfying K number of linear constraints

Question

Background: Normally in linear programing we have some objective function $$\text{maximize}\sum_{i = 1}^n a_i x_i $$ $$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m$$ where $a_i, b_{ji}, c_j$ are all constants given in the problem statement and each $x_i$ is an optimization variable which we may choose the value of. Note that the above problem may not have a feasible solution if all of the linear constraints cannot be satisfied at the same time. Determining if the constraints are satisfiable and optimizing the objective function can both be done in polynomial time.

Problem Statement: Consider a slightly modified version of the above problem where we don't care about the optimization function and are just given the set of constraints

$$\sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m $$ We are interested in answering the question "can at least $k$ of these constraints can be satisfied?".

This feels NP-Hard as it it seems to amount to a combinatorial selection problem in the sense that we are now selecting a specific set of $k$ items out of $n$ possible items, and there could only be one such set of $k$ items that works.

Question: Is this problem NP-hard, what if we impose $0\leq x_i \leq 1$ for all $i$? If so, what problem could be used to construct a good reduction?

Answer 1

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:

1. 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,\ldots$ instead) and $m$ identical constraints: $x_i\ge 1$.
2. For each clause, say $x_i\vee x_j$, add a constraint $x_i+x_j\ge 1$. If a negative literal is involved, for example, $x_i\vee\neg x_j$, then the constraint becomes $x_i+(1-x_j)\ge 1$.

Now we can conclude that there exist $nm+k$ constraints that can be simultaneously satisfied if and only if there exist $k$ clauses that can be simultaneously satisfied in the MAX-2-SAT instance.

Answer 2

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 the optimal solution has a value ≥ k should be exactly what you want, with the advantage that you get the maximum number of restrictions that could be fulfilled.

It's now a mixed integer programming problem, and therefore probably NP-complete, but there are algorithms that work probably better than you starting from scratch.

For example, you may get an initial solution ignoring the "integer" requirement with a sum < k which immediately shows you there is no solution. And an ILP algorithm will probably have some heuristics which y_i can most likely to 1.