Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

Let $\mathcal{P}$ be an instance of a discrete minimization problem with $n$ variables $\{x_{1},...,x_{n}\}$, let $Sol(\mathcal{P})$ be the set of feasible solutions to $\mathcal{P}$, let $z^{*}(\mathcal{P})$ be an optimal solution to $\mathcal{P}$, and let $D(x_{i})$ be the domain of variable $x_{i},i\in\{1,...,n\}$. Let $\mathcal{M}$ be a multivalued decision diagram that contains potential solutions to $\mathcal{P}$. $\mathcal{M}$ is a directed acyclic graph divided into $n+1$ layers; let $\ell_{u}$ be the index of the layer containing node $u,u\in\mathcal{M}$, and let $L_{i}$ be the set containing the nodes on layer $i$. Layer $1$ contains only a root node $r$ (with no in arcs), and layer $n+1$ contains just a terminal node $t$ (with no out arcs). Each arc $a_{uv}\in\mathcal{M}$ goes from a node $u$ on layer $\ell_{u}\in\{1,...,n\}$ to a node $v$ on layer $\ell_{u+1}$ ($\ell_{u+1}=\ell_{v}$). Each arc $a_{uv}$ has a label representing the assignment of variable $x_{\ell_{u}}$ to $l\in D(x_{\ell_{u}})$. An arc $a_{uv}$ with label $l$ ($a_{uv}\rightarrow l$) also has a value $v(a_{uv})$ equal to the value of being at node $u$ and assigning $x_{\ell_{u}}$ to $l$ ($x_{\ell_{u}}=l$). For simplicity, we sometime refer to $v(a_{uv})$ as $v(a)$. Thus, each path from $r$ to $t$ represents the assignment of the $n$ variables to values, and a potential solution to $\mathcal{P}$.

Let $Sol(\mathcal{M})$ be the set of all paths in $\mathcal{M}$ from $r$ to $t$, and let $T^{*}(u)$ be the value of the shortest path from $r$ to a node $u$. If $Sol(\mathcal{M})=Sol(\mathcal{P})$, then $\mathcal{M}$ perfectly represents the solution space of $\mathcal{P}$, and we call $\mathcal{M}$ exact. If $\mathcal{M}$ is exact, then the value of the shortest path through the diagram is $z^{*}(\mathcal{P})$ (an optimal solution to $\mathcal{P}$). Let the shortest path through $\mathcal{M}$ be $z^{*}(\mathcal{M})$. If $Sol(\mathcal{M})\subseteq Sol(\mathcal{P})$, then $\mathcal{M}$ represents only feasible solutions to $\mathcal{P}$, but does not necessarily represent all feasible solutions to $\mathcal{P}$. In this case, we call $\mathcal{M}$ restricted, and use the notation $\overline{\mathcal{M}}$ to mean that $\mathcal{M}$ is restricted. The shortest path through $\overline{\mathcal{M}}$ is not guaranteed to be optimal, but it is guaranteed to be feasible. If $Sol(\mathcal{P})\subseteq Sol(\mathcal{M})$, then $\mathcal{M}$ represents all of the feasible solutions to $\mathcal{P}$, but potentially represents infeasible solutions as well. In this case, we call $\mathcal{M}$ relaxed, and use the notation $\underline{\mathcal{M}}$ to mean that $\mathcal{M}$ is relaxed. The shortest path through $\underline{\mathcal{M}}$ is guaranteed to be at least as good as $z^{*}(\mathcal{P})$, but is not guaranteed to be feasible.

