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::{CreateSpec, 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", "i64", &["i64"]),
21        ],
22        category: crate::registry::ProblemCategory::Graph,
23        module_path: module_path!(),
24        description: "Find K centers minimizing total weighted distance (p-median problem)",
25        fields: MinimumSumMulticenterCreateSpec::FIELDS,
26    }
27}
28
29/// The Min-Sum Multicenter (p-median) problem.
30///
31/// Given a graph G = (V, E) with vertex weights w(v) and edge lengths l(e),
32/// find a subset P ⊆ V of K vertices (centers) that minimizes the total
33/// weighted distance Σ_{v ∈ V} w(v) · d(v, P), where d(v, P) is the
34/// shortest-path distance from v to the nearest center in P.
35///
36/// # Type Parameters
37///
38/// * `G` - The graph type (e.g., `SimpleGraph`)
39/// * `W` - The weight/length type (e.g., `i64`, `One`)
40///
41/// # Example
42///
43/// ```
44/// use problemreductions::models::graph::MinimumSumMulticenter;
45/// use problemreductions::topology::SimpleGraph;
46/// use problemreductions::{Problem, BruteForce};
47///
48/// // Path graph: 0-1-2, unit weights and lengths, K=1
49/// let graph = SimpleGraph::new(3, vec![(0, 1), (1, 2)]);
50/// let problem = MinimumSumMulticenter::new(graph, vec![1i64; 3], vec![1i64; 2], 1);
51///
52/// let solver = BruteForce::new();
53/// let solution = solver.solve(&problem).unwrap().unwrap();
54/// // Center at vertex 1 gives total distance 0+1+1 = 2 (optimal)
55/// assert_eq!(solution, vec![false, true, false]);
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58#[serde(try_from = "MinimumSumMulticenterData<G, W>")]
59#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
60pub struct MinimumSumMulticenter<G, W> {
61    /// The underlying graph.
62    graph: G,
63    /// Non-negative weight for each vertex.
64    vertex_weights: Vec<W>,
65    /// Non-negative length for each edge (in edge index order).
66    edge_lengths: Vec<W>,
67    /// Number of centers to place.
68    k: usize,
69}
70
71#[derive(Deserialize)]
72#[serde(bound(deserialize = "G: Graph + Deserialize<'de>, W: Clone + Default + Deserialize<'de>"))]
73struct MinimumSumMulticenterData<G, W> {
74    graph: G,
75    vertex_weights: Vec<W>,
76    edge_lengths: Vec<W>,
77    k: usize,
78}
79
80impl<G, W> TryFrom<MinimumSumMulticenterData<G, W>> for MinimumSumMulticenter<G, W>
81where
82    G: Graph,
83    W: Clone + Default,
84{
85    type Error = crate::registry::ConstructionError;
86
87    fn try_from(data: MinimumSumMulticenterData<G, W>) -> Result<Self, Self::Error> {
88        Self::try_new(data.graph, data.vertex_weights, data.edge_lengths, data.k)
89    }
90}
91
92#[derive(Debug, Deserialize, crate::CreateSpec)]
93struct MinimumSumMulticenterCreateSpec {
94    #[create(codec = "edge-list")]
95    graph: Vec<(usize, usize)>,
96    num_vertices: Option<usize>,
97    #[create(codec = "comma-separated")]
98    weights: Option<Vec<i64>>,
99    #[create(codec = "comma-separated")]
100    edge_weights: Option<Vec<i64>>,
101    k: usize,
102}
103
104#[derive(Debug, Deserialize, crate::CreateSpec)]
105struct MinimumSumMulticenterRandomSpec {
106    /// Number of graph vertices.
107    num_vertices: usize,
108    /// Independent edge probability (default: 0.5).
109    edge_prob: Option<f64>,
110    /// Seed for reproducible generation.
111    seed: Option<i64>,
112    /// Number of centers (default: max(1, num_vertices / 3)).
113    k: Option<usize>,
114}
115
116impl TryFrom<MinimumSumMulticenterCreateSpec> for MinimumSumMulticenter<SimpleGraph, i64> {
117    type Error = crate::registry::ConstructionError;
118
119    fn try_from(spec: MinimumSumMulticenterCreateSpec) -> Result<Self, Self::Error> {
120        let graph = simple_graph_from_create(spec.graph, spec.num_vertices)?;
121        let vertex_weights = spec
122            .weights
123            .unwrap_or_else(|| vec![1; graph.num_vertices()]);
124        let edge_lengths = spec
125            .edge_weights
126            .unwrap_or_else(|| vec![1; graph.num_edges()]);
127        Self::try_new(graph, vertex_weights, edge_lengths, spec.k)
128    }
129}
130
131fn simple_graph_from_create(
132    edges: Vec<(usize, usize)>,
133    num_vertices: Option<usize>,
134) -> Result<SimpleGraph, crate::registry::ConstructionError> {
135    if edges.is_empty() && num_vertices.is_none() {
136        return Err("num_vertices is required for an empty graph"
137            .to_string()
138            .into());
139    }
140    for (index, &(u, v)) in edges.iter().enumerate() {
141        if u == v {
142            return Err(format!("graph edge {index} is a self-loop at vertex {u}").into());
143        }
144    }
145    let inferred = edges
146        .iter()
147        .flat_map(|&(u, v)| [u, v])
148        .max()
149        .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
150        .transpose()?
151        .unwrap_or(0);
152    let num_vertices = num_vertices.unwrap_or(inferred);
153    if num_vertices < inferred {
154        return Err(format!("num_vertices {num_vertices} is too small for graph endpoints; need at least {inferred}").into());
155    }
156    Ok(SimpleGraph::new(num_vertices, edges))
157}
158
159impl<G: Graph, W: Clone + Default> MinimumSumMulticenter<G, W> {
160    /// Create a MinimumSumMulticenter problem.
161    ///
162    /// # Panics
163    /// - If `vertex_weights.len() != graph.num_vertices()`
164    /// - If `edge_lengths.len() != graph.num_edges()`
165    /// - If `k == 0` or `k > graph.num_vertices()`
166    pub fn new(graph: G, vertex_weights: Vec<W>, edge_lengths: Vec<W>, k: usize) -> Self {
167        Self::try_new(graph, vertex_weights, edge_lengths, k)
168            .unwrap_or_else(|error| panic!("{error}"))
169    }
170
171    fn try_new(
172        graph: G,
173        vertex_weights: Vec<W>,
174        edge_lengths: Vec<W>,
175        k: usize,
176    ) -> Result<Self, crate::registry::ConstructionError> {
177        if vertex_weights.len() != graph.num_vertices() {
178            return Err(crate::registry::ConstructionError::length_mismatch(
179                "vertex_weights",
180                vertex_weights.len(),
181                graph.num_vertices(),
182            ));
183        }
184        if edge_lengths.len() != graph.num_edges() {
185            return Err(crate::registry::ConstructionError::length_mismatch(
186                "edge_lengths",
187                edge_lengths.len(),
188                graph.num_edges(),
189            ));
190        }
191        if k == 0 {
192            return Err("k must be positive".into());
193        }
194        if k > graph.num_vertices() {
195            return Err("k must not exceed num_vertices".into());
196        }
197        Ok(Self {
198            graph,
199            vertex_weights,
200            edge_lengths,
201            k,
202        })
203    }
204
205    /// Get a reference to the underlying graph.
206    pub fn graph(&self) -> &G {
207        &self.graph
208    }
209
210    /// Get a reference to the vertex weights.
211    pub fn vertex_weights(&self) -> &[W] {
212        &self.vertex_weights
213    }
214
215    /// Get a reference to the edge lengths.
216    pub fn edge_lengths(&self) -> &[W] {
217        &self.edge_lengths
218    }
219
220    /// Get the number of centers K.
221    pub fn k(&self) -> usize {
222        self.k
223    }
224}
225
226impl<G: Graph, W: WeightElement> MinimumSumMulticenter<G, W> {
227    /// Get the number of vertices in the underlying graph.
228    pub fn num_vertices(&self) -> usize {
229        self.graph().num_vertices()
230    }
231
232    /// Get the number of edges in the underlying graph.
233    pub fn num_edges(&self) -> usize {
234        self.graph().num_edges()
235    }
236
237    /// Get the number of centers K.
238    pub fn num_centers(&self) -> usize {
239        self.k
240    }
241
242    /// Compute shortest distances from each vertex to the nearest center.
243    ///
244    /// Uses multi-source Dijkstra with linear scan: initializes all centers
245    /// at distance 0 and greedily relaxes edges by increasing distance.
246    /// Correct because all edge lengths are non-negative.
247    ///
248    /// Returns `None` if any vertex is unreachable from all centers.
249    fn shortest_distances(&self, config: &[bool]) -> Option<Vec<W::Sum>> {
250        let n = self.graph.num_vertices();
251        let edges = self.graph.edges();
252
253        let mut adj: Vec<Vec<(usize, W::Sum)>> = vec![Vec::new(); n];
254        for (idx, &(u, v)) in edges.iter().enumerate() {
255            let len = self.edge_lengths[idx].to_sum();
256            adj[u].push((v, len.clone()));
257            adj[v].push((u, len));
258        }
259
260        // Multi-source Dijkstra with linear scan (works with PartialOrd)
261        let mut dist: Vec<Option<W::Sum>> = vec![None; n];
262        let mut visited = vec![false; n];
263
264        // Initialize centers
265        for (v, &selected) in config.iter().enumerate() {
266            if selected {
267                dist[v] = Some(W::Sum::zero());
268            }
269        }
270
271        for _ in 0..n {
272            // Find unvisited vertex with smallest distance
273            let mut u = None;
274            for v in 0..n {
275                if visited[v] {
276                    continue;
277                }
278                if let Some(ref dv) = dist[v] {
279                    match u {
280                        None => u = Some(v),
281                        Some(prev) => {
282                            if *dv < dist[prev].clone().unwrap() {
283                                u = Some(v);
284                            }
285                        }
286                    }
287                }
288            }
289            let u = match u {
290                Some(v) => v,
291                None => break, // remaining vertices are unreachable
292            };
293            visited[u] = true;
294
295            let du = dist[u].clone().unwrap();
296            for &(next, ref len) in &adj[u] {
297                if visited[next] {
298                    continue;
299                }
300                let new_dist = du.clone() + len.clone();
301                let update = match &dist[next] {
302                    None => true,
303                    Some(d) => new_dist < *d,
304                };
305                if update {
306                    dist[next] = Some(new_dist);
307                }
308            }
309        }
310
311        dist.into_iter().collect()
312    }
313}
314
315impl<G, W> Problem for MinimumSumMulticenter<G, W>
316where
317    G: Graph + crate::variant::VariantParam,
318    W: WeightElement + crate::variant::VariantParam,
319{
320    const NAME: &'static str = "MinimumSumMulticenter";
321    type Solution = Vec<bool>;
322    type Value = Min<W::Sum>;
323
324    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
325
326    fn variant() -> Vec<(&'static str, &'static str)> {
327        crate::variant_params![G, W]
328    }
329
330    fn evaluate(
331        &self,
332        config: &Self::Solution,
333    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
334        if config.len() != self.graph.num_vertices() {
335            return Err(crate::traits::EvaluationError::InvalidConfiguration(
336                "center-selection length does not match the graph vertices".into(),
337            ));
338        }
339        Ok({
340            // Check exactly K centers are selected
341            let num_selected = config.iter().filter(|&&selected| selected).count();
342            if num_selected != self.k {
343                return Ok(Min(None));
344            }
345
346            // Compute shortest distances to nearest center
347            let distances = match self.shortest_distances(config) {
348                Some(d) => d,
349                None => return Ok(Min(None)),
350            };
351
352            // Compute total weighted distance: Σ w(v) * d(v)
353            let mut total = W::Sum::zero();
354            for (v, dist) in distances.iter().enumerate() {
355                let weighted_distance = W::checked_mul_sum(
356                    self.vertex_weights[v].to_sum(),
357                    dist.clone(),
358                    "multiplying multicenter vertex weight by distance",
359                )?;
360                total = W::checked_add_to_sum(
361                    total,
362                    weighted_distance,
363                    "summing weighted multicenter distances",
364                )?;
365            }
366
367            Min(Some(total))
368        })
369    }
370}
371
372impl<G, W> crate::solvers::BruteForceProblem for MinimumSumMulticenter<G, W>
373where
374    G: Graph + crate::variant::VariantParam,
375    W: WeightElement + crate::variant::VariantParam,
376{
377    fn dimensions(&self) -> Vec<usize> {
378        vec![2; self.graph.num_vertices()]
379    }
380}
381
382crate::impl_random_generate!(MinimumSumMulticenter<SimpleGraph, i64>, MinimumSumMulticenterRandomSpec, |spec| {
383    let graph = crate::random::SimpleGraphRandomSpec {
384        num_vertices: spec.num_vertices,
385        edge_prob: spec.edge_prob,
386        seed: spec.seed,
387    }.graph()?;
388    let k = spec.k.unwrap_or(std::cmp::max(1, spec.num_vertices / 3));
389    if k == 0 || k > spec.num_vertices {
390        return Err(format!("k must be between 1 and {}", spec.num_vertices).into());
391    }
392    let lengths = vec![1; graph.num_edges()];
393    Ok(MinimumSumMulticenter::new(graph, vec![1; spec.num_vertices], lengths, k))
394});
395
396crate::declare_variants! {
397    default MinimumSumMulticenter<SimpleGraph, i64> => "2^num_vertices" create MinimumSumMulticenterCreateSpec random,
398}
399
400crate::register_brute_force! {
401    MinimumSumMulticenter<SimpleGraph, i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
402}
403
404#[cfg(feature = "example-db")]
405pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
406    vec![crate::example_db::specs::ModelExampleSpec {
407        id: "minimum_sum_multicenter_simplegraph",
408        instance: Box::new(MinimumSumMulticenter::new(
409            SimpleGraph::new(
410                7,
411                vec![
412                    (0, 1),
413                    (1, 2),
414                    (2, 3),
415                    (3, 4),
416                    (4, 5),
417                    (5, 6),
418                    (0, 6),
419                    (2, 5),
420                ],
421            ),
422            vec![1i64; 7],
423            vec![1i64; 8],
424            2,
425        )),
426        optimal_config: serde_json::json!(vec![false, false, true, false, false, true, false]),
427        optimal_value: serde_json::json!(6),
428    }]
429}
430
431#[cfg(test)]
432#[path = "../../unit_tests/models/graph/minimum_sum_multicenter.rs"]
433mod tests;
434
435crate::decision_problem_meta!(MinimumSumMulticenter<SimpleGraph, i64>, "DecisionMinimumSumMulticenter");
436crate::register_decision_variant!(
437    MinimumSumMulticenter<SimpleGraph, i64>, "DecisionMinimumSumMulticenter", "2^num_vertices", &[],
438    "Does a feasible solution have objective value <= the bound?",
439    category: crate::registry::ProblemCategory::Graph,
440    dims: [
441            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
442            VariantDimension::new("weight", "i64", &["i64"]),
443        ],
444    fields: [
445        crate::registry::FieldInfo { name: "graph", type_name: "Vec<(usize,usize)>", description: "Graph edges as comma-separated vertex pairs." },
446        crate::registry::FieldInfo { name: "num_vertices", type_name: "usize", description: "Number of vertices, including isolated vertices." },
447        crate::registry::FieldInfo { name: "weights", type_name: "Vec<i64>", description: "Weights for each vertex." },
448        crate::registry::FieldInfo { name: "edge_weights", type_name: "Vec<i64>", description: "Weights for each edge in graph order." },
449        crate::registry::FieldInfo { name: "k", type_name: "usize", description: "Number of centers." },
450        crate::registry::FieldInfo { name: "bound", type_name: "i64", description: "Accept objective values <= this bound" },
451    ],
452    decode: |_, indices: Vec<usize>| crate::config::config_to_bits(&indices)
453);
454
455#[cfg(feature = "example-db")]
456pub(crate) fn decision_canonical_rule_example_specs(
457) -> Vec<crate::example_db::specs::RuleExampleSpec> {
458    vec![crate::example_db::specs::RuleExampleSpec {
459        id: "decision_minimum_sum_multicenter_to_minimum_sum_multicenter",
460        build: || {
461            let source = crate::models::decision::Decision::new(
462                MinimumSumMulticenter::new(
463                    SimpleGraph::new(
464                        7,
465                        vec![
466                            (0, 1),
467                            (1, 2),
468                            (2, 3),
469                            (3, 4),
470                            (4, 5),
471                            (5, 6),
472                            (0, 6),
473                            (2, 5),
474                        ],
475                    ),
476                    vec![1i64; 7],
477                    vec![1i64; 8],
478                    2,
479                ),
480                6,
481            );
482            let witness = serde_json::json!(vec![false, false, true, false, false, true, false]);
483            crate::example_db::specs::rule_example_with_witness::<
484                _,
485                MinimumSumMulticenter<SimpleGraph, i64>,
486            >(
487                source,
488                crate::export::SolutionPair {
489                    source_config: witness.clone(),
490                    target_config: witness,
491                },
492            )
493        },
494    }]
495}
problemreductions/models/graph/minimum_sum_multicenter.rs

problemreductions/models/graph/
minimum_sum_multicenter.rs
