# LP sum of variables that are above a threshold

I am trying to code a constraint of the form:

$$\sum_i y_i < K\,\text{where}\,\begin{cases}y_i = x_i\quad\text{if}\,x_i>k_i\\0\quad\text{otherwise}.\end{cases}$$

In other words, I want to constrain the sum of $$x_i$$ (only) for those $$x_i>k_i$$, where $$k_i$$ are fixed and all positive, and $$x_i$$ are free and all positive.

I think this is a straightforward MIP, but wondering if it can be coded in LP. I can't show it's not convex.

Any suggestions appreciated.

The constraint is not convex, and cannot be formulated as a pure LP. You will have to resort to a MIP model.

## Why it is not convex

As an example, consider the case where : $$K = 2$$, $$k_1 = 1$$, $$k_2 = 1$$.

The solution where $$x_1 = 1.8$$ and $$x_2 = 0.8$$ gives $$y_1 = 1.8$$ and $$y_2 = 0$$, and is valid. The symmetric solution with $$x_1 = 0.8$$ and $$x_2 = 1.8$$ is valid as well.

But their average is $$x_1 = 1.3$$ and $$x_2 = 1.3$$. This gives $$y_1 = 1.3$$ and $$y_2 = 1.3$$, where the constraint is violated. Hence the feasible set has a hole: it is not convex.

## A possible MIP formulation

It is possible to formulate this constraint as a MIP by adding boolean variables $$b$$. For example, using the big-M method (with $$M$$ chosen to be bigger than the range of $$x$$): \begin{align}y &\geq x - Mb\\b &\leq (k-x)/M + 1\end{align}

• thanks Gabriel, that helped me out. – Henry Dec 30 '19 at 19:00
• Don't you mean, "The constraint is not linear,..."? As stated it implies that constraints need only be convex to be used in an LP, which of course is not true. – Cary Swoveland Dec 31 '19 at 2:36
• Indeed, continuous LPs are convex, and their feasible region is a convex polytope. What type of constraint are you thinking about? – Gabriel Gouvine Dec 31 '19 at 9:06
• @Cary Swoveland Constraint is convex does not imply it can be represented by LP. But, as is the point of thsi answer to which I am commenting, non-convex implies it can not be represented by LP. – Mark L. Stone Dec 31 '19 at 13:06