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(
42        &self,
43        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
44    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
45        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
46
47        Ok(target_solution.iter().map(|&value| value == 1).collect())
48    }
49}
50
51#[reduction(transform = {
52    exact {
53        num_vars = "num_vertices",
54        num_constraints = "num_vertices * (num_vertices - 1) / 2",
55    },
56    upper_bound {
57        max_constraint_magnitude_bits = "1",
58        num_nonzeros = "num_vertices * (num_vertices * (num_vertices - 1) / 2)",
59    },
60})]
61impl ReduceTo<ILP<bool>> for MinimumMetricDimension<SimpleGraph> {
62    type Result = ReductionMDToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.graph().num_vertices();
66
67        // Precompute all-pairs shortest paths via BFS from each vertex
68        let all_dists: Vec<Vec<usize>> = (0..n).map(|v| bfs_distances(self.graph(), v)).collect();
69
70        // Constraints: For each pair (u, v) with u < v,
71        // Σ_{w : d(u,w) ≠ d(v,w)} z_w ≥ 1
72        let mut constraints = Vec::new();
73        for u in 0..n {
74            for v in (u + 1)..n {
75                let terms: Vec<(usize, i64)> = (0..n)
76                    .filter(|&w| all_dists[w][u] != all_dists[w][v])
77                    .map(|w| (w, 1))
78                    .collect();
79                constraints.push(LinearConstraint::ge(terms, 1));
80            }
81        }
82
83        // Objective: minimize Σ z_v (unit weights)
84        let objective: Vec<(usize, i64)> = (0..n).map(|v| (v, 1)).collect();
85
86        let target = ILP::new(n, constraints, objective, ObjectiveSense::Minimize)
87            .map_err(Self::target_construction)?;
88
89        Ok(ReductionMDToILP { target })
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "minimummetricdimension_to_ilp",
97        build: || {
98            // P3 path graph: 3 vertices, metric dimension = 1
99            let source = MinimumMetricDimension::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]));
100            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
101        },
102    }]
103}
104
105#[cfg(test)]
106#[path = "../unit_tests/rules/minimummetricdimension_ilp.rs"]
107mod tests;
problemreductions/rules/minimummetricdimension_ilp.rs

problemreductions/rules/
minimummetricdimension_ilp.rs
