A Multi-Valued Decision Diagram-Based Approach to Constrained Optimal Path Problems over Directed Acyclic Graphs

1 Introduction

Numerous combinatorial optimization problems, particularly those that can be solved using dynamic programming paradigm, can be reduced to optimal path problems over directed acyclic graphs (DAGs). Given a weighted DAG, the optimal path problem aims to find a path from a source vertex to a target vertex on the given DAG such that its length is minimal or maximal. These problems include the 0-1 knapsack problem [Kellerer et al., 2004], the Viterbi path problem [Forney, 1973] and the edit distance problem [Wagner and Fischer, 1974]. In many complex real-world scenarios, we do not only find the optimal path on the DAG but also require the optimal path to satisfy a logical constraint. Unfortunately, these constrained optimal path problems become more challenging than optimal path problems without constraints.

∗Both are corresponding authors.

Some efficient algorithms targeted at specific problems and constraints have been proposed. For example, Yamada et al. [2002] proposed a heuristic method to solve the disjunctively constrained knapsack problem. Oommen [1986] developed an algorithm for the constrained string editing problem. A unified method to these problems is to formalize each problem as an integer linear programming (ILP) instance, which can be solved by state-of-the-art ILP solvers, for example, CPLEX 1 and Gurobi 2 . But the computational time of ILP solvers lacks a theoretical upper bound, making it difficult to estimate the solution time.

BDD-constrained search (BCS) [Nishino et al., 2015] is a unified and efficient approach for the constrained optimization problem, which treats logical constraints as Boolean functions. To maintain logical constraints, this algorithm makes use of binary decision diagram (BDD) [Bryant, 1986], a compact form of Boolean functions. It performs a search on the DAG in a dynamic programming paradigm and employs BDDs to check for equivalent paths to reduce the search space. More importantly, BCS has theoretical upper bounds for computational time and space. BCS solves the constrained optimal path problem over DAGs more efficient than CPLEX. However, since BCS considers the edges as variables and the logical constraint as a Boolean function, it obtains incorrect local constraint w.r.t. a given path in some cases. This leads to extra redundant operations during the search, impacting the efficiency.

To mitigate the above deficiencies of BCS, in this paper, we propose a novel method to the constrained optimization problem, namely MDD-constrained search (MCS). The main idea is to treat logical constraints as multi-valued functions. Each variable of multi-valued functions corresponds to a vertex in a DAG and its domain is the outgoing edges of its corresponding vertex along a special element. We utilize multi-valued decision diagrams (MDDs) [Kam et al., 1998] as the representation of logical constraints. Furthermore, we analyze the time and space complexity of MCS and compare them with the time and space complexity of BCS. Finally, We compare two algorithms BCS and MCS on four datasets with six logical constraints. The experimental results demonstrate MCS shows a substantial improvement over BCS in terms of search time and memory requirements.

1 https://www.ibm.com/products/ilog-cplex-optimization-studio

2 https://www.gurobi.com/

2 Preliminaries

2.1 Directed Acyclic Graphs

Let G = (V, E) represent a directed acyclic graph (DAG), where V is a set of vertices and E is a set of edges. We use |V| and |E| for the number of vertices and edges, respectively. The notation [v1, · · · , v|V|] denotes a sequence of vertices which follow a topological sorted order σv. We use σv(vi) for the position of vi in the topological order σv. The notation vi ≺σv vj means that vertex vi precedes vj in σv. Given an edge e, we use Vs(e) and Vt(e) for the source and target vertex of e, respectively. Given a topological sorted order σv of vertices, we can define a topological order σe : [e1, · · · , e|E|] of edges w.r.t. σv where Vs(ei) ⪯σv Vs(ej) for i < j. A path p is a sequence [ep(1), . . . , ep(|p|)] of edges where Vt(ep(i)) = Vs(ep(i+1)) for 1 ≤ i ≤ |p| - 1. A path [ep(1), . . . , ep(i)] is a prefix of p if i ≤ |p| and [ep(i), . . . , ep(|p|)] is a suffix of p if i ≥ 1. We assume each edge ei has a real-valued weight wi. The length of a path is the sum of weights of each edge along it. Given two vertices s and t, we use Pst for the set of all paths from s to t, and Est for the set of edges where each edge e satisfies that s ⪯σv Vs(e) and Vs(e) ≺σv t.

2.2 Decision Diagrams

Let f(x1, · · · , xn) be a multi-valued function where each variable xi has a finite domain Di and f returns {⊤, ⊥}. We use |Di| for the size of Di. Multi-valued decision diagrams (MDDs) [Kam et al., 1998] are a directed acyclic graph that compactly represents a multi-valued function. To avoid confusion, we use the terminologies node and arc for decision diagrams and vertex and edge for general DAG. An MDD consists of two types of nodes: terminal nodes and internal nodes. A terminal node is labeled by ⊤ or ⊥, signifying the Boolean value of a multi-valued function. An internal node n is labeled by a variable var(n) and has |Di| outgoing arcs where var(n) = xi. We use childv(n) for the outing arc of n where var(n) = xi and v ∈ Di. It means that the variable xi is assigned to the element v. We also use childv(n) to denote the successor node of n to which the arc childv(n) points. We say nodes labeled by the same variable are at the same level. For simplicity, we sometimes use a node to denote the subgraph rooted by it and to represent a multi-valued function.

