# 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.

If there is any research about this, please let me know.

• 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

## 1 Answer

For debugging purposes, it's helpful to identify small subsets of infeasible constraints in an LP formulation- an Irreducible Infeasible Subset (IIS) is a subset of the constraints that are infeasible and such that removing any constraint from the IIS results in a feasible set of constraints. This is doable in polynomial time and fairly fast in practice, but it is not the same as finding a maximum feasible subsystem.

This problem of finding a maximum subset of feasible constraints in an infeasible LP is NP-Hard. See

Amaldi, Edoardo, Marc E. Pfetsch, and Leslie E. Trotter Jr. "On the maximum feasible subsystem problem, IISs and IIS-hypergraphs." Mathematical Programming 95, no. 3 (2003): 533-554.

• You save my day. Thank you very much! May 9 at 13:33
• @Artermi, if that answer your question you could accept the answer. May 9 at 15:53
• I found a similar problem. Do you know any polynomial algorithm for the case of 2D? Here May 11 at 17:14