Constructing an exact decision diagram for $\mathcal{P}$ is often intractable for large values of $n$. Observe that having an exact decision diagram means that the solution to $\mathcal{P}$ can be read in polynomial time by recursively calculating the shortest path through $\mathcal{M}$, so creating an exact decision diagram for NP-hard problems, such as for the travelling salesperson problem (TSP), is NP-hard as well [20]. The focus of most research that uses decision diagrams for optimization is on the construction of $\overline{\mathcal{M}}$ and/or $\underline{\mathcal{M}}$. Let $w=w(\mathcal{M})$ be the width of the largest layer of $\mathcal{M}$. The creation of an exact decision diagram potentially leads to $w$ being an exponential function of $n$, but when creating $\overline{\mathcal{M}}$ and/or $\underline{\mathcal{M}}$, $w$ can be constrained to be any natural number, limiting the number of operations construction will take. Let $w_{m}$ be the largest width allowed during construction. As $w_{m}$ approaches the width necessary to create an exact decision diagram, $z^{*}(\overline{\mathcal{M}})$ and $z^{*}(\underline{\mathcal{M}})$ approach $z^{*}(\mathcal{P})$, but the number of operations necessary to construct the diagram also increases.

Figure 1 gives an instance of sequence ordering problem (SOP), and Figure 2 contains simple examples of exact, restricted, and relaxed decision diagrams for that instance where $w_{m}=2$ for $\overline{\mathcal{M}}$ and $\underline{\mathcal{M}}$. The SOP requires finding the minimum-cost sequence of $n$ elements that includes each element exactly once, subject to transition costs $c_{ij}$ of following $x_{i}$ with $x_{j}$, and subject to precedence constraints requiring that certain elements precede others in the sequence. In other words, the SOP is an asymmetric TSP with precedence constraints. The label of each node matches the union of the labels of the incoming arcs. Each arc $a_{uv}$ is labeled in the format $(l,val(a_{uv}))$, representing the assignment of $x_{\ell_{u}}$ to $l$, and $val(a)$ represents the cost of the shortest path from the label of $u$ to $l$. In other words, an arc with label $l$ leaving layer $i$, represents the assignment of $l$ to the $i^{th}$ position of the sequence. The red path in each diagram indicates the shortest path through the diagram, and $T^{*}$ indicates the cost of the shortest path through the diagram.

Constructing $\overline{\mathcal{M}}$ for a given width $w_{m}$ is a straightforward process that can be thought of as a generalized greedy algorithm. Beginning with the root node $r$, an arc is generated for every element in the domain of $r$, and a node is generated at the end of each arc in the second layer. The process is repeated for each layer, except layer $n$ where all outgoing arcs point to the terminal, unless $w(\overline{\mathcal{M}})$ exceeds $w_{m}$. Then the least promising node is removed from the offending layer until $w(\overline{\mathcal{M}})$ is equal to $w_{m}$. The definition of least promising is a heuristic decision. For the purposes of this paper, the least promising node is the node $u$ such that the shortest path from $r$ to $u$ is longer than the shortest path from $r$ to any other node $v\neq u$ in layer $\ell_{u}$.

It is of note that another method of reducing the width of $\overline{\mathcal{M}}$ is merging equivalent nodes. In the SOP, two nodes can be considered equivalent if they have the same state (last element in the sequence), and all incoming paths have visited the same set of elements. For example, a node with exactly one incoming path $[A,B,C]$ could be merged with a node in the same layer with exactly one incoming path $[B,A,C]$. In many MDD applications this is a valuable insight, and it helps motivate the algorithm for constructing $\underline{\mathcal{M}}$. However, for the SOP, we observed that the work of finding equivalent nodes in $\overline{\mathcal{M}}$ often outweighed the benefit of being able to merge nodes.

