I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger than $K$ and not all constraints have to be satisfied. The question is the following:

Find the parameters $\alpha_1,...,\alpha_K$ such that out of $N$ constraints maximum number of them ($M\leq N$) are satisfied.

Is this problem NP-Hard? What is the most effective way of solving such problems for large $N$ and $K$?

  • $\begingroup$ If you phrase it as $\min_{x,s} \{ ||s||_0 : Ax+s=b \}$, it is similar to the problem studied in this paper. $\endgroup$
    – LinAlg
    Oct 24 '18 at 15:50
  • $\begingroup$ @LinAlg that problem is a completey different one, as long as I understood. In my problem the parameter vector is real valued and there are no constraints for the choice of parameters. The only point is the total number of constraints that are satisfied. Out of all parameter vectors I need the one which will increase this number. A specific example is here: mathematica.stackexchange.com/questions/184194/… $\endgroup$ Oct 24 '18 at 16:01
  • $\begingroup$ My phrasing of your problem seems correct to me. If $s_i=0$, constraint $i$ is satisfied. The objective maximizes the number of elements in $s$ that are $0$. $\endgroup$
    – LinAlg
    Oct 24 '18 at 16:40
  • $\begingroup$ @LinAlg I roughly understood what you are saying. Two points: $1.$ I have inequality constraints. $2.$ I checked that paper and there is $L_2$ norm and sparse solution in terms of the parameters. I have neither of these things.. $\endgroup$ Oct 24 '18 at 17:01
  • $\begingroup$ If there is no objective function, then there is nothing to optimize. If you consider a matrix form of the constraints, then maybe you want to remove redundant rows from the matrix (the ones that form a linear combination of other rows). $\endgroup$
    – NoChance
    Oct 24 '18 at 21:45

This can be shown to be NP-hard by reduction from 0-1 ILP feasibility. Take any 0-1 integer linear programming feasibility problem


$x \in \left\{ 0, 1 \right\}^{n}$

Where $A$ has $m$ rows and $n$ columns.

Relax the integrality constraint and add $2n$ additional constraints

$x_{i}=0, i=1, 2, \ldots, n$

$x_{i}=1, i=1, 2, \ldots, n$

Now, the 0-1 ILP is feasible if and only if you can satisfy $m+n$ constraints in the real system of equations.

  • $\begingroup$ I’ve used equality constraints, but any equality constraint can be replaced by a pair of inequalities. $\endgroup$ Oct 25 '18 at 2:14
  • $\begingroup$ Which algorithm may be the most suitable to solve this problem? I have a person by person approach in mind but I am sure there should be more effective ones.. $\endgroup$ Oct 25 '18 at 7:03
  • $\begingroup$ You can formulate your problem as a mixed integer linear programming problem with one 0-1 variable for each of the original inequality constraints using the "Big-M technique" for turning the constraint on or off by whether the variable is 0 or 1. Whether it will be practical to solve the resulting MILP will depend a lot on the size of the problem. $\endgroup$ Oct 25 '18 at 16:31
  • $\begingroup$ Okey. As long as I understood you talking about the same method which @LinAlg described in his comment. The objective function would then be the $L_0$ norm of the related vector of zeros and ones. $\endgroup$ Oct 25 '18 at 16:37
  • $\begingroup$ $x_i=0$ and $x_i=1$ for the same indexes? That sounds strange to me. $\endgroup$ Oct 26 '18 at 12:18

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.