2
$\begingroup$

I have a binary variable $\bf x$ of length 4000. Let ${\bf x}=[x_1,x_2,\cdots, x_{4000}]$.

Let's say we have ${\bf y}=[y_1,y_2,y_3,y_4]$, where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ y_2&=x_2+x_{6}+x_{10}+\cdots+x_{3998} \\ y_3&=x_3+x_{7}+x_{11}+\cdots+x_{3999} \\ y_4&=x_4+x_{8}+x_{12}+\cdots+x_{4000} \end{align}

Now, the constraint I have is: the number of nonzero elements in ${\bf y}$ is $\le 2$

In other words, the $l_0$ norm of vector ${\bf y}$ is $\le 2$

How to model this constraint with and without (if possible) introducing new variables?

With new variables $z_i$

$$y_i \leq M \cdot z_i \quad \text{for } i = 1, 2, 3, 4$$

$$\sum_{i=1}^{4} z_i \leq 2$$

Is it correct? If yes, what would be a good value for $M$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, this is correct and is the standard approach. You want $M$ to be a small upper bound on the left hand side when $z_i=1$, so take $M$ to be the number of $x$ variables on the right hand side of the equality constraint for $y_i$. In your example, that would be $M=1000$.

If $y$ does not appear anywhere else in your model, you can eliminate it by substitution, yielding constraints of the form $\sum_j x_j \le M z_i$, which you can optionally strengthen by disaggregating to $x_j \le z_i$. The resulting formulation is essentially the same as in https://or.stackexchange.com/a/11785/500

$\endgroup$

Your Answer

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

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