There are many methods of constructing relaxed decision diagrams, and many heuristic decisions that must be made when doing so. In this paper, we focus on the method described by Cire and van Hoeve (2013) [21] for sequencing problems. As opposed to the top-down construction described in Section 2.2, here $\underline{\mathcal{M}}$ will be constructed by separation. Constructing DDs by separation uses $\underline{\mathcal{M}}$ as a domain store over which constraints can be propagated. This method starts with a weak relaxation, and then strengthens it by splitting nodes until each layer is either exact, or has a width equal to $w_{m}$. The algorithm begins from a $1$-width MDD with an arc from the node on layer $\ell_{i}$ to the node on layer $\ell_{i+1}$ for each element that can be placed at position $\ell_{i}$ in the sequence. Thus, even though each layer only has one node, there can be several arcs between layers (see the relaxed diagram in Figure 2). Then a node $u$ is selected and split to strengthen the relaxation. The process of splitting $u$ involves creating two new nodes $u^{\prime}_{1}$ and $u^{\prime}_{2}$, and then distributing the in arcs of $u$ between $u^{\prime}_{1}$ and $u^{\prime}_{2}$. Then for each out arc $a_{uv}$ from $u$, arcs $a_{u^{\prime}_{1}v}$ and $a_{u^{\prime}_{2}v}$ are added such that $a_{uv}$, $a_{u^{\prime}_{1}v}$ and $a_{u^{\prime}_{2}v}$ all have the same label. Finally $u^{\prime}_{1}$ and $u^{\prime}_{2}$ are filtered to remove infeasible and sub-optimal arcs. A collection of filtering rules are used to check each arc. As an example, given a feasible solution to $\mathcal{P}$ with objective value $z_{opt}$, an arc $a$ can be removed if all paths containing $a$ have an objective value greater than $z_{opt}$. The full process of identifying which arcs can be removed is detailed in Cire and van Hoeve (2013) [21], and is not replicated here.

The following notation and definitions are critical to understanding these algorithms. Let $All_{u}^{\downarrow}$ be the set of arc labels that appear in every path from $r$ to $u$. Let $Some_{u}^{\downarrow}$ be the set of arc labels that appear in at least one path from $r$ to $u$. Let $All_{u}^{\uparrow}$ and $Some_{u}^{\uparrow}$ be defined as above, except that they refer to paths from $u$ to $t$. Let $\mathscr{J}$ be the set of all possible arc labels. For the SOP, we define an exact node $u$ as a node where $Some_{u}^{\downarrow}=All_{u}^{\downarrow}$ and all arcs ending at $u$ originate from exact nodes. Intuitively, a node $u$ is exact if all paths to $u$ contain the same set of labels, and all parents of $u$ are exact. Algorithm 1 formalizes the process of strengthening $\underline{\mathcal{M}}$.

Deciding which nodes to split, and how to split them, are heuristic decisions with a significant impact on the bound that can be achieved without exceeding $w_{m}$ [20]. The algorithm discussed here selects nodes that can be split into equivalency classes, such that every path to the new node contains a certain label. Deciding which equivalency classes to produce first is another heuristic decision. The details of ordering the importance of the labels are specific to the problem being solved, and are not discussed here. However, it is important to note that the ordering for this implementation is static, and does not change between iterations.

In a typical branch-and-bound algorithm, the branching takes place by splitting on the domain of the variables. With decision diagrams, the branching takes place on the nodes themselves by selecting a set of exact nodes to represent the problem. The solver outlined by Bergman et al. [19] defines an exact node as a node $u$ for which every path from $r$ to $u$ ends in an equivalent state. As mentioned above, we can be more specific when applying this to sequencing problems, and define an exact node $u$ as a node where $Some_{u}^{\downarrow}=All_{u}^{\downarrow}$ and all arcs ending at $u$ originate from exact nodes. An exact cutset is defined as a set of exact nodes that contain every path from $r$ to $t$. Let $\underline{\mathcal{M}}(u)$ be a relaxed decision diagram with root $u$, and let $\overline{\mathcal{M}}(u)$ be a restricted decision diagram with root $u$. The branch-and-bound algorithm for MDDs proceeds by selecting an exact cutset of $\underline{\mathcal{M}}$, and using each node $u$ in the cutset as the root for a new restricted decision diagram $\overline{\mathcal{M}}(u)$ and relaxed decision diagram $\underline{\mathcal{M}}(u)$. A node can be removed from the queue if the relaxation of that node is not better than the best known solution to $\mathcal{P}$, otherwise the exact cutset of the new node is added to the queue, and the process repeats until the queue is empty. This is detailed by Algorithm 2.

