problemreductions/rules/
partitionintocliques_ilp.rs

1//! Reduction from PartitionIntoCliques to binary ILP.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::PartitionIntoCliques;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::{Graph, SimpleGraph};
8
9#[derive(Debug, Clone)]
10pub struct ReductionPartitionIntoCliquesToILP {
11    target: ILP<bool>,
12    num_vertices: usize,
13    num_cliques: usize,
14}
15
16impl ReductionResult for ReductionPartitionIntoCliquesToILP {
17    type Source = PartitionIntoCliques<SimpleGraph>;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        (0..self.num_vertices)
31            .map(|vertex| {
32                (0..self.num_cliques)
33                    .find(|&clique| target_solution[vertex * self.num_cliques + clique] == 1)
34                    .ok_or_else(|| {
35                        crate::rules::ExtractionError::invalid(format!(
36                            "target solution does not assign vertex {vertex} to a clique"
37                        ))
38                    })
39            })
40            .collect()
41    }
42}
43
44#[reduction(
45    transform = upper_bound {
46        num_vars = "num_vertices^2",
47        num_constraints = "num_vertices + num_vertices^3",
48    },
49    unavailable = {
50        num_nonzeros = "the exact target parameter depends on the source clique bound and non-edges",
51    }
52)]
53impl ReduceTo<ILP<bool>> for PartitionIntoCliques<SimpleGraph> {
54    type Result = ReductionPartitionIntoCliquesToILP;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let num_vertices = self.num_vertices();
58        let num_cliques = self.num_cliques();
59        let num_vars = num_vertices * num_cliques;
60        let variable = |vertex: usize, clique: usize| vertex * num_cliques + clique;
61        let mut constraints = Vec::new();
62
63        for vertex in 0..num_vertices {
64            constraints.push(LinearConstraint::eq(
65                (0..num_cliques)
66                    .map(|clique| (variable(vertex, clique), 1))
67                    .collect(),
68                1,
69            ));
70        }
71
72        for u in 0..num_vertices {
73            for v in (u + 1)..num_vertices {
74                if !self.graph().has_edge(u, v) {
75                    for clique in 0..num_cliques {
76                        constraints.push(LinearConstraint::le(
77                            vec![(variable(u, clique), 1), (variable(v, clique), 1)],
78                            1,
79                        ));
80                    }
81                }
82            }
83        }
84
85        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
86            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
87
88        Ok(ReductionPartitionIntoCliquesToILP {
89            target,
90            num_vertices,
91            num_cliques,
92        })
93    }
94}
95
96#[cfg(feature = "example-db")]
97pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
98    use crate::export::SolutionPair;
99
100    vec![crate::example_db::specs::RuleExampleSpec {
101        id: "partitionintocliques_to_ilp",
102        build: || {
103            let source = PartitionIntoCliques::new(SimpleGraph::new(3, vec![(0, 1)]), 2);
104            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
105                source,
106                SolutionPair {
107                    source_config: serde_json::json!(vec![0, 0, 1]),
108                    target_config: serde_json::json!(vec![1, 0, 1, 0, 0, 1]),
109                },
110            )
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/partitionintocliques_ilp.rs"]
117mod tests;
problemreductions/rules/partitionintocliques_ilp.rs

problemreductions/rules/
partitionintocliques_ilp.rs