An MDD is ordered if the labels of internal nodes in each path from the root node to a terminal node follow the same order. An MDD is reduced if it contains neither isomorphic sub-graphs nor nodes where all outgoing arcs points to the same node. An ordered and reduced MDD was proven to be a canonical form of multi-valued functions, that is, any multi-valued function has a unique ordered and reduced MDD w.r.t. a given variable order. In the rest of this paper, we assume that every MDD is ordered and reduced.

We say a multi-valued function f is a Boolean function, iff the domain of each variable of f contains only two elements {⊤,⊥}. Similarly to MDDs, binary decision diagrams (BDDs) [Bryant, 1986] are a graph-based representation of Boolean functions where each internal node n has exactly two outgoing arcs child⊤(n) and child⊥(n).

Example 1. Figure 1(a) depicts a DAG G with 7 vertices and 12 edges. A logical constraint requires valid paths on G to include edge e6 or both edges e5 and e11 simultaneously. We consider each edge ei as variable and use the Boolean function f(e1, · · · , e12) : e6 ∨ (e5 ∧ e11) to represent the above constraint. Figure 1(b) shows a BDD representing f where internal nodes are represented by circles and terminal nodes are represented by rectangles. The variable of nodes is shown on the left. Each arc child⊤(n) (resp. child⊥(n)) of node n is a solid line marked with the assignment ⊤ (resp. ⊥). The BDD representing f contains only nodes labeled by three variables e5, e6 and e11.

The logical constraint can be defined by a multi-valued function g(v1, · · · , v7). The domain of vi is the set of the outgoing edges of vi together with the special element ∅ indicating that vi is never traversed. For example, D2 = {∅, e3, e4, e5, e6} and D5 = {∅, e10, e11}. When v2 = e5 and v5 = e11, or v2 = e6, the function g returns ⊤. Figure 1(c) illustrates an MDD representing the multi-valued function g where each variable vi denotes a vertex of the DAG G shown in Figure 1(a).

2.3 Optimal Path Problem over DAGs

Given a weighted DAG, the optimal path problem aims to find a path from a source vertex to a target vertex on the given DAG such that its length is minimal or maximal. Numerous combinatorial optimization problems, such as the 0-1 knapsack problem, the edit distance problem, and the Viterbi path problem, can be formalized as optimal path problems over DAGs, especially those that can be solved with dynamic programming (DP). In this paper, we focus on the constrained optimal path problem over DAGs that is a variant of optimal path problem.

Definition 1. Given a DAG G = (V, E), a source vertex s, a target vertex t and a global constraint f on the paths from s to t, the constrained optimal path problem over DAGs aims to find the shortest or longest path from s to t that satisfies f.

We remark that in the field of constraint programming, the concept of global constraint is used to denote a constraint that can involve an arbitrary set of variables. In this paper, we use the terminology "global constraint" to denote the given logical constraint in the constrained optimal path problem.

3 BDD-Constrained Search

In this section, we first introduce a unified approach for the constrained optimal path problem over DAGs, namely BDD-constrained search (BCS), proposed in [Nishino et al., 2015]. Then, we discuss the deficiencies of BCS.

3.1 The Main Algorithm

The shortest path from the source vertex s to the target vertex t that goes across an intermediate vertex v is the concatenation of the shortest path in Psv and the shortest path in Pvt. This property makes it simple to design an efficient algorithm for the shortest path problem over DAGs with time complexity O(|E|) [Cormen et al., 2022]. The algorithm first constructs a topological order σv of vertices for the given graph G, and then searches the shortest path

Algorithm 1: BDD-Constrained Search

Input: G = (V, E): a weighted DAG; r: the root node of the BDD representing the constraint; s: the source vertex of G; t: the target vertex of G. Output: p: the shortest path from s to t under the constraint; l: the length of p. 1 σv ←a topological sorted order of vertices 2 σe ← a topological sorted order of edges w.r.t. σv 3 foreach v ∈ V do 4 L[v] ← ∅ and B[v] ← ∅ 5 L[s][r] ← 0 6 foreach ei taken in the topological order σe do 7 u ← Vs(ei) and v ← Vt(ei) 8 foreach (n, l) ∈ L[u] do 9 n′ ← followBDD(ei, n) 10 if n′ = ⊥ then continue ; 11 if there is no (n′ , l′ ) ∈ L[v] or L[v][n′ ] > l +wi then 12 L[v][n′ ] ← l + wi and B[v][n′ ] ← (ei, n) 13 l ←L[t][⊤] and (e, n) ←B[t][⊤] 14 p ← ∅ 15 while Vs(e) ̸= s do 16 append the edge e to p 17 (e, n) ← B[Vs(e)][n] 18 append the edge e to p

among vertices arranged in σv. For each intermediate vertex v between s and t, we only keep the shortest path p from s to v since p is a prefix of the shortest path from s through v to t.

Unfortunately, the aforementioned property does not hold in the constrained optimal path problem.

Definition 2. Let v be an intermediate vertex between the source vertex s and the target vertex t and f the global constraint on Pst. Let p be a prefix path in Psv. A valid suffix path q ∈ Pvt w.r.t. p is such that the concatenation of p and q satisfies f. We use Rp for the set of valid suffix path w.r.t. p on Pvt.

By selecting different prefix paths from Psv, the sets of

Algorithm 2: followBDD Input: e: an edge; n: a BDD node representing the local constraint fp w.r.t. the path p. Output: n′ : the BDD node representing the local constraint fq w.r.t. the path q where q is the concatenation of p and e. 1 if n is a terminal node then n′ ←n; 2 while var(n) ≺σe e do /* σe is the topological order of edges */ 3 n← child⊥(n) 4 if n is a terminal node then n′ ← n; 5 n′ ←n 6 if var(n) = e then n′ ← child⊤(n) ;

