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, K2, K3, 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_witness(
52            self.target_problem(),
53            target_solution,
54            |value| value.value.is_some(),
55            "target ILP assignment is infeasible",
56        )?;
57
58        one_hot_decode_rows(target_solution, self.num_vertices, self.num_colors, 0)
59    }
60}
61
62/// Helper function implementing the KColoring to ILP reduction logic.
63fn reduce_kcoloring_to_ilp<K: KValue, G: Graph>(
64    problem: &KColoring<K, G>,
65) -> Result<ReductionKColoringToILP<K, G>, crate::registry::ConstructionError> {
66    let k = problem.num_colors();
67    let num_vertices = problem.graph().num_vertices();
68    let num_vars = num_vertices * k;
69
70    // Helper function to get variable index
71    let var_index = |v: usize, c: usize| -> usize { v * k + c };
72
73    let mut constraints = Vec::new();
74
75    // Constraint 1: Each vertex has exactly one color
76    // sum_c x_{v,c} = 1 for each vertex v
77    for v in 0..num_vertices {
78        let terms: Vec<(usize, i64)> = (0..k).map(|c| (var_index(v, c), 1)).collect();
79        constraints.push(LinearConstraint::eq(terms, 1));
80    }
81
82    // Constraint 2: Adjacent vertices have different colors
83    // x_{u,c} + x_{v,c} <= 1 for each edge (u,v) and each color c
84    for (u, v) in problem.graph().edges() {
85        for c in 0..k {
86            constraints.push(LinearConstraint::le(
87                vec![(var_index(u, c), 1), (var_index(v, c), 1)],
88                1,
89            ));
90        }
91    }
92
93    // Objective: minimize 0 (feasibility problem)
94    // We use an empty objective
95    let objective: Vec<(usize, i64)> = vec![];
96
97    let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)?;
98
99    Ok(ReductionKColoringToILP {
100        target,
101        num_vertices,
102        num_colors: k,
103        _phantom: std::marker::PhantomData,
104    })
105}
106
107crate::register_aggregate_reduction!(ReductionKColoringToILP<KN, SimpleGraph>);
108
109#[crate::aggregate_reduction(ilp_feasibility)]
110impl<K: KValue, G: Graph + crate::variant::VariantParam> crate::rules::AggregateReductionResult
111    for ReductionKColoringToILP<K, G>
112{
113}
114
115// Register only the KN variant in the reduction graph. Each edge row has at most
116// two nonzeros: a self-loop merges both endpoint terms into one coefficient.
117#[reduction(transform = {
118    exact {
119        num_vars = "num_vertices * num_colors",
120        num_constraints = "num_vertices + num_edges * num_colors",
121    },
122    upper_bound {
123        num_nonzeros = "num_colors * (num_vertices + 2 * num_edges)",
124        max_constraint_magnitude_bits = "2",
125    },
126})]
127impl ReduceTo<ILP<bool>> for KColoring<KN, SimpleGraph> {
128    type Result = ReductionKColoringToILP<KN, SimpleGraph>;
129
130    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
131        reduce_kcoloring_to_ilp(self).map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)
132    }
133}
134
135// Additional concrete impls for tests (not registered in reduction graph)
136macro_rules! impl_kcoloring_to_ilp {
137    ($($ktype:ty),+) => {$(
138        impl ReduceTo<ILP<bool>> for KColoring<$ktype, SimpleGraph> {
139            type Result = ReductionKColoringToILP<$ktype, SimpleGraph>;
140            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
141                reduce_kcoloring_to_ilp(self)
142                    .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)
143            }
144        }
145    )+};
146}
147
148impl_kcoloring_to_ilp!(K2, K3);
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
152    use crate::export::SolutionPair;
153    use crate::topology::SimpleGraph;
154
155    vec![crate::example_db::specs::RuleExampleSpec {
156        id: "kcoloring_to_ilp",
157        build: || {
158            let (n, edges) = crate::topology::small_graphs::petersen();
159            let source = KColoring::<KN, _>::with_k(SimpleGraph::new(n, edges), 3);
160            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
161                source,
162                SolutionPair {
163                    source_config: serde_json::json!(vec![0, 2, 0, 1, 2, 1, 1, 2, 0, 0]),
164                    target_config: serde_json::json!(vec![
165                        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,
166                        0, 0, 1, 0, 0,
167                    ]),
168                },
169            )
170        },
171    }]
172}
173
174#[cfg(test)]
175#[path = "../unit_tests/rules/coloring_ilp.rs"]
176mod tests;
problemreductions/rules/coloring_ilp.rs

problemreductions/rules/
coloring_ilp.rs