Gillard et al. [13] expanded on Algorithm 2 by incorporating a local search. A heuristic is used to quickly calculate a rough relaxed bound¹¹1Gillard et al. [13] call the value rough upper bound, but since we are testing a minimization problem in this paper, we use the term rough relaxed bound instead. at each node, and if the length of the shortest path to that node plus the rough relaxed bound is worse than the best known solution, the node can be removed. More formally, let $rrb(u)$ be a rough relaxed bound on $\mathcal{P}$ starting from node $u$, and let $z_{opt}$ be the value of best known solution so far. If $T^{*}(u)+rrb(u)>z_{opt}$, the node can be removed. They also provide evidence that if $rrb(u)$ is inexpensive to compute, it can be used to filter nodes in $\overline{\mathcal{M}}$ and $\underline{\mathcal{M}}$. The method of using a rough relaxed bound to trim nodes is used in this paper, but the details are problem specific and are discussed in a later section.

The branch-and-bound algorithm proposed by Bergman et al. (2016) [19] requires selecting an exact cutset of $\underline{\mathcal{M}}$. Peel-and-bound requires selecting a diagram from the queue, and an exact node to start the peel process. The choice of node has a substantial impact on how quickly the process converges to an optimal solution, because it serves two purposes simultaneously. As discussed earlier, the first purpose of peeling is to avoid recreating a portion of the diagram at each iteration. The second purpose is to strengthen the overall relaxation. Let $\underline{u}$ be a diagram peeled from $\underline{\mathcal{M}}$, and let $\underline{\mathcal{M}}^{*}$ be $\underline{\mathcal{M}}$ after the peel operation. If $Sol(\mathcal{P})\subseteq Sol(\underline{\mathcal{M}})$ then $Sol(\mathcal{P})\subseteq Sol(\underline{\mathcal{M}}^{*})\cup Sol(\underline{u})$. The only step of peel-and-bound that removes paths is the filter step, which only removes an arc if no feasible solutions can pass through that arc. If the node the peel is induced from contains the shortest path through $\underline{\mathcal{M}}$, then there will be a new shortest path through $\underline{\mathcal{M}}^{*}$ with $T^{*}(\underline{\mathcal{M}}^{*})\geq T^{*}(\underline{\mathcal{M}})$. Similarly after peeling, the peeled diagram is going to be strengthened and $T^{*}(\mathcal{M}(\underline{u}))\geq T^{*}(\underline{u})$. Therefore, when implementing the selectDiagram and selectExactNode functions from Algorithm 3, we propose selecting the diagram $\mathscr{D}$ with the weakest bound, and an exact node from $\mathscr{D}$ that contains $z^{*}(\mathscr{D})$ at each iteration. Using these parameters, the peel step of peel-and-bound strengthens the relaxed bound of $\mathcal{P}$, in addition to providing a stronger initial diagram to use when generating $\mathcal{M}(\underline{u})$.

We propose two heuristics for selecting a node from $\mathscr{D}$ that contains $z^{*}(\mathscr{D})$. The first heuristic picks the first node in the shortest path through the diagram with at least one child that is not exact, we call this the last exact node. The second heuristic picks the frontier node, the highest-index exact node that contains $z^{*}(\mathscr{D})$. Taking the last exact node is more of a breadth-first search, taking the largest possible set of nodes that can be strengthened (anything above the last exact node is exact, and cannot be improved). In contrast, taking the frontier node is more of a depth-first search, taking fewer nodes and exploring those nodes at greater depth.

Cire and van Hoeve (2013) [21] propose that each iteration of Algorithm 1 starts from a $1$-width MDD. However, for peel-and-bound with a non-separable objective function, starting from a $1$-width MDD poses a problem. The arcs in such a diagram do not have exact values, because they are dependent on the state of the node they originate from. As nodes are peeled, the values of those arcs must be updated, and the operation becomes computationally expensive at scale. This problem can be avoided by creating the initial diagram using a structure where all of the arcs ending at a given node have the same label. The resulting initial diagram has a width of $n$, and each node on the layer is assigned to one state $s\in\{1,...,n\}$. Then every possible feasible arc between consecutive layers is added. Thus, the nodes of $\underline{\mathcal{M}}$ do not have relaxed states, and each arc can only take one possible value. Starting from such a diagram not only removes the need to update arc values, it ensures that every arc generated during peel-and-bound is an exact copy of an arc that exists in the initial diagram, since arcs are only copied or removed, never updated or added. An alternative method of handling non-separable objective functions is explored by Hooker [22, 23, 24].

