problemreductions/models/graph/
minimum_sum_multicenter.rs

1//! Min-Sum Multicenter (p-median) problem implementation.
2//!
3//! The p-median problem asks for K facility locations (centers) on a graph
4//! that minimize the total weighted distance from all vertices to their nearest center.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::{Min, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumSumMulticenter",
16        display_name: "Minimum Sum Multicenter",
17        aliases: &["pmedian"],
18        dimensions: &[
19            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
20            VariantDimension::new("weight", "i32", &["i32"]),
21        ],
22        module_path: module_path!(),
23        description: "Find K centers minimizing total weighted distance (p-median problem)",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
26            FieldInfo { name: "vertex_weights", type_name: "Vec<W>", description: "Vertex weights w: V -> R" },
27            FieldInfo { name: "edge_lengths", type_name: "Vec<W>", description: "Edge lengths l: E -> R" },
28            FieldInfo { name: "k", type_name: "usize", description: "Number of centers to place" },
29        ],
30    }
31}
32
33/// The Min-Sum Multicenter (p-median) problem.
34///
35/// Given a graph G = (V, E) with vertex weights w(v) and edge lengths l(e),
36/// find a subset P ⊆ V of K vertices (centers) that minimizes the total
37/// weighted distance Σ_{v ∈ V} w(v) · d(v, P), where d(v, P) is the
38/// shortest-path distance from v to the nearest center in P.
39///
40/// # Type Parameters
41///
42/// * `G` - The graph type (e.g., `SimpleGraph`)
43/// * `W` - The weight/length type (e.g., `i32`, `One`)
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::graph::MinimumSumMulticenter;
49/// use problemreductions::topology::SimpleGraph;
50/// use problemreductions::{Problem, Solver, BruteForce};
51///
52/// // Path graph: 0-1-2, unit weights and lengths, K=1
53/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
54/// let problem = MinimumSumMulticenter::new(graph, vec![1i32; 3], vec![1i32; 2], 1);
55///
56/// let solver = BruteForce::new();
57/// let solution = solver.find_witness(&problem).unwrap();
58/// // Center at vertex 1 gives total distance 0+1+1 = 2 (optimal)
59/// assert_eq!(solution, vec![0, 1, 0]);
60/// ```
61#[derive(Debug, Clone, Serialize, Deserialize)]
62pub struct MinimumSumMulticenter<G, W> {
63    /// The underlying graph.
64    graph: G,
65    /// Non-negative weight for each vertex.
66    vertex_weights: Vec<W>,
67    /// Non-negative length for each edge (in edge index order).
68    edge_lengths: Vec<W>,
69    /// Number of centers to place.
70    k: usize,
71}
72
73impl<G: Graph, W: Clone + Default> MinimumSumMulticenter<G, W> {
74    /// Create a MinimumSumMulticenter problem.
75    ///
76    /// # Panics
77    /// - If `vertex_weights.len() != graph.num_vertices()`
78    /// - If `edge_lengths.len() != graph.num_edges()`
79    /// - If `k == 0` or `k > graph.num_vertices()`
80    pub fn new(graph: G, vertex_weights: Vec<W>, edge_lengths: Vec<W>, k: usize) -> Self {
81        assert_eq!(
82            vertex_weights.len(),
83            graph.num_vertices(),
84            "vertex_weights length must match num_vertices"
85        );
86        assert_eq!(
87            edge_lengths.len(),
88            graph.num_edges(),
89            "edge_lengths length must match num_edges"
90        );
91        assert!(k > 0, "k must be positive");
92        assert!(k <= graph.num_vertices(), "k must not exceed num_vertices");
93        Self {
94            graph,
95            vertex_weights,
96            edge_lengths,
97            k,
98        }
99    }
100
101    /// Get a reference to the underlying graph.
102    pub fn graph(&self) -> &G {
103        &self.graph
104    }
105
106    /// Get a reference to the vertex weights.
107    pub fn vertex_weights(&self) -> &[W] {
108        &self.vertex_weights
109    }
110
111    /// Get a reference to the edge lengths.
112    pub fn edge_lengths(&self) -> &[W] {
113        &self.edge_lengths
114    }
115
116    /// Get the number of centers K.
117    pub fn k(&self) -> usize {
118        self.k
119    }
120}
121
122impl<G: Graph, W: WeightElement> MinimumSumMulticenter<G, W> {
123    /// Get the number of vertices in the underlying graph.
124    pub fn num_vertices(&self) -> usize {
125        self.graph().num_vertices()
126    }
127
128    /// Get the number of edges in the underlying graph.
129    pub fn num_edges(&self) -> usize {
130        self.graph().num_edges()
131    }
132
133    /// Get the number of centers K.
134    pub fn num_centers(&self) -> usize {
135        self.k
136    }
137
138    /// Compute shortest distances from each vertex to the nearest center.
139    ///
140    /// Uses multi-source Dijkstra with linear scan: initializes all centers
141    /// at distance 0 and greedily relaxes edges by increasing distance.
142    /// Correct because all edge lengths are non-negative.
143    ///
144    /// Returns `None` if any vertex is unreachable from all centers.
145    fn shortest_distances(&self, config: &[usize]) -> Option<Vec<W::Sum>> {
146        let n = self.graph.num_vertices();
147        let edges = self.graph.edges();
148
149        let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n];
150        for (idx, &(u, v)) in edges.iter().enumerate() {
151            let len = self.edge_lengths[idx].to_sum();
152            adj[u].push((v, len.clone()));
153            adj[v].push((u, len));
154        }
155
156        // Multi-source Dijkstra with linear scan (works with PartialOrd)
157        let mut dist: Vec<Option<W::Sum>> = vec![None; n];
158        let mut visited = vec![false; n];
159
160        // Initialize centers
161        for (v, &selected) in config.iter().enumerate() {
162            if selected == 1 {
163                dist[v] = Some(W::Sum::zero());
164            }
165        }
166
167        for _ in 0..n {
168            // Find unvisited vertex with smallest distance
169            let mut u = None;
170            for v in 0..n {
171                if visited[v] {
172                    continue;
173                }
174                if let Some(ref dv) = dist[v] {
175                    match u {
176                        None => u = Some(v),
177                        Some(prev) => {
178                            if *dv < dist[prev].clone().unwrap() {
179                                u = Some(v);
180                            }
181                        }
182                    }
183                }
184            }
185            let u = match u {
186                Some(v) => v,
187                None => break, // remaining vertices are unreachable
188            };
189            visited[u] = true;
190
191            let du = dist[u].clone().unwrap();
192            for &(next, ref len) in &adj[u] {
193                if visited[next] {
194                    continue;
195                }
196                let new_dist = du.clone() + len.clone();
197                let update = match &dist[next] {
198                    None => true,
199                    Some(d) => new_dist < *d,
200                };
201                if update {
202                    dist[next] = Some(new_dist);
203                }
204            }
205        }
206
207        dist.into_iter().collect()
208    }
209}
210
211impl<G, W> Problem for MinimumSumMulticenter<G, W>
212where
213    G: Graph + crate::variant::VariantParam,
214    W: WeightElement + crate::variant::VariantParam,
215{
216    const NAME: &'static str = "MinimumSumMulticenter";
217    type Value = Min<W::Sum>;
218
219    fn variant() -> Vec<(&'static str, &'static str)> {
220        crate::variant_params![G, W]
221    }
222
223    fn dims(&self) -> Vec<usize> {
224        vec![2; self.graph.num_vertices()]
225    }
226
227    fn evaluate(&self, config: &[usize]) -> Min<W::Sum> {
228        // Check exactly K centers are selected
229        let num_selected: usize = config.iter().sum();
230        if num_selected != self.k {
231            return Min(None);
232        }
233
234        // Compute shortest distances to nearest center
235        let distances = match self.shortest_distances(config) {
236            Some(d) => d,
237            None => return Min(None),
238        };
239
240        // Compute total weighted distance: Σ w(v) * d(v)
241        let mut total = W::Sum::zero();
242        for (v, dist) in distances.iter().enumerate() {
243            total += self.vertex_weights[v].to_sum() * dist.clone();
244        }
245
246        Min(Some(total))
247    }
248}
249
250crate::declare_variants! {
251    default MinimumSumMulticenter<SimpleGraph, i32> => "2^num_vertices",
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "minimum_sum_multicenter_simplegraph_i32",
258        instance: Box::new(MinimumSumMulticenter::new(
259            SimpleGraph::new(
260                7,
261                vec![
262                    (0, 1),
263                    (1, 2),
264                    (2, 3),
265                    (3, 4),
266                    (4, 5),
267                    (5, 6),
268                    (0, 6),
269                    (2, 5),
270                ],
271            ),
272            vec![1i32; 7],
273            vec![1i32; 8],
274            2,
275        )),
276        optimal_config: vec![0, 0, 1, 0, 0, 1, 0],
277        optimal_value: serde_json::json!(6),
278    }]
279}
280
281#[cfg(test)]
282#[path = "../../unit_tests/models/graph/minimum_sum_multicenter.rs"]
283mod tests;
problemreductions/models/graph/minimum_sum_multicenter.rs

problemreductions/models/graph/
minimum_sum_multicenter.rs
