1
$\begingroup$

In an undirected graph, I'm trying to model a constraint that forcing the optimizer to set an edge $(u,v)$ between two nodes to only exist (= $1$) if the two nodes have been selected to be $1$. The three decision variables can be something like that:

$z(u,v) \geq y_u x_v$ , $\quad x,y,z \in \{0,1\}$

and to linearize the multiplication here, I'm introducing a new decision variable $r=xy$ and these constraints has been added:

$z(u,v) \geq r(u,v)$

$r(u,v) \leq y_u$

$r(u,v) \leq x_v$

$r(u,v) \geq y_u + x_v -1$

Keeping in mind that this is for undirected graph where $r(u,v)$ is different from $r(v,u)$. How can I model this in Python using Pulp and NetworkX ?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Do you instead mean directed graph? $\endgroup$ – RobPratt Nov 26 '20 at 0:43
  • $\begingroup$ No, I actually meant it (undirected graph), that is why I'm confused about modeling that constraint $\endgroup$ – Amedeo Nov 26 '20 at 1:15
  • 2
    $\begingroup$ Hmm, $r(u,v)$ is different from $r(v,u)$ usually means directed. Is it maybe bipartite? If not, why do you have both $x$ and $y$ variables? $\endgroup$ – RobPratt Nov 26 '20 at 1:18
  • $\begingroup$ Thank you for your comment, x and y at two different levels, I forgot to mention that I'm solving a hierarchical problem $\endgroup$ – Amedeo Nov 26 '20 at 1:27
  • 1
    $\begingroup$ Do you want to model $z(1,2) = x_1\cdot y_2$ and $z(2,1) = x_2\cdot y_1$? Or do you want to model $x_1\land y_2 \lor x_2\land y_1 \Leftrightarrow z(1,2) \lor z(2,1)$? Or do you just have either the variable $z(1,2)$ or the variable $z(2,1)$, as it represents a directed edge and you want this one variable to be active when one of the $x_1y_2, x_2,y_1$ is $1$? $\endgroup$ – SimonT Dec 1 '20 at 18:06

Your Answer

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

Browse other questions tagged or ask your own question.