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(transform = {
62    exact {
63        max_constraint_magnitude_bits = "1",
64        num_vars = "num_vertices * num_vertices + num_vertices",
65        num_constraints = "num_vertices + num_vertices * num_vertices + num_vertices * num_vertices",
66    },
67    upper_bound {
68        num_nonzeros = "(num_vertices * num_vertices + num_vertices) * (num_vertices + num_vertices * num_vertices + num_vertices * num_vertices)",
69    },
70})]
71impl ReduceTo<ILP<bool>> for MaximumDomaticNumber<SimpleGraph> {
72    type Result = ReductionDomaticNumberToILP;
73
74    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
75        let n = self.graph().num_vertices();
76        let num_vars = n * n + n;
77        let mut constraints = Vec::new();
78
79        // Partition constraints: for each vertex v, Σ_i x_{v,i} = 1
80        for v in 0..n {
81            let terms: Vec<(usize, i64)> = (0..n).map(|i| (v * n + i, 1)).collect();
82            constraints.push(LinearConstraint::eq(terms, 1));
83        }
84
85        // Domination constraints: for each v, i: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} >= y_i
86        // Rewritten as: x_{v,i} + Σ_{u ∈ N(v)} x_{u,i} - y_i >= 0
87        for v in 0..n {
88            let mut neighborhood = self.graph().neighbors(v);
89            neighborhood.push(v);
90            neighborhood.sort_unstable();
91            neighborhood.dedup();
92            for i in 0..n {
93                let mut terms: Vec<(usize, i64)> =
94                    neighborhood.iter().map(|&u| (u * n + i, 1)).collect();
95                // -y_i
96                terms.push((n * n + i, -1));
97                constraints.push(LinearConstraint::ge(terms, 0));
98            }
99        }
100
101        // Linking constraints: x_{v,i} <= y_i for each v, i
102        // Forces y_i = 1 whenever any vertex is assigned to set i,
103        // ensuring extract_solution always yields a valid partition.
104        for v in 0..n {
105            for i in 0..n {
106                constraints.push(LinearConstraint::le(
107                    vec![(v * n + i, 1), (n * n + i, -1)],
108                    0,
109                ));
110            }
111        }
112
113        // Objective: maximize Σ y_i
114        let objective: Vec<(usize, i64)> = (0..n).map(|i| (n * n + i, 1)).collect();
115
116        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
117            .map_err(Self::target_construction)?;
118
119        Ok(ReductionDomaticNumberToILP { target, n })
120    }
121}
122
123#[cfg(feature = "example-db")]
124pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
125    vec![crate::example_db::specs::RuleExampleSpec {
126        id: "maximumdomaticnumber_to_ilp",
127        build: || {
128            // Use small P3 graph (3 vertices, domatic number = 2)
129            let source = MaximumDomaticNumber::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]));
130            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
131        },
132    }]
133}
134
135#[cfg(test)]
136#[path = "../unit_tests/rules/maximumdomaticnumber_ilp.rs"]
137mod tests;
problemreductions/rules/maximumdomaticnumber_ilp.rs

problemreductions/rules/
maximumdomaticnumber_ilp.rs
