LP sum of variables that are above a threshold

Question

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.

Answer 1

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}