How to linearize the product of a non-binary discrete variable and a continuous variable?

Question

Given a set $J$, I have the following constraint:

$w_j = y_j u \quad \forall j \in J$

where $y_j \in \mathbb{N}$ and $u \in \mathbb{R}⁺_0$. I would like to make this constraint linear.

Note: I am familiar with the linearization of this similar constraint when $y_j \in \{0, 1\} \quad \forall j \in J$ which could be

$w_j \leq u, \quad \forall j \in J$

$w_j \leq My_j, \quad \forall j \in J$

$w_j \geq u - M(1 - y_j), \quad \forall j \in J$.

However in my case, $y_j$ is not a binary variable but a integer non-negative variable.

Just so it is clear, $\mathbb{N}$ is the set of all integers including $0$ and $\mathbb{R}⁺_0$ is the set of all real non-negative numbers.

Answer 1

If you can bound $y_j$ by some (not too large) positive integer $Y$, so that $y_j\in \{0,1,\dots,Y\}$, you can introduce binary variables $z_0, z_1,\dots,z_Y$ and add the following constraints:$$\sum_{i=0}^Y z_i=1$$ $$y_j=\sum_{i=0}^Y i\cdot z_i$$and $$w_j=\sum_{i=0}^Y i\cdot z_i \cdot u.$$Now linearize each of the products $z_i\cdot u$.