RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming

Domain-independent dynamic programming (DIDP) is a model-based paradigm where a combinatorial optimization problem is formulated as a declarative DP model and is solved by a general-purpose solver [14, 17]. The model is defined in Dynamic Programming Description Language (DyPDL), which is explicitly designed for combinatorial optimization by allowing a user to incorporate redundant information via state constraints, state dominance, and a dual bound function.

A state constraint is a condition that must be satisfied by all states. In TSPTW, since we need to visit all customers, a state does not lead to a solution if one of the customers cannot be reached by its deadline. Let $c_{ij}^{\ast }$ be the shortest travel time from customer $i$ to $j$, which can be precomputed from the travel costs. A state $(U,i,t)$ must satisfy $t+c_{ij}^{\ast }\le b_j$ for each customer $j\in U$. Using the value function $V$,

This constraint is redundant, i.e., implied by Equation (2), but can be helpful for a solver.¹¹1In general, a state constraint is not necessarily redundant.

A state $S$ dominates another state $S^{\prime }$ if the value of $S$ is equal to or better than that of $S^{\prime }$, i.e., $V(S)\le V(S^{\prime })$ in minimization. In DyPDL, a user can explicitly define a sufficient condition for state dominance. In the TSPTW example, $(U,i,t)$ is at least as good as $(U,i,t^{\prime })$ if $t\le t^{\prime }$, i.e.,

A dual bound function $\eta$ defines a lower/upper bound on $V(S)$ in minimization/maximization, i.e., $V(S)\ge \eta (S)$ for minimization. In TSPTW, the travel cost to visit customer $j$ can be underestimated by $c_j^{\text{to}}={\min }_{k\in N\setminus \{j\}}{c}_{kj}$. Given a state $(U,i,t)$, the sum of $c_j^{\text{to}}$ over $j\in U\cup \{0\}$ is a dual bound function. Similarly, the travel cost from $j$ to a customer is underestimated by $c_j^{\text{from}}={\min }_{k\in N\setminus \{j\}}{c}_{jk}$. In other words,

Hooker [11] proposed that a DP formulation can be represented as a decision diagram (DD), a data structure based on a directed graph, and that a solution can be extracted from such a DD. Based on this observation, Bergman et al. [2] proposed a branch-and-bound algorithm to solve DPs based on DDs. Since constructing an exact DD, which fully represents the DP formulation, is computationally expensive, the algorithm repeatedly constructs restricted and relaxed DDs, which are computationally cheaper and provide bounds on the optimal objective value. To construct a relaxed DD, a function called a merge operator is required, which maps two states to a single state. DD-based branch-and-bound can also exploit state dominance and a dual bound function when they are defined [3, 7, 18].

We discuss the design of RPID. First, we argue the advantage of RPID over didp-rs. Then, we highlight the differences between RPID and existing DD-based solvers.

With didp-rs, previous work [17] used DP models for eleven problem classes: TSPTW, the capacitated vehicle routing problem (CVRP), the multi-commodity pickup and delivery traveling salesperson problem (m-PDTSP), the orienteering problem with time windows (OPTW), the multi-dimensional knapsack problem (MDKP), bin packing, the simple assembly line balancing problem (SALBP-1), $1||\sum w_i{T}_i$, talent scheduling, the minimization of open stacks problem (MOSP), and graph-clear. DIDP solvers in didp-rs outperformed commercial CP and mixed-integer programming solvers in TSPTW, m-PDTSP, OPTW, SALBP-1, $1||\sum w_i{T}_i$, talent scheduling, MOSP, and graph-clear. The original models are available in YAML-DyPDL and DIDPPy in a public repository,⁶⁶6https://github.com/Kurorororo/didp-models and we reimplement them in RPID. As a baseline, we also reimplement these models in Rust using didp-rs 0.8.0: we define the DP models by writing expressions with the dypdl library and solve them using the dypdl-heuristic-search library in Rust. We call this baseline “didp-rs.”

We confirmed that the numbers of expanded states are the same in RPID and didp-rs for the same solver and the same problem instance. Thus, we compare the number of optimally solved instances and the average time to solve an instance in each problem class. As shown in Table 1, RPID dominates didp-rs: solving more instances than didp-rs in six problem classes with A* and eight with CABS and never failing to solve an instance solved by didp-rs. On average, RPID is faster than didp-rs in all problem classes and reduces the solving time by at least half in five classes with A* and eight with CABS. We also show the number of solved instances against time for TSPTW, m-PDTSP, and OPTW in Figure 2 and for other problem classes in Appendix B.

