problemreductions/rules/
minimumdominatingset_ilp.rs

1//! Reduction from MinimumDominatingSet to ILP (Integer Linear Programming).
2//!
3//! The Dominating Set problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per vertex (0 = not selected, 1 = selected)
5//! - Constraints: For each vertex v: x_v + sum_{u in N(v)} x_u >= 1
6//!   (v or at least one of its neighbors must be selected)
7//! - Objective: Minimize the sum of weights of selected vertices
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MinimumDominatingSet;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing MinimumDominatingSet to ILP.
16///
17/// This reduction creates a binary ILP where:
18/// - Each vertex corresponds to a binary variable
19/// - For each vertex v, the constraint x_v + sum_{u in N(v)} x_u >= 1 ensures
20///   that v is dominated (either v itself or one of its neighbors is selected)
21/// - The objective minimizes the total weight of selected vertices
22#[derive(Debug, Clone)]
23pub struct ReductionDSToILP {
24    target: ILP<bool>,
25}
26
27impl ReductionResult for ReductionDSToILP {
28    type Source = MinimumDominatingSet<SimpleGraph, i64>;
29    type Target = ILP<bool>;
30
31    fn target_problem(&self) -> &ILP<bool> {
32        &self.target
33    }
34
35    /// Extract solution from ILP back to MinimumDominatingSet.
36    ///
37    /// Since the mapping is 1:1 (each vertex maps to one binary variable),
38    /// the solution extraction is simply copying the configuration.
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok(target_solution.iter().map(|&value| value == 1).collect())
46    }
47}
48
49// Each vertex contributes its own variable plus its neighbor incidences;
50// merging repeated coefficients can only reduce the n+2m nonzero bound.
51#[reduction(transform = {
52    exact {
53        num_vars = "num_vertices",
54        num_constraints = "num_vertices",
55    },
56    upper_bound {
57        max_constraint_magnitude_bits = "2 * num_edges + 2",
58        num_nonzeros = "2 * num_edges + num_vertices",
59    },
60})]
61impl ReduceTo<ILP<bool>> for MinimumDominatingSet<SimpleGraph, i64> {
62    type Result = ReductionDSToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let num_vars = self.graph().num_vertices();
66
67        // Constraints: For each vertex v, x_v + sum_{u in N(v)} x_u >= 1
68        // This ensures that v is dominated (either selected or has a selected neighbor)
69        let constraints: Vec<LinearConstraint> = (0..num_vars)
70            .map(|v| {
71                // Build terms: x_v with coefficient 1, plus each neighbor with coefficient 1
72                let mut terms: Vec<(usize, i64)> = vec![(v, 1)];
73                for neighbor in self.neighbors(v) {
74                    terms.push((neighbor, 1));
75                }
76                LinearConstraint::ge(terms, 1)
77            })
78            .collect();
79
80        // Objective: minimize sum of w_i * x_i (weighted sum of selected vertices)
81        let objective: Vec<(usize, i64)> = self
82            .weights()
83            .iter()
84            .enumerate()
85            .map(|(vertex, &weight)| (vertex, weight))
86            .collect();
87
88        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
89            .map_err(Self::target_construction)?;
90
91        Ok(ReductionDSToILP { target })
92    }
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "minimumdominatingset_to_ilp",
99        build: || {
100            let (n, edges) = crate::topology::small_graphs::petersen();
101            let source = MinimumDominatingSet::new(SimpleGraph::new(n, edges), vec![1i64; 10]);
102            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
103        },
104    }]
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/rules/minimumdominatingset_ilp.rs"]
109mod tests;
problemreductions/rules/minimumdominatingset_ilp.rs

problemreductions/rules/
minimumdominatingset_ilp.rs
