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(test)]
141#[path = "../unit_tests/rules/coloring_ilp.rs"]
142mod tests;
problemreductions/rules/coloring_ilp.rs

problemreductions/rules/
coloring_ilp.rs
