mahf_tsplib/
lib.rs

1//! This crate allows easy access to instances of the traveling salesman problem taken from tsplib.
2
3use anyhow::{anyhow, Result};
4use include_dir::{include_dir, Dir};
5use mahf::{
6    problems::{ObjectiveFunction, Problem, VectorProblem},
7    SingleObjective,
8};
9use tspf::WeightKind;
10
11mod instances;
12mod opt;
13
14pub use instances::Instances;
15
16type Edge = (usize, usize);
17pub type Node = usize;
18pub type Route = Vec<Node>;
19
20static FILES: Dir = include_dir!("$CARGO_MANIFEST_DIR/src/tsplib");
21
22/// Represents the (global) optimum of the search space.
23#[derive(Debug, Clone, serde::Serialize)]
24pub struct TspOptimum {
25    pub objective: SingleObjective,
26    pub solution: Option<Route>,
27}
28
29/// Represents an instance of the symmetric travelling salesman problem.
30#[derive(serde::Serialize)]
31pub struct Tsp {
32    best_solution: Option<TspOptimum>,
33    #[serde(skip)]
34    inner: tspf::Tsp,
35}
36
37impl Tsp {
38    fn evaluate_solution(&self, solution: &Route) -> SingleObjective {
39        solution
40            .iter()
41            .copied()
42            .zip(solution.iter().copied().skip(1))
43            .map(|edge| self.distance(edge))
44            .sum::<f64>()
45            .try_into()
46            .unwrap()
47    }
48}
49
50impl From<Instances> for Tsp {
51    fn from(value: Instances) -> Self {
52        value.load()
53    }
54}
55
56impl Tsp {
57    /// Returns the instance name.
58    pub fn name(&self) -> &str {
59        self.inner.name()
60    }
61
62    /// Returns the best known solution, if it exists.
63    pub fn best_solution(&self) -> Option<&TspOptimum> {
64        self.best_solution.as_ref()
65    }
66
67    /// Returns the best known fitness value, if it exists.
68    pub fn best_fitness(&self) -> Option<f64> {
69        self.best_solution.as_ref().map(|o| o.objective.value())
70    }
71
72    /// Returns the weight/distance of the given edge.
73    pub fn distance(&self, edge: Edge) -> f64 {
74        let (a, b) = edge;
75
76        // TODO: this seems like a bug in tspf
77        if self.inner.weight_kind() == WeightKind::Explicit {
78            self.inner.weight(a, b)
79        } else {
80            self.inner.weight(a + 1, b + 1)
81        }
82    }
83
84    /// Greedily constructs a Route, always taking the shortest edge.
85    pub fn greedy_route(&self) -> Route {
86        let mut route = Vec::with_capacity(self.inner.dim());
87        let mut remaining = (1..self.inner.dim()).collect::<Vec<usize>>();
88        route.push(0);
89        while !remaining.is_empty() {
90            let last = *route.last().unwrap();
91            let next_index = remaining
92                .iter()
93                .enumerate()
94                .min_by_key(|(_, &r)| SingleObjective::try_from(self.distance((last, r))).unwrap())
95                .unwrap()
96                .0;
97            let next = remaining.remove(next_index);
98            route.push(next);
99        }
100        route
101    }
102
103    /// This method constructs a TSP instance from a string representation (`data`) and an optional solution (`opt`).
104    /// There is no good reason to call it directly, just use [Instances::try_load()] instead.
105    pub fn try_parse(data: &str, opt: Option<&str>) -> Result<Self> {
106        let tsp =
107            tspf::TspBuilder::parse_str(data).map_err(|err| anyhow!("parsing failed: {}", err))?;
108
109        let mut instance = Tsp {
110            best_solution: None,
111            inner: tsp,
112        };
113
114        if let Some(opt) = opt {
115            instance.best_solution = Some(opt::parse_opt_file(&instance, opt));
116        }
117
118        Ok(instance)
119    }
120}
121
122impl Problem for Tsp {
123    type Encoding = Route;
124    type Objective = SingleObjective;
125
126    fn name(&self) -> &str {
127        "Tsp"
128    }
129}
130
131impl ObjectiveFunction for Tsp {
132    fn objective(&self, solution: &Self::Encoding) -> Self::Objective {
133        self.evaluate_solution(solution)
134    }
135}
136
137impl VectorProblem for Tsp {
138    type Element = usize;
139
140    fn dimension(&self) -> usize {
141        self.inner.dim()
142    }
143}
mahf_tsplib/lib.rs

mahf_tsplib/
lib.rs
