2
$\begingroup$

I'm working on an optimization problem using Docplex and wonder if it's possible to incorporate a logical expression into the objective function of my model.

Specifically, I have three variables x, y, and z.

$$x_{ijk} \quad : \quad binary \quad variable$$ $$y_{ik} \quad and \quad z_{ik} \quad : \quad are \quad continuous \quad variables $$ And I want to model this objective function:

\begin{aligned} \min w_{1} \sum_{k \in K} \sum_{(i, j) \in V} c_{ijk}*x_{ijk} + w_{2}\sum_{k \in K} \sum_{(i, j) \in V} [(y_{jk} - y_{ik})*x_{ijk} \quad if \quad z_{ik} == 0] \end{aligned}

Is it feasible to include such a logical expression directly within the objective function in CPLEX? If so, how can I go about implementing it effectively?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ So you want to minimize $\sum_k\sum_{i,j} (y_{jk}-y_{ik})x_{ijk}(1-\delta_{ik})$ where $\delta_{ik}\in\{0,1\}$ and $z_{ik} \ge \epsilon \delta_{ik}$ ($z_{ik}=0 \implies \delta_{ik}=0$). This needs to be linearized. $\endgroup$
    – Kuifje
    Aug 5 at 14:29
  • $\begingroup$ What should the objective term be if $z_{ik}\neq 0?$ $\endgroup$
    – prubin ♦
    Aug 5 at 15:23
  • $\begingroup$ I have edited the question, it is just the second term of the objective function. In the model, the variable 'z' takes on discrete values from the set {0, 1, 2, 3}. When the value of 'z' is not equal to 0, the second term evaluates to 0. $\endgroup$
    – Nada.S
    Aug 5 at 16:04

1 Answer 1

Reset to default
3
$\begingroup$

We can use a "big M" approach, assuming that you can find a positive constant $M$ such that $\vert y_{jk}-y_{ik} \vert \le M$ for all $k\in K$ and $(i,j)\in V.$

Introduce new binary variables $u_{ik}$ and continuous variables $v_{ijk}.$ The second objective summand (the mess in brackets) becomes $v_{ijk}.$ Now add the following constraints: $$3u_{ik} + z_{ik} \le 3\, (1)$$ $$u_{ik} + z_{ik} \ge 1 \, (2)$$ $$v_{ijk} \le M u_{ik}\, (3)$$ $$v_{ijk} \ge -M u_{ik}\, (3')$$ $$v_{ijk} \le M x_{ijk}\, (4)$$ $$v_{ijk} \ge -M x_{ijk}\, (4')$$ $$v_{ijk} \le y_{jk} - y_{ik} + M(2 - u_{ik} - x_{ijk}) \, (5)$$ and $$v_{ijk} \ge y_{jk} - y_{ik} - M(2 - u_{ik} - x_{ijk}) \, (5')$$

Constraints (1) and (2) combine to set $u_{ik} =1$ if and only if $z_{ik} = 0.$ Constraints (3) and (3') say that the $(i,j,k)$ objective term is 0 if $u_{ik}=0$ (meaning $z_{ik} \in \lbrace 1,2,3 \rbrace$). Constraints (4) and (4') say that the objective term is 0 if $x_{ijk} =0.$ Finally, constraints (5) and (5') say that if $u_{ik}=1$ (meaning $z_{ik}=0$) and $x_{ijk}=1,$ then the objective term equals $y_{jk}-y_{ik}.$

Addendum: If the solver supports "if-then" (implication) constraints (CPLEX does), then the "big M" constraints can be replaced with implications, as follows. $$u_{ik}=0 \implies v_{ijk}=0$$ $$x_{ijk}=0 \implies v_{ijk}=0$$ $$u_{ik} + x_{ijk} = 2 \implies v_{ijk} = y_{jk}-y_{ik}$$

As a general rule, you are probably better off with the "big M" constraints if you can find a reasonably tight value of $M.$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, the reasoning seems to be correct, Just finding the appropriate value of "M" isn't feasible. I just wondering taking into account that the second term will be calculated just in the case if there is an arc between (i,j) $$x_{ijk} =1 \quad and \quad z_{ik}=0$$ it s necessary to deal with the other cases. $\endgroup$
    – Nada.S
    Aug 7 at 8:33
  • $\begingroup$ I'm not sure what you mean by "necessary to deal with the other cases". $\endgroup$
    – prubin ♦
    Aug 7 at 15:10
  • $\begingroup$ I extended the answer to describe use of implication constraints if you can't find a good value for $M.$ $\endgroup$
    – prubin ♦
    Aug 7 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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