problemreductions/models/graph/
bottleneck_traveling_salesman.rs

1//! Bottleneck Traveling Salesman problem implementation.
2//!
3//! The Bottleneck Traveling Salesman problem asks for a Hamiltonian cycle
4//! minimizing the maximum selected edge weight.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "BottleneckTravelingSalesman",
15        display_name: "Bottleneck Traveling Salesman",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Graph,
19        module_path: module_path!(),
20        description: "Find a Hamiltonian cycle minimizing the maximum selected edge weight",
21        fields: BottleneckTravelingSalesmanCreateSpec::FIELDS,
22    }
23}
24
25/// The Bottleneck Traveling Salesman problem on a simple weighted graph.
26#[derive(Debug, Clone, Serialize, Deserialize)]
27pub struct BottleneckTravelingSalesman {
28    graph: SimpleGraph,
29    edge_weights: Vec<i64>,
30}
31
32#[derive(Debug, Deserialize, crate::CreateSpec)]
33struct BottleneckTravelingSalesmanCreateSpec {
34    #[create(codec = "edge-list")]
35    graph: Vec<(usize, usize)>,
36    num_vertices: Option<usize>,
37    #[create(codec = "comma-separated")]
38    edge_weights: Option<Vec<i64>>,
39}
40
41impl TryFrom<BottleneckTravelingSalesmanCreateSpec> for BottleneckTravelingSalesman {
42    type Error = crate::registry::ConstructionError;
43
44    fn try_from(spec: BottleneckTravelingSalesmanCreateSpec) -> Result<Self, Self::Error> {
45        let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
46        let edge_weights = spec
47            .edge_weights
48            .unwrap_or_else(|| vec![1; graph.num_edges()]);
49        if edge_weights.len() != graph.num_edges() {
50            return Err(format!(
51                "edge_weights has length {}, expected {}",
52                edge_weights.len(),
53                graph.num_edges()
54            )
55            .into());
56        }
57        Ok(Self::new(graph, edge_weights))
58    }
59}
60
61fn simple_graph_from_create(
62    edges: Vec<(usize, usize)>,
63    num_vertices: Option<usize>,
64) -> Result<SimpleGraph, crate::registry::ConstructionError> {
65    if edges.is_empty() && num_vertices.is_none() {
66        return Err("num_vertices is required for an empty graph"
67            .to_string()
68            .into());
69    }
70    for (index, &(u, v)) in edges.iter().enumerate() {
71        if u == v {
72            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
73        }
74    }
75    let inferred = edges
76        .iter()
77        .flat_map(|&(u, v)| [u, v])
78        .max()
79        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
80        .transpose()?
81        .unwrap_or(0);
82    let num_vertices = num_vertices.unwrap_or(inferred);
83    if num_vertices < inferred {
84        return Err(format!(
85            "num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}"
86        )
87        .into());
88    }
89    Ok(SimpleGraph::new(num_vertices, edges))
90}
91
92impl BottleneckTravelingSalesman {
93    /// Create a BottleneckTravelingSalesman problem from a graph with edge weights.
94    pub fn new(graph: SimpleGraph, edge_weights: Vec<i64>) -> Self {
95        assert_eq!(
96            edge_weights.len(),
97            graph.num_edges(),
98            "edge_weights length must match num_edges"
99        );
100        Self {
101            graph,
102            edge_weights,
103        }
104    }
105
106    /// Get a reference to the underlying graph.
107    pub fn graph(&self) -> &SimpleGraph {
108        &self.graph
109    }
110
111    /// Get the weights for the problem.
112    pub fn weights(&self) -> Vec<i64> {
113        self.edge_weights.clone()
114    }
115
116    /// Set new weights for the problem.
117    pub fn set_weights(&mut self, weights: Vec<i64>) {
118        assert_eq!(weights.len(), self.graph.num_edges());
119        self.edge_weights = weights;
120    }
121
122    /// Get all edges with their weights.
123    pub fn edges(&self) -> Vec<(usize, usize, i64)> {
124        self.graph
125            .edges()
126            .into_iter()
127            .zip(self.edge_weights.iter().copied())
128            .map(|((u, v), w)| (u, v, w))
129            .collect()
130    }
131
132    /// Get the number of vertices in the underlying graph.
133    pub fn num_vertices(&self) -> usize {
134        self.graph.num_vertices()
135    }
136
137    /// Get the number of edges in the underlying graph.
138    pub fn num_edges(&self) -> usize {
139        self.graph.num_edges()
140    }
141
142    /// This model is always weighted.
143    pub fn is_weighted(&self) -> bool {
144        true
145    }
146
147    /// Check if a configuration is a valid Hamiltonian cycle.
148    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
149        if config.len() != self.graph.num_edges() {
150            return false;
151        }
152        super::traveling_salesman::is_hamiltonian_cycle(&self.graph, config)
153    }
154}
155
156impl Problem for BottleneckTravelingSalesman {
157    const NAME: &'static str = "BottleneckTravelingSalesman";
158    type Solution = Vec<bool>;
159    type Value = Min<i64>;
160
161    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
162
163    fn variant() -> Vec<(&'static str, &'static str)> {
164        crate::variant_params![]
165    }
166
167    fn evaluate(
168        &self,
169        config: &Self::Solution,
170    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
171        Ok({
172            if config.len() != self.graph.num_edges() {
173                return Err(crate::traits::EvaluationError::InvalidConfiguration(
174                    "edge-selection length does not match the graph".into(),
175                ));
176            }
177
178            if !super::traveling_salesman::is_hamiltonian_cycle(&self.graph, config) {
179                return Ok(Min(None));
180            }
181
182            let bottleneck = config
183                .iter()
184                .zip(self.edge_weights.iter())
185                .filter_map(|(&selected, &weight)| selected.then_some(weight))
186                .max()
187                .expect("valid Hamiltonian cycle selects at least one edge");
188
189            Min(Some(bottleneck))
190        })
191    }
192}
193
194impl crate::solvers::BruteForceProblem for BottleneckTravelingSalesman {
195    fn dimensions(&self) -> Vec<usize> {
196        vec![2; self.graph.num_edges()]
197    }
198}
199
200#[cfg(feature = "example-db")]
201pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
202    vec![crate::example_db::specs::ModelExampleSpec {
203        id: "bottleneck_traveling_salesman",
204        instance: Box::new(BottleneckTravelingSalesman::new(
205            SimpleGraph::new(
206                5,
207                vec![
208                    (0, 1),
209                    (0, 2),
210                    (0, 3),
211                    (0, 4),
212                    (1, 2),
213                    (1, 3),
214                    (1, 4),
215                    (2, 3),
216                    (2, 4),
217                    (3, 4),
218                ],
219            ),
220            vec![5, 4, 4, 5, 4, 1, 2, 1, 5, 4],
221        )),
222        optimal_config: serde_json::json!([
223            false, true, true, false, true, false, true, false, false, true
224        ]),
225        optimal_value: serde_json::json!(4),
226    }]
227}
228
229crate::impl_random_generate!(
230    BottleneckTravelingSalesman,
231    crate::random::SimpleGraphRandomSpec,
232    |spec| {
233        let graph = spec.graph()?;
234        let weights = vec![1; graph.num_edges()];
235        Ok(BottleneckTravelingSalesman::new(graph, weights))
236    }
237);
238
239crate::declare_variants! {
240    default BottleneckTravelingSalesman => "num_vertices^2 * 2^num_vertices" create BottleneckTravelingSalesmanCreateSpec random,
241}
242
243crate::register_brute_force! {
244    BottleneckTravelingSalesman decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
245}
246
247#[cfg(test)]
248#[path = "../../unit_tests/models/graph/bottleneck_traveling_salesman.rs"]
249mod tests;
problemreductions/models/graph/bottleneck_traveling_salesman.rs

problemreductions/models/graph/
bottleneck_traveling_salesman.rs
