6

We have two variables $x\geq0$ and $y\in\mathbb{Z}^{0+}$.

We have this constraint in our model $$x = \sum_{i = 0}c_i \mathbb{1}_{\{y=i\}}$$ where $c_i$ is a parameter and $\mathbb{1}_{A} = 1$ if $A$ is true and zero otherwise.

Is this constraint linear?

RobPratt
  • 32,006
  • 1
  • 44
  • 84

2 Answers2

6

Indicator constraints are not linear constraints, but here’s a linearization with binary variables $z_i$: \begin{align} \sum_i z_i &= 1 \\ \sum_i i z_i &= y \\ \sum_i c_i z_i &= x \end{align}

RobPratt
  • 32,006
  • 1
  • 44
  • 84
5

Since the constraint includes binaries, it does not define a convex set, and is therefore not linear.

For example, if $x=c_11_{A}$, $x$ can take values either $0$ or $c_1$. But $\frac{0+c_1}{2} \notin \{0,c_1 \}$, so the constraint does not define a convex set.

Note however that the convex hull of the constraint is linear, which is why such constraints are considered linear in the context of Mixed Linear Programming (MIP). So as Erwin points out in the comment section, a MIP is linear/convex if its relaxation is linear/convex.

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • Thank you for the answer. If we reformulated this constraint as $x=\sum_{i}c_i z_i$ where $z_i=1$ if $y=i$, and zero otherwise, it would be a linear constraint. Is that correct? If so, why? Is it because variable $z_i$ creates a convex set? –  Jan 15 '23 at 12:45
  • 1
    no, it would remain non linear, it is just a different notation. Keep in mind that roughly speaking using binaries $\implies$ loosing linearity. – Kuifje Jan 15 '23 at 13:01
  • 7
    A commonly used and more useful definition is: a MIP is linear if its relaxation is linear. I.e. convex MINLPs do exist. (If integer variables make things non-convex, all MIPs are non-convex.) – Erwin Kalvelagen Jan 15 '23 at 13:05
  • Which means solution is for an $i$ is either $0$ or $c_i$. If you draw a line, it's linear. – Sutanu Majumdar Jan 15 '23 at 13:07
  • 1
    I also should have added: a MIP/MINLP is convex if its relaxation is convex. – Erwin Kalvelagen Jan 15 '23 at 13:15