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

problemreductions/rules/
coloring_ilp.rs
