How to model this constraint linearly in binary integer linear programming?

Question

I have a directed acyclic graph, and two binary decision variables:

• $a_{ij}$, which is equal to one when the corresponding edge between the nodes $i$ and $j$ of the graph is selected, and zero otherwise.
• $a_{i}$, which is equal to one when the corresponding node $i$ of the graph is selected, and zero otherwise.

I want to express the following constraint: if the edge between the nodes $i$ and $j$ is selected, then both of the nodes, $i$ and $j$, are selected as well. I.e.:

• if $a_{ij}=1$, then $a_{i}=1$ and $a_{j}=1$
• else if $a_{ij}=0$, then $a_{i}=0$ and/or $a_{j}=0$.

I could easily express this with the following equation: $a_{ij} = a_{i} * a_{j}$

However, since I have to model the particular problem as a binary integer linear programming model, all of the constraints have to be linear.

Is there a way to express the particular constraint linearly?

Please also note, that $n_i$ represents the number of immediate child nodes of node $i$ in the graph (in case this could facilitate the linear formulation of the particular constraint).

Answer 1

3 constraints you'd need
$ a_{ij} \le a_i$
$a_{ij} \le a_j$
$a_i + a_j \le a_{ij}+1$

Answer 2

Since the graph is directed, let's assume $a_{ij}$ means an outgoing edge from $i$ into $j$. Then you can add constraints of the form

$$n_i a_i \geq \sum_j a_{ij}$$

In words, if any $a_{ij}$ is active then $a_i$ must be active. If you also have access to the number of incoming edges at each node, say $m_i$, you can add similar constraints of the form

$$m_j a_j \geq \sum_i a_{ij}$$

EDIT: In fact, you don't need to use $n_i$ or $m_j$, you can replace them both with $M$ (some number larger than the total number of edges in the graph)

Answer 3

Of the $8$ possible points of $\{0,1\}^3$, you want to allow only $(a_i, a_j, a_{ij}) = (0,0,0), (1,0,0), (0,1,0), (1,1,1)$. Eliminating each of the non-allowed points can be done with a "cut" constraint: think of cutting the cube $[0,1]^3$ by a plane that cuts off one of the vertices, leaving the others. Thus to eliminate $(1,1,0)$ you can use the constraint $a_1 + a_j - a_{ij} \le 1$. You can eliminate both $(0,0,1)$ and $(0,1,1)$ (since they are adjacent) by one constraint $a_i - a_{ij} \ge 0$. And similarly both $(0,0,1)$ and $(1,0,1)$ by $a_j - a_{ij} \ge 0$.