valid suffix paths on Pvt vary. Hence, the shortest path in Psv may not be a prefix of the shortest path from s through v to t that satisfies the given logical constraint. We illustrate this with the following example.

Example 2. Figure 1(a) illustrates a weighted DAG G and 1(b) depicts a BDD representing the global constraint f : e6∨ (e5 ∧ e11). Suppose that we want to obtain the shortest path from v1 to v7 satisfying the constraint f . The set Pv1v5 of prefix paths contains paths p1 : [e2, e5, e7] and p2 : [e2, e6, e9] while the set Pv5v7 of suffix paths contains p3 : [e10, e12] and p4 : [e11]. If the prefix p1 is chosen, then only the suffix p4 can be chosen so that the concatenation of p1 and p4 is a valid path. Nevertheless, if we choose p2, then both p3 and p4 are able to concatenate with it in that p2 already satisfies the global constraint. The paths p1 and p2 have length 4 and 6, respectively. The path [e2, e6, e9, e10, e12] of length 9 with prefix p2 however is shorter than the path [e2, e5, e7, e11] of length 10 with prefix p1.

A simple extension to the algorithm for the shortest path problem is to save all of the possible paths from s to every intermediate vertex v. This extended algorithm however requires time and space exponential to |E| and is inefficient.

In order to address the space explosion issue, BCS groups equivalent paths together so as to prune the search space of paths. Two paths p and q are equivalent, if they reach the same vertex (that is, p, q ∈ Psv for some vertex v) and the two sets of valid suffix paths w.r.t. p and q are identical (that is, Rp = Rq). If q is longer than p, we only keep the shorter one p for the vertex v and the set of valid suffix paths Rp since the valid shortest path of Pst does not contain q.

The global constraint f is a logical representation of the set of valid paths of Pst. Given a prefix path p on Psv, the local constraint fp w.r.t. p represents the set of valid suffix paths w.r.t. p. If f is represented by a Boolean function, then the subfunction fp can be obtained by replacing the variable ei in the constraint f by ⊤ (resp. ⊥) if ei ∈ p (resp. ei /∈ p) for every edge ei ∈ Esv.

Example 3. As illustrated in Example 2, path p1 is [e2, e5, e7]. Path p1 connect vertex v1 and v5. The edges in Ev1v5 that occur as variables in the global constraint f are e5 and e6. Since e5 ∈ p1 and e6 /∈ p1, we replace e5 (resp. e6) by ⊤ (resp. ⊥) in f and obtain the local constraint fp1 = ⊥∨ (⊤∧e11) ≡ e11, meaning that any suffix path that contains edge e11 concatenated with p1 is valid.

The main idea of BCS is to combine equivalent paths from s to v into a group and to save groups of equivalent paths as Boolean functions. BCS keeps only the shortest path for each intermediate vertex v and each logically different local constraint on Pvt. Two important components of BCS are (1) deriving the local constraint fp w.r.t. a prefix path p and (2) combining equivalent local constraints fq and fq for every equivalent prefix paths p, q ∈ Psv. The above two components are accomplished via utilizing BDDs.

The main algorithm of BCS, shown in Algorithm 1, maintains two sets of tables L and B where L stores the length of the shortest path while B stores the backtracking information that is used to obtain the constrained shortest path. Both sets L and B have |V| tables L[v] and B[v] for v ∈ V, respectively. The tables L[v] and B[v] are a mapping that takes BDD nodes as keys. Suppose that the current shortest path p from s to v with a local constraint fp on Pvt is l. The local constraint fp is represented by a BDD node n. The expression L[v][n] = l (or (n, l) ∈ L[v]) indicates that the path p has length l. The expression B[v][n] = (e, n′ ) means that (1) the last edge of p is e; and (2) the BDD node n′ denotes the local constraint w.r.t. the path q, which is the prefix of p without only the edge e.

Algorithm 1 works as follows. It first constructs two topological sorted orders σv of vertices and σe of edges, initializes every tables L[v] and B[v] as empty table for each vertex v and sets L[s][r] to be 0 where r is the root node of the BDD representing the global constraint (lines 1 - 5). Then, it traverses each edge ei in the topological sorted order σe (lines 6 - 12). Let u and v be the source and target vertex of ei, respectively. Suppose that the length of the current shortest path p from s to u with the local constraint fp w.r.t. p represented by n is l (that is, (n, l) ∈ L[u]). We obtain a path q by extending the path p with the edge ei. The BDD node n′ denoting the local constraint fq w.r.t. q is generated via the subprocedure followBDD(ei, n), which will be elaborated later. When n′ is a terminal node ⊥, denoting that no valid suffix path w.r.t. q exists, Algorithm 1 continues to the next pair. If a shorter path from s to v with the local constraint fq is found, then the table L[v] and B[v] are simultaneously updated (lines 11 - 12). After traversing all edges, L[t][⊤] is the length of the shortest path that satisfies the global constraint, and we can retrieve the edges along the shortest path via the set B of tables (lines 13 - 18).

