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

problemreductions/rules/
clustering_ilp.rs
