patternMinor
On the hardness of satisfying K number of linear constraints
Viewed 0 times
linearnumbertheconstraintshardnesssatisfying
Problem
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?
$$\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?
Solution
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:
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.
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,\ldots$ instead) and $m$ identical constraints: $x_i\ge 1$.
- 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.
Context
StackExchange Computer Science Q#115216, answer score: 3
Revisions (0)
No revisions yet.