The subprocedure followBDD is illustrated in Algorithm 2. It aims to derive the local constraint fq w.r.t. the path q from the local constraint fp w.r.t. p and an edge e where the path q is the concatenation of p and e. It takes the edge e and a BDD node n denoting the local constraint fp as input, and outputs the BDD node n′ denoting the local constraint fq. If n is a terminal node ⊥, then there exists no valid suffix path w.r.t. p and hence n′ is also ⊥ (lines 1 and 4). In the case where n is a terminal node ⊤, any suffix path is valid and hence n′ is also ⊤ (lines 1 and 4). The variable order of the BDD that represents the global constraint follows the topological order σe of edges. The variable var(n) of the BDD node n is an edge e′ . Every edge e′′ that comes before the edge e and after e′ in σe is not chosen. Therefore, we continue moving to the ⊥-child of the BDD node n until we reach a node whose variable either follows or equals to e (line 3). Finally, if the variable of n is e, we move to its ⊤-child since the current path p contains e (line 6). We show the run of Algorithm 1 by the following example.

Example 4. We continue Example 2. The BDD representing the global constraint f : e6 ∨ (e5 ∧ e11) is illustrated in Figure 1(b), and its root node is n1. Initially, the table L[v1] contains only one pair (n1, 0). Then, Algorithm 1 traverses edges in the topological order [e1, · · · , e12]. Edge e1 starts at v1 and ends at v6. For the pair (n1, 0) ∈ L[v1], the subprocedure followBDD(e1, n1) returns n1. Since L[v6][n1] is not computed yet, we add an element (n1, 1) (resp. (n1, (e1, n1))) to table L[v6] (resp. B[v6]). Algorithm 1 handles other edges in the same way. Finally, the length of the shortest path satisfying the global constraint is 9, stored in L[v7][⊤]. We recover the shortest path [e2, e6, e9, e10, e12] via backtracking the entry B[v7][⊤] = (e12, ⊤).

3.2 Deficiencies of BDD-Constrained Search

BCS reduces many redundant searches on paths via grouping the equivalent paths together and maintaining equivalent local constraints w.r.t. prefix paths in BDDs. Hence BCS performs well in solving the constrained optimal path problem over DAGs. However, we observe that BCS still involves redundant operations and illustrate this in the following.

Let e be an edge from vertex u to vertex v and σv a topological order of vertices. We say an edge e′ is e-forbidden w.r.t. σv, if u ⪯σv Vs(e′ ) and Vs(e′ ) ≺σv v. When edge e is chosen, any e-forbidden edge cannot be chosen from the DAG. However, when deriving the local constraint w.r.t. the path p with the last edge e, BCS still considers these eforbidden edges and hence involves the following three types of redundant operations: (1) It processes e-forbidden edges that occurs in the BDD; (2) It generates an incorrect local constraint w.r.t. p, that is, a Boolean function represented by a BDD does not conform to the local constraint w.r.t. p; and (3) The two tables L[v] and B[v] include unnecessary information due to the incorrect local constraint.

Example 5. We continue with Example 2. The source vertex of edge e1 is v1 and the target vertex is v6. Clearly, e1 is also a path from v1 to v6. The topological order

Algorithm 3: followMDD

Input: e: an edge; n: an MDD node representing the local constraint gp w.r.t. the path p. Output: n′ : the MDD node representing the local constraint gq w.r.t. the path q where q is the concatenation of p and e. 1 if n is a terminal node then n′ ←n; 2 if var(n) = Vs(e) then n← childe(n) ; 3 while var(n) ≺σv Vt(e) do /* σv is the topological order of vertices */ 4 n← child∅(n) 5 if n is a terminal node then n′ ← n; 6 n′ ←n

σ of vertices is [v1, v2, v3, v4, v5, v6, v7]. It follows that the vertices, which are after v1 and before v6 w.r.t. σ, are {v1, v2, v3, v4, v5}. The set of e1-forbidden edges is {e2, e3, e4, e5, e6, e7, e8, e9, e10, e11}. Edge e2 has the same source vertex v1 as e1. Any path contains at most one outgoing edge for each vertex. When e1 is chosen, the remaining path does not contain edge e2. Similarly, the remaining path does not go through the vertices v2, v3, v4 and v5. Hence the outgoing edges of the above vertices cannot be chosen.

We hereafter show the redundant operations of BCS. After initialization, Algorithm 1 first handles edge e1. In the case where e1 is chosen, we obtain a path p : [e1]. Any e1-forbidden edge, including e5 and e6, cannot be chosen. In addition, the global constraint f requires a valid path to contain edge e6 or both edges e5 and e11 simultaneously. Therefore any path with prefix p fails to satisfy f and the local constraint w.r.t. p is ⊥.

Since e1 precedes e5 in the topological order of edges, Algorithm 1 invokes the subprocedure followBDD(e1, n1) that yields the BDD node n1, and then computes the two entries L[v6][n1] and B[v6][n1]. In fact, the Boolean function e6 ∨ (e5 ∧ e11) represented by n1 is an incorrect local constraint w.r.t. p. In addition, for each path q ∈ Pv1v6 , there is no local constraint w.r.t. q represented by n1. As a result, the two tables L[v6] and B[v6] contain unnecessary entries L[v6][n1] and B[v6][n1] for the incorrect local constraint. The vertex has only one outgoing edge e12. In the subsequent subprocedure followBDD(e12, n1), it is inevitable to assign the Boolean value ⊥ to n1 and n2 (line 3), meaning that e5 and e6 are not chosen in the path whose prefix is p.

4 MDD-Constrained Search

As pointed out in the previous section, BCS involves three types of redundant operations. In this section, we introduce the proposed algorithm, MDD-constrained search (MCS), reducing the redundant operations of BCS. Then, we propose two improvements: domain reduction and DAG partition to represent constraints in more compact MDDs.

4.1 MDD-Constrained Search

