0
$\begingroup$

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.

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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