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$
5
  • $\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$
    – tcokyasar
    Feb 19 '20 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 '20 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$
    – tcokyasar
    Feb 19 '20 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 '20 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$
    – tcokyasar
    Feb 19 '20 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.

$\endgroup$
7
  • $\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$
    – tcokyasar
    Feb 19 '20 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 '20 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$
    – tcokyasar
    Feb 20 '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 '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$
    – tcokyasar
    Jun 27 '20 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.