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(&self, target_solution: &[usize]) -> Vec<usize> {
40        let n = self.n;
41        let mut config = vec![0; n];
42        for v in 0..n {
43            for i in 0..n {
44                if target_solution[v * n + i] == 1 {
45                    config[v] = i;
46                    break;
47                }
48            }
49        }
50        config
51    }
52}
53
54#[reduction(
55    overhead = {
56        num_vars = "num_vertices * num_vertices + num_vertices",
57        num_constraints = "num_vertices + num_vertices * num_vertices + num_vertices * num_vertices",
58    }
59)]
60impl ReduceTo<ILP<bool>> for MaximumDomaticNumber<SimpleGraph> {
61    type Result = ReductionDomaticNumberToILP;
62
63    fn reduce_to(&self) -> Self::Result {
64        let n = self.graph().num_vertices();
65        let num_vars = n * n + n;
66        let mut constraints = Vec::new();
67
68        // Partition constraints: for each vertex v, Σ_i x_{v,i} = 1
69        for v in 0..n {
70            let terms: Vec<(usize, f64)> = (0..n).map(|i| (v * n + i, 1.0)).collect();
71            constraints.push(LinearConstraint::eq(terms, 1.0));
72        }
73
74        // Domination constraints: for each v, i: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} >= y_i
75        // Rewritten as: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} - y_i >= 0
76        for v in 0..n {
77            let neighbors = self.graph().neighbors(v);
78            for i in 0..n {
79                let mut terms: Vec<(usize, f64)> = vec![(v * n + i, 1.0)];
80                for &u in &neighbors {
81                    terms.push((u * n + i, 1.0));
82                }
83                // -y_i
84                terms.push((n * n + i, -1.0));
85                constraints.push(LinearConstraint::ge(terms, 0.0));
86            }
87        }
88
89        // Linking constraints: x_{v,i} <= y_i for each v, i
90        // Forces y_i = 1 whenever any vertex is assigned to set i,
91        // ensuring extract_solution always yields a valid partition.
92        for v in 0..n {
93            for i in 0..n {
94                constraints.push(LinearConstraint::le(
95                    vec![(v * n + i, 1.0), (n * n + i, -1.0)],
96                    0.0,
97                ));
98            }
99        }
100
101        // Objective: maximize Σ y_i
102        let objective: Vec<(usize, f64)> = (0..n).map(|i| (n * n + i, 1.0)).collect();
103
104        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
105
106        ReductionDomaticNumberToILP { target, n }
107    }
108}
109
110#[cfg(feature = "example-db")]
111pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
112    vec![crate::example_db::specs::RuleExampleSpec {
113        id: "maximumdomaticnumber_to_ilp",
114        build: || {
115            // Use small P3 graph (3 vertices, domatic number = 2)
116            let source = MaximumDomaticNumber::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]));
117            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/maximumdomaticnumber_ilp.rs"]
124mod tests;
problemreductions/rules/maximumdomaticnumber_ilp.rs

problemreductions/rules/
maximumdomaticnumber_ilp.rs
