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 ReductionClusteringToILP {
22    fn var_index(&self, element: usize, cluster: usize) -> usize {
23        element * self.num_clusters + cluster
24    }
25}
26
27impl ReductionResult for ReductionClusteringToILP {
28    type Source = Clustering;
29    type Target = ILP<bool>;
30
31    fn target_problem(&self) -> &Self::Target {
32        &self.target
33    }
34
35    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
36        (0..self.num_elements)
37            .map(|element| {
38                (0..self.num_clusters)
39                    .find(|&cluster| {
40                        let idx = self.var_index(element, cluster);
41                        idx < target_solution.len() && target_solution[idx] == 1
42                    })
43                    .unwrap_or(0)
44            })
45            .collect()
46    }
47}
48
49#[reduction(
50    overhead = {
51        num_vars = "num_elements * num_clusters",
52        num_constraints = "num_elements + num_elements * (num_elements - 1) / 2 * num_clusters",
53    }
54)]
55impl ReduceTo<ILP<bool>> for Clustering {
56    type Result = ReductionClusteringToILP;
57
58    fn reduce_to(&self) -> Self::Result {
59        let num_elements = self.num_elements();
60        let num_clusters = self.num_clusters();
61        let num_vars = num_elements * num_clusters;
62        let mut constraints = Vec::new();
63
64        let var_index =
65            |element: usize, cluster: usize| -> usize { element * num_clusters + cluster };
66
67        for element in 0..num_elements {
68            let terms: Vec<(usize, f64)> = (0..num_clusters)
69                .map(|cluster| (var_index(element, cluster), 1.0))
70                .collect();
71            constraints.push(LinearConstraint::eq(terms, 1.0));
72        }
73
74        let distances = self.distances();
75        let diameter_bound = self.diameter_bound();
76        for (i, row) in distances.iter().enumerate() {
77            for (j, &distance) in row.iter().enumerate().skip(i + 1) {
78                if distance > diameter_bound {
79                    for cluster in 0..num_clusters {
80                        constraints.push(LinearConstraint::le(
81                            vec![(var_index(i, cluster), 1.0), (var_index(j, cluster), 1.0)],
82                            1.0,
83                        ));
84                    }
85                }
86            }
87        }
88
89        ReductionClusteringToILP {
90            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
91            num_elements,
92            num_clusters,
93        }
94    }
95}
96
97#[cfg(feature = "example-db")]
98pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
99    use crate::export::SolutionPair;
100
101    vec![crate::example_db::specs::RuleExampleSpec {
102        id: "clustering_to_ilp",
103        build: || {
104            let source = Clustering::new(
105                vec![
106                    vec![0, 1, 3, 3],
107                    vec![1, 0, 3, 3],
108                    vec![3, 3, 0, 1],
109                    vec![3, 3, 1, 0],
110                ],
111                2,
112                1,
113            );
114            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
115                source,
116                SolutionPair {
117                    source_config: vec![0, 0, 1, 1],
118                    target_config: vec![1, 0, 1, 0, 0, 1, 0, 1],
119                },
120            )
121        },
122    }]
123}
124
125#[cfg(test)]
126#[path = "../unit_tests/rules/clustering_ilp.rs"]
127mod tests;
problemreductions/rules/clustering_ilp.rs

problemreductions/rules/
clustering_ilp.rs
