1
$\begingroup$

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".

Improve this question
$\endgroup$
5
  • $\begingroup$ Are the variables $x_{ij}$ are real-valued, i.e. $x_{ij} \in \mathbb{R}_{+}$? $\endgroup$
    – joni
    Sep 27 at 8:17
  • $\begingroup$ Yes, $x_{ij}$ and $z_{ij}$ are real valued, only $y_j$ is binary. $\endgroup$
    – Christian
    Sep 27 at 9:28
  • $\begingroup$ @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$? $\endgroup$
    – A.Omidi
    Sep 27 at 11:20
  • $\begingroup$ 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". $\endgroup$
    – Christian
    Sep 27 at 15:57
  • $\begingroup$ @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. $\endgroup$
    – A.Omidi
    Sep 27 at 18:26

2 Answers 2

Reset to default
3
$\begingroup$

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.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Instead of returning a (linear) expression as the lookup's result, using a result variable with restrictions is a nice idea. Compared it with my model and it got better. Initially I was afraid it might not be as sharp as my formulation, but my tests do not indicate this. $\endgroup$
    – Christian
    Sep 27 at 20:25
  • 1
    $\begingroup$ 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}$). $\endgroup$
    – Christian
    Oct 4 at 5:46
3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.