We present an instance-wise comparison of the solving time by RPID and didp-rs in Figure 1. In the majority of instances, RPID achieves a speedup of more than two times. For A*, RPID is slower in one SALBP-1 instance, where we observe that RPID proves optimality faster than didp-rs but takes more time for termination, including freeing allocated memory. For CABS, RPID is slower than didp-rs in 19 MOSP instances. This performance degradation seems to be due to the implementation of state variables. The DP model for MOSP has two set state variables, and each transition performs set operations on them. Both our RPID model and didp-rs use the same library, fixedbitset, to represent set state variables. However, while didp-rs 0.8.0 uses fixedbitset 0.4.2, our model uses 0.5.7 (the latest version as of writing). We observe that using 0.4.2 with our RPID model results in better performance than didp-rs. We suspect that the overhead of didp-rs is relatively low in MOSP, sometimes outweighed by the difference in the set variable implementation.

Table 1 and Figure 1 present large performance gains in bin packing and OPTW. In particular, RPID achieves more than 100 times speedup in some bin packing instances. In bin packing, we minimize the number of bins to pack a set of items $N$, where a bin has the capacity $c$, and each item $i\in N$ has the weight $w_i$. In the DP model, a state is represented by the remaining capacity of the current bin $r$ and the set of unpacked items $U$. Each transition packs an item $i\in U$ with $w_i\le r$ and reduces $r$ by $w_i$. If no such item exists, only one transition is applicable, which opens a new bin and packs an arbitrary item $i$, updating $r$ to $c-w_i$. In didp-rs, two transitions are defined for each item $i$, one to pack it in the current bin and another to pack it in a new bin. The latter has a precondition $j\notin U\vee w_j>r$ for each $j\in N$ to confirm that no item can be packed in the current bin, requiring $O(|N|)$ time to check in the worst case. Since there are $O(|N|)$ such transitions, identifying applicable transitions requires $O({|N|}^2)$ time. In RPID, we can avoid such computation by checking $\forall j\in U,w_j>r$ only once in the successor generator function, as presented in Appendix A.

For OPTW, the restrictions of the DyPDL syntax result in a large expression tree with less efficient execution than what can be done with Rust code. In the model, the dual bound function computes ${\sum }_{j\in U:{\varphi }_j}{c}_j$, where $U\subseteq N$ is a set state variable, ${\varphi }_j$ is a Boolean condition on $j$, and $c_j$ is a constant depending on $j$. To represent this computation, the current implementation takes the sum of expressions representing “$c_j$ if $j\in U\wedge {\varphi }_j$ and $0$ otherwise” for all $j\in N$, resulting in an expression tree with depth $O(|N|)$.

As we discussed in Section 3.1.1, a dual bound function based on the 1-tree weight can be used for the DP model of TSPTW. The DP models for CVRP and m-PDTSP are similar to that of TSPTW, and dual bound functions similar to Inequality (5) are used, so they can also be replaced with the 1-tree bound. We implement such DP models in RPID, using Kruskal’s algorithm to compute the MST weight, which requires sorting edges in the ascending order of the weights. In our implementation, sorting is performed in preprocessing, and Kruskal’s algorithm ignores edges connected to visited customers in a given state.

Since OPTW and MDKP can be considered generalizations of 0-1 knapsack, the Dantzig bound [4] can be used as a dual bound function. Due to restrictions of expressions in didp-rs, Kuroiwa and Beck [17] approximated the Dantzig bound in their DP models. In RPID, we implement DP models using the Dantzig bound as a dual bound function. We compare the new DP models with the original models (the ones used in Section 4.1) using A* and CABS in RPID, measuring the number of state expansions by each heuristic search algorithm to solve an instance optimally. Our heuristic search algorithms maintain the global dual bound, a lower/upper bound of the optimal objective value in minimization/maximization. We subtract the number of expansions after the global dual bound matches the optimal objective value from the total number of expansions. This metric is called “expansions before the last $f$-layer” and is conventionally used to compare different heuristic functions for A*.

As shown in Table 2, our dual bound functions reduce the number of expansions in all problem classes. In CVRP, m-PDTSP, OPTW, and MDKP, the number of optimally solved instances is increased, and the time to solve an instance is reduced by a factor of two to six. We also present the number of solved instances against time for TSPTW, m-PDTSP, and OPTW in Figure 2. The result shows that the flexibility of the RPID modeling can contribute to significant performance improvement. However, in TSPTW, the time to solve an instance is increased, and the number of instances solved optimally by CABS is decreased. One potential reason is the quadratic computational complexity of Kruskal’s algorithm on a complete graph compared to the linear complexity of the dual bound function in Inequality (5). While the expensive dual bound function pays off in CVRP and m-PDTSP, it does not in TSPTW, possibly because many states are already pruned by Equation (3).

