# Maximum Constraints Satisfaction of Linear Programming

The question I need to solve is to maximize the satisfied constraints in linear programming.

To be more specific, Suppose I have an infeasible LP problem, my goal now, is to find the maximum number of the constraints which I can satisfy.

Put in a formulation way:

$$\max \sum_{i=1}^K x_i,\\ \text{s.t.}\ \mathrm{diag}(x)(A-b) y \geq 0$$

And I have $$A \in \mathbb{R}^{k\times m}$$ and $$y \in \mathbb{R}^m$$

If $$y$$ is in a finite domain, it would be maximum satisfiability (MAX-SAT), which is proved to be an NP-hard problem. However, for a linear program problem, I cannot find if it's NP-hard or polynomial-time solvable.

• Your notation is unclear (or perhaps simply wrong) Is the original set of constraints (of which you want to satisfy as many as possible) $Ay \geq b$? Are the $x_{i}$ variables discrete 0-1 variables? May 9 at 5:04
• Yes, the infeasible set is $Ay \geq b$. And yes, $x_i$ are discrete 0-1 variables. May 10 at 6:22