In order to mitigate the deficiencies of BCS, we design a novel search algorithm, namely MDD-constrained search, which adopts the same main search framework illustrated in Algorithm 1 as BCS. The main idea is to represent the global constraint in multi-valued function where each variable is a vertex in a DAG and the domain of each variable is the outgoing edges of its corresponding vertex along with the special element ∅. Furthermore, we make use of MDDs as the representation of global constraints instead of BDDs. Finally, we develop a subprocedure followMDD instead of followBDD in BCS.

We begin by elaborating how to gain the local constraint in multi-valued function. Suppose that p is a prefix path of Psv and g is a multi-valued function representing the global constraint on Pst. The local constraint gp w.r.t. p is obtained as follows: for every edge ei ∈ Esv, the value of the variable Vs(ei) in the constraint g is assigned to be ei if ei ∈ p and to be ∅ if there is no edge ej ∈ Esv s.t. ej ∈ p and Vs(ei) = Vs(ej ).

The subprocedure followMDD, illustrated in Algorithm 3, takes the edge e and the MDD node n representing the local constraint gp as input, and outputs the MDD node n′ representing the local constraint gq. The MDD node n′ is also a terminal node if n is (line 1). When n is ⊥ (resp. ⊤), q concatenated with any suffix path is invalid (resp. valid). Any vertex that comes between u and v in the topological order of vertices is not traversed. Therefore, we go to the arc child∅(n) of the MDD node n until we reach a terminal node or a node whose variable either follows or equals to v (lines 3 - 5).

Suppose that a path p connects vertex u to vertex v, with e as its last edge. Due to the use of multi-valued function representing local constraint, MCS has the following advantages: (1) It does not consider all e-forbidden edges but simply assigns ∅ to each source vertex of them; (2) It always obtains the correct local constraint w.r.t. the given path p, which confirmed by the Theorem 1; and (3) There is no unnecessary information caused by incorrect local constraints in tables L[v] and B[v]. We show how MCS reduces the redundant operations of BCS with the following example.

Example 6. We continue with Example 5. The MDD representing the global constraint g : (v2 = e5 ∧ v5 = e11) ∨ v2 = e6 is illustrated in Figure 1(c). We select the first edge e1 and obtain a path p : [e1]. The target vertex of e1 is v6. The local constraint on Pv6v7 w.r.t. p is ⊥.

To obtain the local constraint w.r.t. the path p, MCS invokes the subprocedure followMDD(e1, n1). Since v6 is a vertex that follows v2 in the topological order of vertices, followMDD assigns ∅ to the MDD node n1 and reaches the ⊥-node. The two edges e5 and e6 are e1-forbidden, no valid suffix path when e1 is chosen. Hence, ⊥ is the correct local constraint w.r.t. p and there is no unnecessary entries stored in L[v6] and B[v6]. In addition, MCS does not consider both e5 and e6, expect for assigning ∅ to one vertex v2.

Theorem 1. Let e be an edge from vertex u to vertex v, and p and q two paths where q is the concatenation of p and e. Let n be the MDD node representing the correct local constraint w.r.t. p. The subprocedure followMDD(e, n) returns the MDD node n′ representing the correct local constraint w.r.t. q.

Proof. By assumption, the MDD node n represents the correct local constraint gp w.r.t. p, that is, for every edge ei ∈

Algorithm 4: followMDD' Input: e: an edge; n: an MDD node representing the local constraint gp w.r.t. the path p. Output: n′ : the MDD node representing the local constraint gq w.r.t. the path q where q is the concatenation of p and e. 1 if n is a terminal node then n′ ←n; 2 if var(n) = Vs(e) then 3 if e in the domain of var(n) then 4 n ← childe(n) 5 else 6 n ← child∅(n) 7 while var(n) ≺σv Vt(e) do /* σv is the topological order of vertices */ 8 n← child∅(n) 9 if n is a terminal node then n′ ← n; 10 n′ ←n

Esu, the value of the variable Vs(ei) in the constraint g is assigned. The subprocedure followMDD(e, n) handles every vertex that comes after u and before v (lines 2 - 5 in Algorithm 3). Hence, for each edge ej ∈ Euv, the variable Vs(ej) is assigned. Thus n′ denotes the correct local constraint w.r.t. q.

4.2 Domain Reduction

In the previous subsection, we showed the advantage of using multi-valued functions to represent constraints over Boolean functions. Each vertex in general has a huge number of outgoing edges in a large-scale DAG. Hence, the domain of each vertex in the multi-valued function has many elements and each node in the MDD has a great number of outgoing arcs. It takes much time to create the MDD representing the global constraint.

To solve the above problem, we propose domain reduction for multi-valued function. An edge ei with source vertex v is irrelevant to a global constraint g, if g(e1, · · · ,∅, · · · , en) = g(e1, · · · , ei, · · · , en) for every outgoing edge ei of each vertex vi. To reduce the domain of vertex v, all irrelevant edges of v can be combined into the special element ∅. The notation v = ∅ indicates that either the outgoing edge of v is one of the irrelevant edges or v is never traversed. For example, Figure 1(c) represents g : (v2 = e5 ∧ v5 = e11) ∨ v2 = e6 as the MDD without domain reduction while Figure 1(d) depicts the MDD with domain reduction. In the former MDD, the node with label v2 has 5 outgoing arcs, whereas in the latter, it has only 3. As e3 and e4 does not occur in g and hence is irrelevant, the reduced domain of the variable v2 is {∅, e5, e6}.