The focus of this paper is sequencing problems, but peel-and-bound can be easily applied to other optimization problems. However, some existing MDD based methods conflict with peel-and-bound. For example, some MDD algorithms use a dynamic variable order [25], such that the variables the layers on $\overline{M}$ are mapped to in one iteration of branch-and-bound, are different in the next. Peel-and-bound as it is presented in this paper cannot be paired with a dynamic variable order. Furthermore, the method in this paper is specific to decision diagrams generated using separation. We believe the method can be extended to decision diagrams that use a merge operator, but it has not been shown here.

Memory limitations present a problem for peel-and-bound in theory, but not in practice. Each open diagram remains in the queue, and thus must be stored in memory. However, this problem can be handled in many ways; two are given here. A dynamic method of handling the problem is to start targeting large diagrams with bounds close to $z_{opt}$ as memory limitations start to become a problem. Such diagrams can usually be closed quickly, and subsequently removed from memory, freeing up space for the algorithm to continue. Alternatively, the diagrams with bounds closest to $z_{opt}$ can be deleted in favor of storing just the root node, then when they need to be processed, initial diagrams are generated for those once again. This method essentially falls back to branch-and-bound until memory limitations cease to be a problem. Additional approaches for working with memory limitations, and evidence that the problem can be handled efficiently, are presented in Perez and Régin (2018) [26].

This implementation incorporates the rough relaxed bounding method proposed by Gillard et al. [13]. Rough relaxed bounding was used to trim the domain of each node during construction of the restricted DDs, and was also added as a check to the filter function in Algorithm 1. When the initial model is created, a map is also created from each node $u$, to a list of the other nodes sorted by their distance from $u$. The rough relaxed bound $rrb(a)$ of an arc $a_{fg}$ was calculated as follows. For each node $u$ that has not necessarily been visited ($u\notin All_{g}^{\downarrow}$), look up the shortest distance from that node to a different node that has also not been visited. Then, sort the resulting list, and repeatedly remove the largest value until the list has a length equal to the number of remaining decisions. The sum of the values in the list, plus the value of the shortest path from $r$ to the end of $a$, is the rough relaxed bound of $a$. If $rrb(a)$ is worse than the best known solution, the arc is removed.

The sequence ordering problem can be considered as an asymmetric travelling salesperson problem with precedence constraints. The objective is to find a minimum cost path that visits each of the $n$ elements exactly once, and respects the precedence constraints. The method used for generating relaxed DDs requires creating a heuristic ordering of all possible arc assignments by importance. The arc values in this case are representative of the $n$ elements in the path. The ordering used was generated by sorting the $n$ elements, first by their average distance from the other elements, and then by the number of elements each element must precede. The resulting order places a higher importance on elements that are far away from other elements and must precede many other elements.

The branch-and-bound algorithm processes nodes in an order designed to try and improve the existing relaxed bound at each iteration. When a node $u$ is added to the BnB queue, it is assigned a value equal to the value of the shortest path from the root $r$ to the terminal $t$, that passes through $u$. The best known relaxed bound on the problem is the smallest value of a node in the queue, and that node is always chosen to be processed. Peel-and-bound is implemented with the same goal of improving bounds at each iteration. However, PnB stores diagrams, not nodes. Let the value of a diagram be the value of the shortest path to the terminal. At each iteration of peel-and-bound, the diagram with the lowest value is selected, and then a node is chosen from that diagram to induce the peel process. All of the experiments here used a process where the selected node is the first node in the shortest path from $r$ to $t$ with a child node that is not exact (the last exact node). Testing was done to determine whether using the last exact node or the frontier node would perform better for the problem being considered, but there was not a significant difference between the two during any of the tests. Several of the benchmark problems were run using various decision diagram widths, and the last exact node was chosen because it sometimes showed a very slight improvement over the frontier node. While it is likely that this choice makes a difference on some problems, it does not matter for the SOP.

