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$

1 Answer 1

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}

$\endgroup$
4
  • $\begingroup$ thanks Gabriel, that helped me out. $\endgroup$
    – Henry
    Dec 30, 2019 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$ Dec 31, 2019 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$
    – Ggouvine
    Dec 31, 2019 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$ Dec 31, 2019 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.