problemreductions/rules/
maximumdomaticnumber_ilp.rs

1//! Reduction from MaximumDomaticNumber to ILP (Integer Linear Programming).
2//!
3//! The Maximum Domatic Number problem can be formulated as a binary ILP:
4//! - Variables: x_{v,i} for each vertex v and set index i (binary: vertex v in set i),
5//!   plus y_i for each set index i (binary: set i is used).
6//! - Partition constraints: for each v, Σ_i x_{v,i} = 1
7//! - Domination constraints: for each v and i, x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} ≥ y_i
8//! - Linking constraints: x_{v,i} ≤ y_i for each v, i
9//! - Objective: maximize Σ y_i
10
11use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
12use crate::models::graph::MaximumDomaticNumber;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16
17/// Result of reducing MaximumDomaticNumber to ILP.
18///
19/// Variable layout:
20/// - x_{v,i} at index v*n + i (vertex v assigned to set i)
21/// - y_i at index n*n + i (set i is used)
22#[derive(Debug, Clone)]
23pub struct ReductionDomaticNumberToILP {
24    target: ILP<bool>,
25    n: usize,
26}
27
28impl ReductionResult for ReductionDomaticNumberToILP {
29    type Source = MaximumDomaticNumber<SimpleGraph>;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    /// Extract solution from ILP back to MaximumDomaticNumber.
37    ///
38    /// For each vertex v, find the set index i where x_{v,i} = 1.
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({
46            let n = self.n;
47            let mut config = vec![0; n];
48            for v in 0..n {
49                for i in 0..n {
50                    if target_solution[v * n + i] == 1 {
51                        config[v] = i;
52                        break;
53                    }
54                }
55            }
56            config
57        })
58    }
59}
60
61#[reduction(
62    transform = exact {
63        num_vars = "num_vertices * num_vertices + num_vertices",
64        num_constraints = "num_vertices + num_vertices * num_vertices + num_vertices * num_vertices",
65    },
66    unavailable = {
67        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
68    }
69)]
70impl ReduceTo<ILP<bool>> for MaximumDomaticNumber<SimpleGraph> {
71    type Result = ReductionDomaticNumberToILP;
72
73    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
74        let n = self.graph().num_vertices();
75        let num_vars = n * n + n;
76        let mut constraints = Vec::new();
77
78        // Partition constraints: for each vertex v, Σ_i x_{v,i} = 1
79        for v in 0..n {
80            let terms: Vec<(usize, i64)> = (0..n).map(|i| (v * n + i, 1)).collect();
81            constraints.push(LinearConstraint::eq(terms, 1));
82        }
83
84        // Domination constraints: for each v, i: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} >= y_i
85        // Rewritten as: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} - y_i >= 0
86        for v in 0..n {
87            let neighbors = self.graph().neighbors(v);
88            for i in 0..n {
89                let mut terms: Vec<(usize, i64)> = vec![(v * n + i, 1)];
90                for &u in &neighbors {
91                    terms.push((u * n + i, 1));
92                }
93                // -y_i
94                terms.push((n * n + i, -1));
95                constraints.push(LinearConstraint::ge(terms, 0));
96            }
97        }
98
99        // Linking constraints: x_{v,i} <= y_i for each v, i
100        // Forces y_i = 1 whenever any vertex is assigned to set i,
101        // ensuring extract_solution always yields a valid partition.
102        for v in 0..n {
103            for i in 0..n {
104                constraints.push(LinearConstraint::le(
105                    vec![(v * n + i, 1), (n * n + i, -1)],
106                    0,
107                ));
108            }
109        }
110
111        // Objective: maximize Σ y_i
112        let objective: Vec<(usize, i64)> = (0..n).map(|i| (n * n + i, 1)).collect();
113
114        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
115            .map_err(Self::target_construction)?;
116
117        Ok(ReductionDomaticNumberToILP { target, n })
118    }
119}
120
121#[cfg(feature = "example-db")]
122pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
123    vec![crate::example_db::specs::RuleExampleSpec {
124        id: "maximumdomaticnumber_to_ilp",
125        build: || {
126            // Use small P3 graph (3 vertices, domatic number = 2)
127            let source = MaximumDomaticNumber::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]));
128            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
129        },
130    }]
131}
132
133#[cfg(test)]
134#[path = "../unit_tests/rules/maximumdomaticnumber_ilp.rs"]
135mod tests;
problemreductions/rules/maximumdomaticnumber_ilp.rs

problemreductions/rules/
maximumdomaticnumber_ilp.rs
