problemreductions/rules/
minimummetricdimension_ilp.rs

1//! Reduction from MinimumMetricDimension to ILP (Integer Linear Programming).
2//!
3//! The Metric Dimension problem can be formulated as a binary ILP:
4//! - Variables: One binary variable z_v per vertex (0 = not selected, 1 = selected)
5//! - Constraints: For each pair (u, v) with u < v:
6//!   Σ_{w : d(u,w) ≠ d(v,w)} z_w ≥ 1
7//!   (at least one resolving vertex distinguishes u from v)
8//! - Objective: Minimize Σ z_v
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::minimum_metric_dimension::bfs_distances;
12use crate::models::graph::MinimumMetricDimension;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16
17/// Result of reducing MinimumMetricDimension to ILP.
18///
19/// This reduction creates a binary ILP where:
20/// - Each vertex corresponds to a binary variable z_v
21/// - For each pair (u, v) with u < v, the constraint
22///   Σ_{w : d(u,w) ≠ d(v,w)} z_w ≥ 1 ensures that the pair is resolved
23/// - The objective minimizes the total number of selected vertices
24#[derive(Debug, Clone)]
25pub struct ReductionMDToILP {
26    target: ILP<bool>,
27}
28
29impl ReductionResult for ReductionMDToILP {
30    type Source = MinimumMetricDimension<SimpleGraph>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract solution from ILP back to MinimumMetricDimension.
38    ///
39    /// Since the mapping is 1:1 (each vertex maps to one binary variable),
40    /// the solution extraction is simply copying the configuration.
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        target_solution.to_vec()
43    }
44}
45
46#[reduction(
47    overhead = {
48        num_vars = "num_vertices",
49        num_constraints = "num_vertices * (num_vertices - 1) / 2",
50    }
51)]
52impl ReduceTo<ILP<bool>> for MinimumMetricDimension<SimpleGraph> {
53    type Result = ReductionMDToILP;
54
55    fn reduce_to(&self) -> Self::Result {
56        let n = self.graph().num_vertices();
57
58        // Precompute all-pairs shortest paths via BFS from each vertex
59        let all_dists: Vec<Vec<usize>> = (0..n).map(|v| bfs_distances(self.graph(), v)).collect();
60
61        // Constraints: For each pair (u, v) with u < v,
62        // Σ_{w : d(u,w) ≠ d(v,w)} z_w ≥ 1
63        let mut constraints = Vec::new();
64        for u in 0..n {
65            for v in (u + 1)..n {
66                let terms: Vec<(usize, f64)> = (0..n)
67                    .filter(|&w| all_dists[w][u] != all_dists[w][v])
68                    .map(|w| (w, 1.0))
69                    .collect();
70                constraints.push(LinearConstraint::ge(terms, 1.0));
71            }
72        }
73
74        // Objective: minimize Σ z_v (unit weights)
75        let objective: Vec<(usize, f64)> = (0..n).map(|v| (v, 1.0)).collect();
76
77        let target = ILP::new(n, constraints, objective, ObjectiveSense::Minimize);
78
79        ReductionMDToILP { target }
80    }
81}
82
83#[cfg(feature = "example-db")]
84pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
85    vec![crate::example_db::specs::RuleExampleSpec {
86        id: "minimummetricdimension_to_ilp",
87        build: || {
88            // P3 path graph: 3 vertices, metric dimension = 1
89            let source = MinimumMetricDimension::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]));
90            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
91        },
92    }]
93}
94
95#[cfg(test)]
96#[path = "../unit_tests/rules/minimummetricdimension_ilp.rs"]
97mod tests;
problemreductions/rules/minimummetricdimension_ilp.rs

problemreductions/rules/
minimummetricdimension_ilp.rs
