problemreductions/rules/
clustering_ilp.rs

1//! Reduction from Clustering to ILP (Integer Linear Programming).
2//!
3//! Use one binary assignment variable `x_{i,c}` for each element `i` and
4//! cluster `c`. Equality constraints force every element into exactly one
5//! cluster, and conflict constraints forbid any pair with distance above the
6//! diameter bound from sharing a cluster.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::Clustering;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing Clustering to ILP.
14#[derive(Debug, Clone)]
15pub struct ReductionClusteringToILP {
16    target: ILP<bool>,
17    num_elements: usize,
18    num_clusters: usize,
19}
20
21impl ReductionResult for ReductionClusteringToILP {
22    type Source = Clustering;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        crate::rules::ilp_helpers::one_hot_decode_rows(
36            target_solution,
37            self.num_elements,
38            self.num_clusters,
39            0,
40        )
41    }
42}
43
44#[reduction(
45    transform = upper_bound {
46        num_vars = "num_elements * num_clusters",
47        num_constraints = "num_elements + num_elements * (num_elements - 1) / 2 * num_clusters",
48    },
49    unavailable = {
50        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
51    }
52)]
53impl ReduceTo<ILP<bool>> for Clustering {
54    type Result = ReductionClusteringToILP;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let num_elements = self.num_elements();
58        let num_clusters = self.num_clusters();
59        let num_vars = num_elements * num_clusters;
60        let mut constraints = Vec::new();
61
62        let var_index =
63            |element: usize, cluster: usize| -> usize { element * num_clusters + cluster };
64
65        for element in 0..num_elements {
66            let terms: Vec<(usize, i64)> = (0..num_clusters)
67                .map(|cluster| (var_index(element, cluster), 1))
68                .collect();
69            constraints.push(LinearConstraint::eq(terms, 1));
70        }
71
72        let distances = self.distances();
73        let diameter_bound = self.diameter_bound();
74        for (i, row) in distances.iter().enumerate() {
75            for (j, &distance) in row.iter().enumerate().skip(i + 1) {
76                if distance > diameter_bound {
77                    for cluster in 0..num_clusters {
78                        constraints.push(LinearConstraint::le(
79                            vec![(var_index(i, cluster), 1), (var_index(j, cluster), 1)],
80                            1,
81                        ));
82                    }
83                }
84            }
85        }
86
87        Ok(ReductionClusteringToILP {
88            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
89                .map_err(Self::target_construction)?,
90            num_elements,
91            num_clusters,
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: "clustering_to_ilp",
102        build: || {
103            let source = Clustering::new(
104                vec![
105                    vec![0, 1, 3, 3],
106                    vec![1, 0, 3, 3],
107                    vec![3, 3, 0, 1],
108                    vec![3, 3, 1, 0],
109                ],
110                2,
111                1,
112            );
113            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
114                source,
115                SolutionPair {
116                    source_config: serde_json::json!(vec![0, 0, 1, 1]),
117                    target_config: serde_json::json!(vec![1, 0, 1, 0, 0, 1, 0, 1]),
118                },
119            )
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/clustering_ilp.rs"]
126mod tests;
problemreductions/rules/clustering_ilp.rs

problemreductions/rules/
clustering_ilp.rs
