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}

Improve this question
$\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
    Commented Feb 19, 2020 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
    Commented Feb 19, 2020 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
    Commented Feb 19, 2020 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
    Commented Feb 19, 2020 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
    Commented Feb 19, 2020 at 18:23

1 Answer 1

Reset to default
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$
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
    Commented Feb 19, 2020 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
    Commented Feb 19, 2020 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
    Commented Feb 20, 2020 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
    Commented Feb 20, 2020 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
    Commented Jun 27, 2020 at 13:25

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.