# Suppose there is a set of n linear constraints <mo fence="false" stretchy="false">{ <msubsup>

Suppose there is a set of n linear constraints $\left\{{a}_{i}^{T}x+{b}_{i}\le 0{\right\}}_{i=1}^{n}$ with ${a}_{i}\in {\mathbb{R}}^{d}$, ${b}_{i}\in \mathbb{R}$, $x\in {\mathbb{R}}^{d}$. How can I find ${x}^{\ast }$ that maximizes $|\left\{i\in \left[n\right]\mid {a}_{i}^{T}{x}^{\ast }+{b}_{i}\le 0\right\}|$? Is this problem solvable or can be approximated within polynomial time?
Some reference materials would also be nice. Thanks!
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Karla Hull
The maximum cardinality feasible subsystem problem is NP-hard
You might also search for the equivalent minimum cardinality IIS set cover problem.
You can solve the problem via mixed integer linear programming as follows. Let binary decision variable indicate whether constraint i is satisfied. The problem is to maximize $\sum _{i}{z}_{i}$ subject to linear (big-M) constraints

Here, Mi is a (small) constant upper bound on the LHS when ${z}_{i}=0$.