# Matrix lookup modelling variants

As part of a bigger model I have a matrix of variables $$x_{ij} \geq 0$$ and a "selector" set of variables $$y_j \in \{0,1\}, \sum_j y_j = 1$$. From $$x_{ij}$$ I'd like to get the variables of column $$j$$, where $$y_j = 1$$, so it's kind of a matrix lookup: $$x_{.j}$$ with $$j = \sum_k k \space y_k$$

I'm interested in efficient modelling variants to achieve this. Probably there is not the best variant, as it largely depends on the other parts of the model, so proposals are welcomed.

My approach:

$$c_i$$: columns of $$x_{ij}$$ where $$y_j = 1$$ $$\forall i: c_i = \sum_j x_{ij} \space y_j$$ As $$x_{ij} \space y_j$$ is not linear, I introduce substitute $$z_{ij} \geq 0$$ and $$M$$ as upper bound on $$x_{ij}$$ with

$$0 \leq z_{ij} \leq x_{ij} \\ x_{ij} - M (1 - y_j) \leq z_{ij} \leq M \space y_j \\$$ So $$c_i = \sum_j z_{ij}$$ with the constraints from above. It works, but I wonder if it can be improved. What I don't like (beside Big-M) is that I have to introduce additional variables in the size of $$x_{ij}$$ plus 3 additional constraints per variable - and in the end I only need $$c_i$$. The $$z_{ij}$$ are just "intermediates".

• Are the variables $x_{ij}$ are real-valued, i.e. $x_{ij} \in \mathbb{R}_{+}$?
– joni
Sep 27 at 8:17
• Yes, $x_{ij}$ and $z_{ij}$ are real valued, only $y_j$ is binary. Sep 27 at 9:28
• @Christian, what exactly you mean by the multiplication of these two variables? Is it for activating the variable $x_{i,j}$ when each of the variable $y_{j}$ is being one? If so, do you try to use $\sum_{i} x_{i,j} \leq M y_{j} \quad \forall j \in J$? Sep 27 at 11:20
• Yes, the multiplication is for activating the "selected" column of $x_{ij}$. $\sum_i x_{ij} \leq M y_j$ is not a valid constraint, as it would force $x_{ij}$ to $0$ for unselected columns. But $\sum_i z_{ij} \leq |I| M y_j$ would be a valid inequality, but I guess my $z_{ij} \leq M y_j$ is "sharper". Sep 27 at 15:57
• @Christian, I am not sure to understand what you described. if the model does not allow to have unselected $y_{j}$, you should not worry about the mentioned constraint. Sep 27 at 18:26

You do not really need the $$z$$ variables. You can just add the constraints $$x_{ij} - M(1-y_j) \le c_i \le x_{ij} + M(1-y_j)\quad \forall j.$$
• Just would like to share some feedback: I have determined the lower and upper bounds of $c_i$ as $c^{lower}_i = \min_j x^{lower}_{ij}$ and $c^{upper}_i = \max_j x^{upper}_{ij}$, the left hand $M = x^{upper}_{ij} - c^{lower}_i$ and right hand $M = c^{upper}_i - x^{lower}_{ij}$. Additionally I added $\sum_j x^{lower}_{ij} y_j \leq c_i \leq \sum_j x^{upper}_{ij} y_j$ which helps improving the relaxation in case of $x_{ij}$ with tight ranges (or constants, when $x^{lower}_{ij} = x^{upper}_{ij}$). Oct 4 at 5:46
If your modeling API supports indicator constraints, you can impose $$y_j =1 \implies c_i=x_{ij}.$$ @prubin’s answer provides the corresponding big-M formulation of this constraint.