rpid/
lib.rs

1//! Rust Programmable Interface for Domain-Independent Dynamic Programming (RPID)
2//!
3//! With RPID, you can formulate dynamic programming by implementing traits and
4//! solve it by calling a solver.
5//! You need to implement the [Dp] trait to define a dynamic programming model,
6//! and a solver may require the [Dominance] and [Bound] traits to enable dominance checking and pruning with bounds.
7//!
8//! ## Example
9//!
10//! Solving the traveling salesperson problem (TSP) with the CABS solver.
11//!
12//! ```
13//! use fixedbitset::FixedBitSet;
14//! use rpid::prelude::*;
15//! use rpid::solvers;
16//!
17//! struct Tsp {
18//!     c: Vec<Vec<i32>>,
19//! }
20//!
21//! struct TspState {
22//!     unvisited: FixedBitSet,
23//!     current: usize,
24//! }
25//!
26//! impl Dp for Tsp {
27//!     type State = TspState;
28//!     type CostType = i32;
29//!     type Label = usize;
30//!
31//!     fn get_target(&self) -> Self::State {
32//!         let mut unvisited = FixedBitSet::with_capacity(self.c.len());
33//!         unvisited.insert_range(1..);
34//!
35//!         TspState {
36//!             unvisited,
37//!             current: 0,
38//!         }
39//!     }
40//!
41//!     fn get_successors(
42//!         &self,
43//!         state: &Self::State,
44//!     ) -> impl IntoIterator<Item = (Self::State, Self::CostType, Self::Label)> {
45//!         state.unvisited.ones().map(|next| {
46//!             let mut unvisited = state.unvisited.clone();
47//!             unvisited.remove(next);
48//!
49//!             let successor = TspState {
50//!                 unvisited,
51//!                 current: next,
52//!             };
53//!             let weight = self.c[state.current][next];
54//!
55//!             (successor, weight, next)
56//!         })
57//!     }
58//!
59//!     fn get_base_cost(&self, state: &Self::State) -> Option<Self::CostType> {
60//!         if state.unvisited.is_clear() {
61//!             Some(self.c[state.current][0])
62//!         } else {
63//!             None
64//!         }
65//!     }
66//! }
67//!
68//! impl Dominance for Tsp {
69//!     type State = TspState;
70//!     type Key = (FixedBitSet, usize);
71//!
72//!     fn get_key(&self, state: &Self::State) -> Self::Key {
73//!         (state.unvisited.clone(), state.current)
74//!     }
75//! }
76//!
77//! impl Bound for Tsp {
78//!     type State = TspState;
79//!     type CostType = i32;
80//!
81//!     fn get_dual_bound(&self, _: &Self::State) -> Option<Self::CostType> {
82//!         Some(0)
83//!     }
84//! }
85//!
86//! let tsp = Tsp { c: vec![vec![0, 1, 2], vec![1, 0, 3], vec![2, 3, 0]] };
87//! let mut solver
88//!     = solvers::create_cabs(tsp, SearchParameters::default(), CabsParameters::default());
89//! let solution = solver.search();
90//! assert_eq!(solution.cost, Some(6));
91//! assert_eq!(solution.transitions, vec![1, 2]);
92//! assert!(solution.is_optimal);
93//! assert!(!solution.is_infeasible);
94//! assert_eq!(solution.best_bound, Some(6));
95//! ```
96//!
97//! For more examples, see <https://github.com/Kurorororo/didp-rust-models>.
98//!
99//! ## References
100//!
101//! Ryo Kuroiwa and J. Christopher Beck. RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming.
102//! In *31st International Conference on Principles and Practice of Constraint Programming (CP 2025)*,
103//! volume 340 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:21.
104//! Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
105//! [doi:10.4230/LIPIcs.CP.2025.23](https://doi.org/10.4230/LIPIcs.CP.2025.23)
106
107pub mod algorithms;
108mod dp;
109pub mod io;
110pub mod solvers;
111pub mod timer;
112
113pub use dp::{Bound, BoundMut, Dominance, Dp, DpMut, OptimizationMode};
114pub use solvers::Solution;
115
116pub mod prelude {
117    //! Prelude to import commonly used items.
118    pub use super::solvers::{CabsParameters, Search, SearchParameters};
119    pub use super::{Bound, Dominance, Dp, OptimizationMode, Solution};
120}
rpid/lib.rs

rpid/
lib.rs
