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

Addison Trujillo 2022-07-08 Answered
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

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it

## Answers (1)

Karla Hull
Answered 2022-07-09 Author has 20 answers
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$.
###### Not exactly what you’re looking for?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it