We also adjust the subprocedure followMDD. The adjusted subprocedure, namely followMDD′ , illustrated in Algorithm 4, is the same as followMDD except the following. If an edge e is in the reduced domain of the vertex var(n), we choose the childe(n); otherwise, we choose child∅(n) (lines 3 - 6). The subprocedure followMDD′ has only one more step than followMDD, which is to determine whether an edge is in the domain of a vertex (lines 3 - 6). This step has no influence on the variable assignment process. Therefore, followMDD′ (e, n) always outputs the correct local constraints as well.

Theorem 2. Let e be an edge from vertex u to vertex v, and p and q two paths where q is the concatenation of p and e. Let n be the MDD node representing the correct local constraint w.r.t. p. The subprocedure followMDD′ (e, n) returns the MDD node n′ representing the correct local constraint w.r.t. q.

4.3 DAG Partition

In 0-1 knapsack and Viterbi path problems, we can partition the set of vertices into mutually exclusive groups so as to reduce the number of variables in the global constraint. For example, in the DAG representing a Viterbi path problem instance, some vertices have the same meaning that assigns different hidden states to the same specific output o. In this case, these vertices can be combined into a group. Meanwhile, the outgoing edges of a vertex from the group can also be grouped together, since they represent the operation of choosing one specific state for o simultaneously. Thus, the constraint of assigning the state to o can be reduced into a constraint on the edge group in the Viterbi path problem.

Let G = (V, E) be a DAG, s the source vertex, and t the target vertex. Suppose that we have a topological order σv of vertices and a topological order σe of edges. Partitioning V into a collection V 1G , · · · , V n G satisfies the following two conditions: (1) for every 1 ≤ i ≤ n - 1, every two vertices v ∈ V iG and v′ ∈ V i+1 G , we have v ≺σv v′ ; and (2) any path from s to t goes through at most one vertex of each group V iG for 1 ≤ i ≤ n. Similarly, partitioning E into a collection E 1 G , · · · , E m G satisfies : (1) for every 1 ≤ i ≤ m- 1, every two edges e ∈ E iG and e′ ∈ E i+1 G , we have e ≺σe e′ ; and (2) any path from s to t contains at most one edge of each group E iG for 1 ≤ i ≤ m.

In general, the domain of each group V iG consists of each outgoing edge group of each vertex v ∈ V iG together with the special element ∅. In 0-1 knapsack and Viberti path problems, any path that starts at s and ends with t has to go through one vertex from each vertex group. In this case, the domain of the group V iG does not contain the special element ∅ if all outgoing edge groups of each vertex v ∈ V iG are contained in the constraint.

5 Complexity Analysis

In this section, we analyze the time and space complexity of both search algorithms: BCS and MCS.

We first introduce two concepts for complexity: width and forbidden nodes and elaborate them with an example.

Definition 3. The width of a MDD is the maximum number of nodes pointed to by the edges in a cut of the MDD at a level of nodes.

Definition 4. Let e be an edge and σe a topological order of edges. Let Ee be a set of edges where each edge e′ of Ee is such that (1) Vt(e′ ) = Vt(e) and that (2) e is e′ -forbidden.

Let e′′ be the minimal element of Ee w.r.t. σe. Let FB be a BDD representing the global constraint. The forbidden node of level e in FB is a node that is between the level e′′ and e.

Example 7. Figure 1(a) depicts a DAG G with a topological order σe of edges. Figure 1(b) illustrates a BDD FB representing the global constraint f = e6 ∨ (e5 ∧ e11), where only levels e5, e6 and e11 contain nodes. The number of nodes pointed to by the edges in the cuts of levels e5, e6, and e11 is 2, 3, and 2, respectively. Hence the width of FB is 3.

The set Ee8 contains one edge e6, and the minimal element of Ee8 w.r.t. σe is also e6. Two BDD nodes n2 and n3 are between level e6 and e8 in FB. Hence, both n2 and n3 are forbidden nodes of level e8.

The time and space complexity of BCS are given in the following theorem.

Theorem 3. Let G = (V, E) be a DAG and FB a BDD representing the global constraint. Let wB be the width of FB and γ the maximum number of forbidden nodes of a level in FB. The time complexity of BCS is O(|E|2 · (wB + γ)), and the space complexity is O(|V| · (wB + γ)).

Proof. For a vertex v, the sizes of L[v] and B[v] depend on the number of BDD nodes that are used as keys. Let Ev be a set of edges where Ev = {e′ | Vt(e′ ) = v}. Let σe be a topological order of edges and e the maximal element of Ev w.r.t. σe. We first focus on correct local constraints. The two tables L[v] and B[v] have at most as many keys as nodes pointed to by the edges that intercepts a cut of FB at level e. The number of these nodes is at most wB. We now consider incorrect local constraints. For the vertex v, BCS obtains at most as many different incorrect local constraints as forbidden nodes of level e. The number of these forbidden nodes is at most γ. As a result, L[v] and B[v] have at most wB + γ keys. Thus the space complexity is O(|V| · (wB + γ)).

The update process in Algorithm 1 (lines 6 - 12) performs at most |E| · (wB +γ) times. Each update process invokes the subprocedure followBDD, which performs the traverse process in Algorithm 2 (lines 2 - 4) at most |E| times. Therefore, the time complexity is O(|E|2 · (wB + γ)).

We remark that the time and space complexity of BCS given in this paper is different from that in [Nishino et al., 2015], where the time and space complexity are O(|E| · wB). This is because Nishino et al. [2015] did not consider incorrect local constraints and the time complexity of the subprocedure followBDD. The space complexity is O(|V| · (wB +γ)) rather than O(|E| · wB) since the numbers of L[v] and B[v] are equal to the number of vertices.

