Binary optimization on a direct-acyclic-graph(DAG)

78 Views Asked by At

Given a DAG $G$, each edge of the DAG $e \in E(G)$ relates to a attribute $w_e \in \{-1, 1\}$

Try to find the optimized attribute setting $[w_e]$ s.t. the cost function

$$ \sum_{e\in E(G)} w_e $$

is maximized, in another word, set as more 1 as possible. The constraints come from the DAG structure. For each path $e_s,e_i,e_j,...,e_t$ from the source node $s$ to the sink node $t$, the production of all edge attributes:

$$ w_{es} \cdot w_{ei} \cdot w_{ej} ... \cdot w_{et} $$

must stay the same value.

In summary, the model is:

For a DAG $G$ with edges sets:

$$ Maximize \sum_{e\in E(G)} w_e\\ s.t.\; w_e\in\{-1,1\}\\ w_{es} \cdot w_{ei} ... \cdot w_{et} = 1,\;e_s,e_i,...,e_t\;\text{is a path}\\ w_{es} \cdot w_{ej} ... \cdot w_{et} = -1,\;e_s,e_j,...,e_t\;\text{is a path}\\ w_{es} \cdot w_{ek} ... \cdot w_{et} = 1,\;e_s,e_k,...,e_t\;\text{is a path}\\ w_{es} \cdot w_{el} ... \cdot w_{et} = -1,\;e_s,e_l,...,e_t\;\text{is a path}\\ ... $$

For an example, consider a DAG looks like:

     --> A --
s - |        | -> t
     --> B --

This DAG has 4 edges $$ e_1 : s \rightarrow A\\ e_2 : s \rightarrow B\\ e_3 : A \rightarrow t\\ e_4 : B \rightarrow t\\ $$ there are two paths from s to t, let's say they have constraints like: $$ e_1\cdot e_3 = 1\\ e_2\cdot e_4 = -1 $$

then, we need find a config $[e_1, e_2, e_3, e_4] \in \{1,-1\}^4$ that has maximum summation. Here the answer is $[1, 1, -1, 1]$

1

There are 1 best solutions below

0
On

Suppose we set $w_e = (-1)^{x_e}$. Then the product of weights along a path is the sum, modulo 2, of the $x$'s along that path, so each constraint is a linear equation over $\mathbb{Z}/2\mathbb{Z}$. Your goal is to minimize the Hamming weight of $x$, subject to these linear equations.

So, your problem is equivalent to $$\min_x \text{wt}(x) \quad \text{such that } Mx=0,$$ where $x \in (\mathbb{Z}/2\mathbb{Z})^n$, $M$ is some $m \times n$ matrix with entries in $\mathbb{Z}/2\mathbb{Z}$ representing the $m$ linear equations associated with the $m$ paths, and $\text{wt}(x)$ denotes the Hamming weight of $x$.

I believe this is closely related to the problem of finding a minimum-weight codeword in a linear code (if we think of $M$ as a parity-check matrix for a linear code). That problem is NP-hard, but there exist subexponential time algorithms for it. You could try applying one of them to this problem. See, e.g., https://cs.stackexchange.com/q/119999/755, https://cs.stackexchange.com/q/52534/755.

However, this doesn't make use of the structure afforded by the DAG. Perhaps there are better algorithms that make use of the DAG structure.