10

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Henry
  • 542
  • 2
  • 7

1 Answers1

10

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}

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Ggouvine
  • 1,877
  • 7
  • 13
  • 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 02:36
  • Indeed, continuous LPs are convex, and their feasible region is a convex polytope. What type of constraint are you thinking about? – Ggouvine Dec 31 '19 at 09:06
  • 1
    @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