Finally, we provide the time and space complexity of MCS.

Theorem 4. Let G = (V, E) be a DAG, FM a MDD representing the global constraint and wM the width of FM. The time complexity of MCS is O(|E| · |V| · wM), and the space complexity of MCS is O(|V| · wM).

Proof. Let v be a vertex in the given DAG and u the previous vertex of v in the topological order σv. Two tables L[v] and B[v] have at most as many keys as nodes pointed to by the edges that intercepts a cut of FM at level u, and the number

of these nodes is at most wM. As a result, the space complexity of MCS is O(|V| · wM). The update process in Algorithm 1 (lines 6 - 12) for MCS performs at most |E| · wM times. Since each update process invokes the subprocedure followMDD and the traverse process in followMDD (lines 2 - 5 in Algorithm 3) executes at most |V| times, the time complexity of MCS is O(|E| · |V| · wM).

Compared with followMDD, followMDD′ only has one more step that determines if an edge is in the domain of a vertex (lines 3 - 6 in Algorithm 4). This process executes at most once in each followMDD′ . As a result, MCS with domain reduction has the same time and space complexity as MCS without domain reduction.

Since MCS always obtains the correct local constraint w.r.t. a path (Theorems 1 and 2), the time and space complexity of MCS does not contain the parameter γ where γ is the maximum number of forbidden nodes at a level in the BDD representation of the global constraint. BDD treats edges as variables while MDD treats vertices as variables. Hence, the assignment process in followBDD performs at most |E| times, while that in followMDD executes at most |V| times. In most constrained optimal path problems, the number |E| of edges in DAGs is much larger than the number |V| of vertices. Although the width wM of the MDD representation of the global constraint is not guaranteed to be smaller than the width wB of BDD representation in theory, the experimental results show that wM is always less than or equal to wB. In summary, MCS has better time and space complexity than BCS.

6 Experiments

6.1 Settings and Datasets

As Nishino et al. [2015] did not provide the source code of BCS, we reproduce this algorithm. Both BCS and MCS are implemented in C++ 3 . We use the CUDD package [Somenzi, 2015] to construct BDD and the Meddly library [Babar and Miner, 2010] to MDD. It is worth noting that our implementation of BCS has similar performance as the original BCS proposed in [Nishino et al., 2015] due to simplicity of BCS illustrated in Algorithm 1. All experiments were conducted on a Linux machine with Intel Core i7-10700 2.90GHz CPU and 16 GB RAM.

We compare our proposed algorithm MCS to BCS on the following four categories of datasets: the shortest path problem over DAGs, the 0-1 knapsack problem [Kellerer et al., 2004], the edit distance problem [Wagner and Fischer, 1974] and the Viberti path problem [Forney, 1973]. We remark that all datasets were mentioned in [Nishino et al., 2015]. We contacted Nishino et al., but they did not provide the datasets. We therefore download all datasets from the original source and preprocess the datasets according to the method in [Nishino et al., 2015]. So the numbers of vertices and edges are a bit different from those in [Nishino et al., 2015].

3 The source code and datasets are publicly available in https: //github.com/someMing/MDD-constrained-search.

The information about the datasets is summarized in Table 1. The columns |V| and |E| represent the number of vertices and edges of the transformed DAGs for each problem, respectively. The columns |VG| and |EG| indicate the number of vertex groups and edge groups of DAGs via DAG partition for 0-1 knapsack problem and Viberti path problem, respectively.

6.2 Logical Constraints

We consider two types of global constraints: Checkpoint and Disjunction that are used in [Nishino et al., 2015].

Checkpoint Constraints. Suppose that we have several disjoint subsets E1, · · · , En of edges. The checkpoint constraint requires any valid path to include at least one edge from each set Ei for 1 ≤ i ≤ n. The checkpoint constraints are generated via the pair of two parameters (n, ρ). The pair (n, ρ) means that we first randomly select edges with probability ρ and then randomly divide them into n sets of equal size. We generate three constraints using the parameters (3, 0.01), (5, 0.05), and (8, 0.2) for each problem instance, and call them Check1, Check2, and Check3.

Disjunctive Constraints. Given a collection of pairs of edges, the disjunctive constraint requires any valid path cannot contain both edges from the same pair. The knapsack problem with disjunctive constraint is the disjunctively constrained knapsack problem (DCKP) [Yamada et al., 2002]. The disjunctive constraints are generated via the pair of two parameters (k, ρ). The pair (k, ρ) means that we first select k-best edges with smaller (resp. greater) weight in the shortest (resp. longest) path problem, and generate all the possible pair from selected edges. Then we randomly select disjunctive pairs from them with probability ρ. We generate three constraints using the parameters (50, 0.01), (60, 0.7), and (100, 0.8) for each problem instance, and mention them Dis1, Dis2, and Dis3.

6.3 Results

The experimental results are shown in Table 2. The columns "Nodes", "Arcs", and "Width" denote the number of nodes, the number of arcs, and the width of compiled decision diagrams, respectively. The columns "Entries" and "Total time" indicate the number of entries of sets L and B and the total running time (milliseconds) in both search algorithms BCS and MCS, respectively. As the numbers of nodes and entries in the MCS with and without domain reduction are identical, we display them together. The total time contains the time of compiling constraints into decision diagrams and of search the optimal path. Due to space limitation, we only present the total time here. In most instances, the compilation time accounts for a small proportion of the total time (1% - 26%), except the shortest path problem over DAGs and the edit distance problem with disjunctive constraints. On the one hand, the decision diagrams representing disjunctive constraints have a huge size, requiring more compilation time. On the other hand, the number of k-best edges defined by disjunctive constraints is much smaller compared to the number of edges, resulting in a large number of equivalent paths and less search time. The best data for columns "Nodes", "Arcs", "Width" , "Entries" and "Total time" is the smallest data among the three algorithms BCS and MCS with and without domain reduction. We highlight the best data in bold.

