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.

  • $\begingroup$ 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? $\endgroup$ May 9 at 5:04
  • $\begingroup$ Yes, the infeasible set is $Ay \geq b$. And yes, $x_i$ are discrete 0-1 variables. $\endgroup$
    – Artermi
    May 10 at 6:22

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.