# 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. 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. 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? 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. Dec 31 '19 at 13:06