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

problemreductions/models/graph/
bottleneck_traveling_salesman.rs
