6
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user8028576 Feb 19 at 17:38
  • $\begingroup$ You cannot interchange the $\sqrt{}$ and $\sum$ like that. Where do $x$, $y$, and $z$ appear elsewhere in the model? $\endgroup$ – RobPratt Feb 19 at 18:17
  • $\begingroup$ 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? $\endgroup$ – user8028576 Feb 19 at 18:20
  • $\begingroup$ 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. $\endgroup$ – RobPratt Feb 19 at 18:22
  • $\begingroup$ 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.) $\endgroup$ – user8028576 Feb 19 at 18:23
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user8028576 Feb 19 at 18:43
  • 1
    $\begingroup$ My approach depends on $\lambda_k$ being constant, not dependent on $k$. Yes, the $M_j$ is a big-M constant. $\endgroup$ – RobPratt Feb 19 at 18:52
  • $\begingroup$ 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}^+$. $\endgroup$ – user8028576 Feb 20 at 5:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – RobPratt Feb 20 at 5:56
  • $\begingroup$ 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! $\endgroup$ – user8028576 Jun 27 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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