MDDs vs BDDs. We begin by comparing the size of BDDs and MDDs with domain reduction. The former has at least as many nodes as the latter. Except the shortest path problem over DAGs with Check2 and Check3 constraints and the edit distance problem with Check3 constraint, MDDs with domain reduction have fewer or an equal number of arcs compared to BDDs. The width of MDDs is at least as less as that of BDDs. This indicates that MDDs with domain reduction is a more compact form of representing logical constraints than BDDs.

The nodes and width in MDDs with and without domain reduction are identical. However, the number of arcs in MDDs with domain reduction is significantly less than that in MDDs without domain reduction. Especially for the shortest path problem over DAGs and the Viterbi path problem, domain reduction achieves at least 3.57 times compression rate. This indicates that domain reduction can effectively reduce the number of arcs in MDDs. As an exception, the number of arcs of both are identical on the Knapsack problem. This is because each vertex group in the DAGs has only two outgoing edge groups, hence there is no improvement via domain reduction.

MCS vs BCS. MCS is consistently faster than BCS, expect in the instance Knapsack with Dis2 constraint. This is because in this instance, BCS does not obtain many incorrect local constraints, resulting in close search times for both algorithms. However, MCS uses 439ms for compilation while BCS just needs 181ms. In most instances, MCS substantially outperforms BCS, for example, the running time of BCS is nearly 11.60 times that of MCS in the Viterbi path problem with Check3 constraint. In addition, MCS stores less entries of sets L and B than BCS. This is because MCS always derives the correct constraint w.r.t. a given path, resulting in a substantial reduction of redundant operations. These experimental results demonstrate that MCS can reduce the search space compared to BCS, leading to less memory requirements and running time.

We can observe that domain reduction is able to accelerate the MCS algorithm in 15 out of 24 instances. In these instances, most variables have domains with large sizes. Domain reduction significantly reduce the number of arcs in the MDDs, thereby decreasing the compilation time. For other 9 instances, the sizes of domains of variables are small. The compact improvement on sizes due to domain reduction can be neglected. Moreover, MCS with domain reduction requires additional operations to determine if the input edges is in the domain of the vertices, increasing the search time.

We do not make a comparison between MCS and CPLEX. It was demonstrated in [Nishino et al., 2015] that BCS performs better than CPLEX on constrained optimal path Andersen et al. [2007] adopted MDDs for constraint store and showed that propagation over MDDs solves all-different problems more efficient than typical domain propagation. A prize-collecting scheduling problem requires selecting a subset of elements from a ground set and ordering the selected elements. For this problem, Horn et al. [2021] utilized MDDs to encode the solutions and proposed a novel construction scheme for MDDs. An extension to MDDs, namely AND/OR MDDs, introducing the AND/OR search space, was proposed in [Mateescu and Dechter, 2006]. Later, Mateescu et al. [2007] used AND/ORMDDs to represent the optimal set of solutions for constraint optimization problems.

8 Conclusions

In this paper, we have proposed a new algorithm, namely MDD-constrained search (MCS), to solve the constrained optimal path problem over DAGs. It considers the logical constraints as multi-valued functions, and uses multi-valued decision diagrams to handle the constraints. Compared with BCS, MCS can always obtain the correct local constraint w.r.t. a given path, and hence reduce numerous redundant operations. From both the time and space perspective, our proposed method is significantly superior to BCS.

Acknowledgments

This paper was supported by National Natural Science Foundation of China (62276114 and 62377028), Guangdong Basic and Applied Basic Research Foundation (2023B1515120064), Science and Technology Planning Project of Guangzhou (202206030007, Nansha Dis-

problems over DAGs. So is MCS.

7 RelatedWork

Some algorithms were proposed for some optimal path problems with specific constraints. Samphaiboon and Yamada [2000] developed a dynamic programming algorithm for the precedence-constrained knapsack problem where the constraint requires that some items can only be selected if their corresponding preceding items have been selected. Multiple sequence alignment with user-defined anchor points takes user-defined homology information as constraints, and a method to solve this problem was introduced in [Morgenstern et al., 2006]. Oommen [1986] proposed an algorithm to solve the edit distance problem with the constraint involving the number and type of edit operations, and Petrovi´c and Goli´c [1993] focused on the edit distance problem with more complex constraints. These above algorithms only solve optimal path problems with specific constraints. In contrast, our MCS approach is a general method to the constrained optimal path problem with arbitrary global constraint that is represented by an MDD. In real applications, we sometimes require solutions to satisfy multiple constraints. MDDs support polytime conjunction operation so as to combine different constraints efficiently.

MDDs provide a compact and efficient representation for multi-valued functions and large sets. Therefore, MDDs are widely used in the fields of constraint programming and combinatorial optimization. Domain propagation is a crucial step for constraint programming. The results of domain propagation are maintained in a constraint store.

trict: 2023ZD001), Jilin Province Natural Science Foundation (20240101378JC), Key Laboratory of Smart Education of Guangdong Higher Education Institutes, Jinan University (2022LSYS003), the Fundamental Research Funds for the Central Universities, JNU (21623202) and the Fundamental Research Funds for the Central Universities, JLU (93K172022K03).