# Modeling the multiplication of two binary decision variables in undirected graph in python

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 ?

• Do you instead mean directed graph? – RobPratt Nov 26 '20 at 0:43
• No, I actually meant it (undirected graph), that is why I'm confused about modeling that constraint – Amedeo Nov 26 '20 at 1:15
• 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? – RobPratt Nov 26 '20 at 1:18
• Thank you for your comment, x and y at two different levels, I forgot to mention that I'm solving a hierarchical problem – Amedeo Nov 26 '20 at 1:27
• 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$? – SimonT Dec 1 '20 at 18:06