The experiments were performed on a computer equipped with an AMD Rome 7532 at 2.40 GHz with 64Gb RAM. The solver was tested using DD widths of $64,128$, and $256$ on the $41$ SOP problems available in TSPLIB [28]. For comparisons between PnB and BnB, a timestamp, new bounds, and the length of the remaining queue were recorded each time the bounds on a problem were improved. Another experiment was performed to test the scalability of PnB at width $2048$, for which only the final bounds were recorded. Execution time was limited to $3,600$ seconds.

The smallest DD width tested for both methods was $64$, and the largest DD width tested was $256$. Figure 5 has summary statistics for those widths as the percentage improvement demonstrated by PnB. A positive percentage always indicates that PnB performed better than BnB in that category, while a negative percentage indicates that BnB performed better. Figure 7 shows performance profiles for all of the experiments. Figure 6 contains summary statistics comparing PnB at width $256$ to PnB at width $2048$, where a positive percentage always indicates that the width of $2048$ performed better.

As shown in Figure 5, peel-and-bound vastly outperforms branch-and-bound in these experiments. The average and median improvements from using peel-and-bound at both widths are significant in terms of the relaxed bound, the remaining optimality gap, and the number of nodes that still need to be processed. The best solution found by the end of the runtime also tends to be slightly better with peel-and-bound, but the found solutions are often so close to the real optimal solutions that there is little room for improvement. At both widths, six of the problems were solved to optimality. BnB was faster in only one of those cases, and in that case the difference was $.04$ seconds. The median time for PnB to close in these cases was $191\%$ faster at a width of 64, and $580\%$ faster at a width of $256$. The relaxed bound produced by PnB at a width of $64$ was better for $28$ of the remaining $35$ problems, and at a width of $256$ was better for $34$ of the remaining $35$ problems. The optimality gap was similarly better for peel-and-bound on every problem except the ones where branch-and-bound found a better relaxed bound. However, of the problems where branch-and-bound had a better optimality gap, the improvement was less than $1\%$ for all but one problem. Figure 7 reinforces that even though there are some instances where a specific branch-and-bound setting slightly outperforms a specific peel-and-bound setting, the gap in those cases is small relative to the general gap between all peel-and-bound settings and all branch-and-bound settings.

As shown in Figure 6, increasing the width to $2048$ from $256$ led to an $19.5\%$ average improvement ($16.3\%$ median improvement) in the relaxed bound. Figure 7 shows that the performance of peel-and-bound nearly uniformly increases with the maximum allowable width. Similar to the difference between branch-and-bound and peel-and-bound, some specific instances see a small out-performance of the peel-and-bound running at a smaller width, but the gap is small relative to the usual gap between the $2048$-width experiment and the rest of the experiments. Additionally, Figure 7 shows that peel$\_2048$ solved $50\%$ of instances to within a $42\%$ optimality gap, peel$\_64$ solved $50\%$ of instances to within a $67\%$ optimality gap, and the best performing branch and bound (bnb$\_64$) solved $50\%$ of instances to within only a $79\%$ optimality gap. The overall performance of peel-and-bound improves as more problems are considered, especially as the maximum allowable width for the decision diagrams is increased.

The selected graphs shown in Figure 8 are representative of the two main types of behavior observed over the problem set. On problems where the underlying relaxation method works well, the relaxed bound moves quickly towards convergence with the best found solution. On problems where the underlying relaxation does not work well, both algorithms slowly improve the relaxed bound, but PnB starts stronger as it can use exact arc values, and it maintains the advantage throughout. It is clear from the time-series data that to be competitive with cutting-edge solvers, peel-and-bound must be combined with other constraint programming propagators. However, it is also clear that peel-and-bound can have a significant edge over a propagator that generates the required decision diagrams from scratch at each iteration.