1
$\begingroup$

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).

$\endgroup$
1

3 Answers 3

Reset to default
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.