problemreductions/rules/
coloring_ilp.rs

1//! Reduction from KColoring to ILP (Integer Linear Programming).
2//!
3//! The Graph K-Coloring problem can be formulated as a binary ILP:
4//! - Variables: x_{v,c} for each vertex v and color c (binary, 1 if vertex v has color c)
5//! - Constraints:
6//!   1. Each vertex has exactly one color: sum_c x_{v,c} = 1 for each vertex v
7//!   2. Adjacent vertices have different colors: x_{u,c} + x_{v,c} <= 1 for each edge (u,v) and color c
8//! - Objective: None (feasibility problem, minimize 0)
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::KColoring;
12use crate::reduction;
13use crate::rules::ilp_helpers::one_hot_decode_rows;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16use crate::variant::{KValue, K1, K2, K3, K4, KN};
17
18/// Result of reducing KColoring to ILP.
19///
20/// This reduction creates a binary ILP where:
21/// - Each (vertex, color) pair corresponds to a binary variable
22/// - Constraints ensure each vertex has exactly one color
23/// - Constraints ensure adjacent vertices have different colors
24#[derive(Debug, Clone)]
25pub struct ReductionKColoringToILP<K: KValue, G> {
26    target: ILP<bool>,
27    num_vertices: usize,
28    num_colors: usize,
29    _phantom: std::marker::PhantomData<(K, G)>,
30}
31
32impl<K: KValue, G> ReductionResult for ReductionKColoringToILP<K, G>
33where
34    G: Graph + crate::variant::VariantParam,
35{
36    type Source = KColoring<K, G>;
37    type Target = ILP<bool>;
38
39    fn target_problem(&self) -> &ILP<bool> {
40        &self.target
41    }
42
43    /// Extract solution from ILP back to KColoring.
44    ///
45    /// The ILP solution has num_vertices * K binary variables.
46    /// For each vertex, we find which color has value 1.
47    fn extract_solution(
48        &self,
49        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
50    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
51        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
52
53        one_hot_decode_rows(target_solution, self.num_vertices, self.num_colors, 0)
54    }
55}
56
57/// Helper function implementing the KColoring to ILP reduction logic.
58fn reduce_kcoloring_to_ilp<K: KValue, G: Graph>(
59    problem: &KColoring<K, G>,
60) -> Result<ReductionKColoringToILP<K, G>, crate::registry::ConstructionError> {
61    let k = problem.num_colors();
62    let num_vertices = problem.graph().num_vertices();
63    let num_vars = num_vertices * k;
64
65    // Helper function to get variable index
66    let var_index = |v: usize, c: usize| -> usize { v * k + c };
67
68    let mut constraints = Vec::new();
69
70    // Constraint 1: Each vertex has exactly one color
71    // sum_c x_{v,c} = 1 for each vertex v
72    for v in 0..num_vertices {
73        let terms: Vec<(usize, i64)> = (0..k).map(|c| (var_index(v, c), 1)).collect();
74        constraints.push(LinearConstraint::eq(terms, 1));
75    }
76
77    // Constraint 2: Adjacent vertices have different colors
78    // x_{u,c} + x_{v,c} <= 1 for each edge (u,v) and each color c
79    for (u, v) in problem.graph().edges() {
80        for c in 0..k {
81            constraints.push(LinearConstraint::le(
82                vec![(var_index(u, c), 1), (var_index(v, c), 1)],
83                1,
84            ));
85        }
86    }
87
88    // Objective: minimize 0 (feasibility problem)
89    // We use an empty objective
90    let objective: Vec<(usize, i64)> = vec![];
91
92    let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)?;
93
94    Ok(ReductionKColoringToILP {
95        target,
96        num_vertices,
97        num_colors: k,
98        _phantom: std::marker::PhantomData,
99    })
100}
101
102// Register only the KN variant in the reduction graph
103#[reduction(
104    transform = exact {
105        num_vars = "num_vertices * num_colors",
106        num_constraints = "num_vertices + num_edges * num_colors",
107        num_nonzeros = "num_colors * (num_vertices + 2 * num_edges)",
108    }
109)]
110impl ReduceTo<ILP<bool>> for KColoring<KN, SimpleGraph> {
111    type Result = ReductionKColoringToILP<KN, SimpleGraph>;
112
113    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
114        reduce_kcoloring_to_ilp(self).map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)
115    }
116}
117
118// Additional concrete impls for tests (not registered in reduction graph)
119macro_rules! impl_kcoloring_to_ilp {
120    ($($ktype:ty),+) => {$(
121        impl ReduceTo<ILP<bool>> for KColoring<$ktype, SimpleGraph> {
122            type Result = ReductionKColoringToILP<$ktype, SimpleGraph>;
123            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
124                reduce_kcoloring_to_ilp(self)
125                    .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)
126            }
127        }
128    )+};
129}
130
131impl_kcoloring_to_ilp!(K1, K2, K3, K4);
132
133#[cfg(feature = "example-db")]
134pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
135    use crate::export::SolutionPair;
136    use crate::topology::SimpleGraph;
137
138    vec![crate::example_db::specs::RuleExampleSpec {
139        id: "kcoloring_to_ilp",
140        build: || {
141            let (n, edges) = crate::topology::small_graphs::petersen();
142            let source = KColoring::<KN, _>::with_k(SimpleGraph::new(n, edges), 3);
143            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
144                source,
145                SolutionPair {
146                    source_config: serde_json::json!(vec![0, 2, 0, 1, 2, 1, 1, 2, 0, 0]),
147                    target_config: serde_json::json!(vec![
148                        1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
149                        0, 0, 1, 0, 0,
150                    ]),
151                },
152            )
153        },
154    }]
155}
156
157#[cfg(test)]
158#[path = "../unit_tests/rules/coloring_ilp.rs"]
159mod tests;
problemreductions/rules/coloring_ilp.rs

problemreductions/rules/
coloring_ilp.rs
