6

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}

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
tcokyasar
  • 1,249
  • 5
  • 12
  • 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? – tcokyasar 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? – RobPratt 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? – tcokyasar 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. – RobPratt 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.) – tcokyasar Feb 19 '20 at 18:23

1 Answers1

6

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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? – tcokyasar Feb 19 '20 at 18:43
  • 1
    My approach depends on $\lambda_k$ being constant, not dependent on $k$. Yes, the $M_j$ is a big-M constant. – RobPratt 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}^+$. – tcokyasar Feb 20 '20 at 05:16
  • 1
    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$. – RobPratt Feb 20 '20 at 05: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! – tcokyasar Jun 27 '20 at 13:25
  • Please post a new question for this. – RobPratt Jun 27 '20 at 13:52
  • Posted a similar question here: https://or.stackexchange.com/questions/4461/linearizing-a-constraint-with-square-root-of-a-variable If you may take a look at it, I would appreciate, Rob! – tcokyasar Jun 30 '20 at 15:21