10
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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}

| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks Gabriel, that helped me out. $\endgroup$ – Henry Dec 30 '19 at 19:00
  • $\begingroup$ 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. $\endgroup$ – Cary Swoveland Dec 31 '19 at 2:36
  • $\begingroup$ Indeed, continuous LPs are convex, and their feasible region is a convex polytope. What type of constraint are you thinking about? $\endgroup$ – Gabriel Gouvine Dec 31 '19 at 9:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Mark L. Stone Dec 31 '19 at 13:06

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.