As discussed in Section 3.1.3, the single successor generation function of RPID can be beneficial when the same information is required by multiple transitions. We evaluate the impact of this interface design using the DP model for $1||\sum w_i{T}_i$, presented in Equation (6). In our original implementation presented in Listing 4 and used in Section 4.1, the total processing time of already processed jobs, ${\sum }_{k\in S}{p}_k$, is computed once for all successor states. We consider two different implementations, “Separate”, where ${\sum }_{k\in S}{p}_k$ is separately computed each time a successor state is generated, and “StateCache”, where ${\sum }_{k\in S}{p}_k$ is stored as a state variable and increased by $p_j$ when $j$ is added to $S$.

We compare the three implementations in Table 3. With A*, Separate slightly increases the average time to solve an instance, and StateCache reaches the memory limit in three instances solved by Original and Separate, possibly due to increased memory usage per state. With CABS, both Separate and StateCache increase average solving time and solve fewer instances than Original due to the time limit. These results confirm that our interface design has a positive impact on performance.

We compare RPID, didp-rs, ddo, and CODD using the problem classes with which previous work compared CODD with didp-rs and ddo [18]: 0-1 knapsack, Golomb ruler, and the maximum independent set problem (MISP). For 0-1 knapsack and MISP, instances are retrieved from the CODD repository.⁷⁷7https://github.com/ldmbouge/CODD/tree/main/data For Golomb ruler, an instance is uniquely determined from a parameter $n$. While previous work compared heuristic search solvers and DD-based solvers [17, 18], the interface designs of the solvers are different; didp-rs uses expression trees and DD-based solvers use functions in the programming language in which they are implemented. With RPID, we conduct the first empirical evaluation comparing heuristic search solvers and DD-based solvers without such differences.

We use ddo 2.0.0 and the latest model implementations available in its repository at the time of writing.⁸⁸8https://github.com/xgillard/ddo/tree/3b39798874b66ac965a0ce915c6f21f562ebaa6e/ddo/examples Ddo requires a parameter called a width as input, and each model code defines a default width. In 0-1 knapsack, we use a width of 4 as it performs better than the default width of 2. In the other two problem classes, we use the default parameters, 10 for Golomb ruler and the width automatically decided based on a problem instance in MISP.

For CODD, from models in its repository,⁹⁹9https://github.com/ldmbouge/CODD/tree/main/examples we use knapsack2 for 0-1 knapsack, gruler_midlb for Golomb ruler, and misp5 for MISP,¹⁰¹⁰10They seem to be the best models according to authors’ description and our preliminary experiments. compiled with GCC 13.2.0. Similar to ddo, CODD also requires a width parameter as input. Following the previous work using the same instances [18], we use 64 for Golomb ruler and 128 for MISP. In 0-1 knapsack, we use the best width for each instance reported in the previous work [18].

For didp-rs and RPID, we implement models following the CODD models. For 0-1 knapsack, ddo, CODD, and RPID models use the Dantzig bound as a dual bound function. As mentioned earlier, the Dantzig bound is difficult to use with didp-rs, so we define a dual bound function similar to those used in the DP models for MDKP and OPTW, and we also evaluate a RPID model with such a dual bound function (No Dantzig).

Tables 4–6 present the results, omitting instances solved within 1 second by all solvers. There is no single winner: RPID with A* shows a clear advantage in 0-1 knapsack, CODD is the best in Golomb ruler, and ddo is almost always the best in MISP. While previous work reported that didp-rs with CABS fails to solve four 0-1 knapsack instances in their evaluation [18], it solves all but one in our evaluation. We suspect that previous work did not use any dual bound function with DIDP, following the model in the didp-rs repository.¹¹¹¹11https://github.com/domain-independent-dp/didp-rs/blob/main/didppy/examples/knapsack.ipynb In our evaluation, CODD reaches the 8GB memory limit in four instances of 0-1 knapsack. Given a larger memory limit, CODD solves all such instances in at most a few tens of seconds, but it is slower than DDO and RPID with the Dantzig bound. Further analysis of the performance difference between DIDP and DD-based solvers is left for future work.