# Linearizing the square root of binary summations

My question is similar to this one and almost identical with this. I am so confused due to indexing and could not make sure if I could apply the solution in here to this indexed version as shown below.

The Question:

Let binary variables $$x_{ijk},y_{jik}\in\{0,1\}$$, non-negative continuous variable $$z_j\in\mathbb{R}^+$$, the parameter $$\lambda_k\in\mathbb{R}^+$$, and $$\mathcal{I}$$, $$\mathcal{J}$$, and $$\mathcal{K}$$ be some polynomial size sets. Given these domains, how can I linearize the following set of equality constraints?

$$\displaystyle z_j=\sqrt{\sum_{\substack{i\in \mathcal{I},\\k\in \mathcal{K}}}\lambda_k\left(x_{ijk}+y_{jik}\right)}\qquad j\in\mathcal{J}$$

Solution Attempt:

As in here, can I say: for $$n\in \{0,1,2\}$$, introduce binary variables $$w_{ijkn}$$ to indicate whether $$x_{ijk}+y_{jik}=n$$, and introduce the following constraints?

\begin{align}\sum_{n=0}^2w_{ijkn}&=1 \qquad \forall i\in \mathcal{I},j\in \mathcal{J}, k\in \mathcal{K}\\\sum_{n=0}^2 n\cdot w_{ijkn}&= x_{ijk}+y_{jik}\qquad \forall i\in \mathcal{I},j\in \mathcal{J}, k\in \mathcal{K}\\z_j&= \sum_{\substack{i\in \mathcal{I},\\k\in \mathcal{K}}}\sqrt{\lambda_k}\sum_{n=0}^2 \sqrt{n}\cdot w_{ijkn} \qquad \forall j\in \mathcal{J}\end{align}

• I feel like my attempt is not correct because the binary summation inside the square root (excluding $\lambda_k$) is not in the domain of $\{0,1,2\}$. Am I right? If yes, any alternative solution suggestions? Feb 19 '20 at 17:38
• You cannot interchange the $\sqrt{}$ and $\sum$ like that. Where do $x$, $y$, and $z$ appear elsewhere in the model? Feb 19 '20 at 18:17
• I agree! $z_j$ appears in the objective function (minimize) with a constant associated coefficient and $x_{ijk}$ and $y_{jik}$ appears everywhere as they are some routing variables for a given $k$. Can we extend the domain of $n$ based on the possible highest summation? Feb 19 '20 at 18:20
• If the objective coefficient of $z_j$ is nonnegative, you can relax your equality to $z_j \ge$ and then apply one of the transformations in the first link. Feb 19 '20 at 18:22
• Yes, it is nonnegative, but, sorry I couldn't get what you mean. (I understand the relaxation but cannot figure out how to form the constraints exactly.) Feb 19 '20 at 18:23

Because your objective is minimization and $$z_j$$ has a nonnegative objective coefficient, you can relax your equality constraint to $$\displaystyle z_j \ge \sqrt{\sum_{\substack{i\in \mathcal{I},\\k\in \mathcal{K}}}\lambda_k\left(x_{ijk}+y_{jik}\right)}\qquad j\in\mathcal{J}$$ and this constraint will naturally be satisfied with equality for an optimal solution.

Now apply one of the transformations here.

• First, any reason why we wouldn't apply your approach? Would it be more computationally expensive if we considered extending the range of $n$ compared to the McCormick Envelopes method shared in the other question? Second, would it be okay to use a bigM for $M_j$ in the McCormick method? Feb 19 '20 at 18:43
• My approach depends on $\lambda_k$ being constant, not dependent on $k$. Yes, the $M_j$ is a big-M constant. Feb 19 '20 at 18:52
• I know this is probably too much to ask but just to make sure I implement it correctly, can you please see my comment to Alexandre? I believe, there is redundancy in the constraints in that answer, most likely because the OP defined $\theta_j\in\mathbb{R}$ while it is implied that $\theta_j\in\mathbb{R}^+$. Feb 20 '20 at 5:16
• Yes, you can strengthen his formulation when $0\le \theta_j \le M_j$. Repeat his derivation, but replace $\theta_j+M_j$ with $\theta_j$. Feb 20 '20 at 5:56
• Hey Rob, I just ended up confronting a similar problem, again. Now, I only have $x_{ijk}$ in the square root as a variable (multiplied by the parameter), where $x_{ijk}\in \mathbb{R}^+$. Does the McCormick envelope still work? I do not see a reason not to, but double-checking. Thanks in advance! Jun 27 '20 at 13:25