problemreductions/rules/
threepartition_ilp.rs

1//! Exact cover of indexed items by triples whose sizes sum to the bound.
2use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
3use crate::models::misc::ThreePartition;
4use crate::rules::traits::{ReduceTo, ReductionResult};
5
6#[derive(Debug, Clone)]
7pub struct ReductionThreePartitionToILP {
8    target: ILP<bool>,
9    triples: Vec<[usize; 3]>,
10    num_elements: usize,
11}
12
13impl ReductionResult for ReductionThreePartitionToILP {
14    type Source = ThreePartition;
15    type Target = ILP<bool>;
16    fn target_problem(&self) -> &Self::Target {
17        &self.target
18    }
19    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
20        crate::rules::traits::validate_target_witness(
21            &self.target,
22            solution,
23            |value| value.value.is_some(),
24            "target ILP assignment is infeasible",
25        )?;
26        let mut groups = vec![0; self.num_elements];
27        for (group, triple) in self
28            .triples
29            .iter()
30            .zip(solution)
31            .filter(|(_, selected)| **selected == 1)
32            .map(|(triple, _)| triple)
33            .enumerate()
34        {
35            for &item in triple {
36                groups[item] = group;
37            }
38        }
39        Ok(groups)
40    }
41}
42#[crate::aggregate_reduction(ilp_feasibility)]
43impl crate::rules::AggregateReductionResult for ReductionThreePartitionToILP {}
44
45#[crate::reduction(transform = {
46    exact {
47        num_constraints = "num_elements",
48        max_constraint_magnitude_bits = "1",
49    },
50    upper_bound {
51        num_vars = "num_elements * (num_elements - 1) * (num_elements - 2) / 6",
52        num_nonzeros = "num_elements * (num_elements - 1) * (num_elements - 2) / 2",
53    },
54})]
55impl ReduceTo<ILP<bool>> for ThreePartition {
56    type Result = ReductionThreePartitionToILP;
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let mut indices = std::collections::BTreeMap::<i64, Vec<usize>>::new();
59        for (item, &size) in self.sizes().iter().enumerate() {
60            indices.entry(size).or_default().push(item);
61        }
62        let mut triples = Vec::new();
63        let mut rows = vec![Vec::new(); self.num_elements()];
64        for (i, &a) in self.sizes().iter().enumerate() {
65            for (j, &b) in self.sizes().iter().enumerate().skip(i + 1) {
66                // Classical input bounds imply a+b < bound, without overflow.
67                if let Some(candidates) = indices.get(&(self.bound() - a - b)) {
68                    for &k in &candidates[candidates.partition_point(|&k| k <= j)..] {
69                        for item in [i, j, k] {
70                            rows[item].push((triples.len(), 1));
71                        }
72                        triples.push([i, j, k]);
73                    }
74                }
75            }
76        }
77        let target: ILP<bool> = ILP::new(
78            triples.len(),
79            rows.into_iter()
80                .map(|terms| LinearConstraint::eq(terms, 1))
81                .collect(),
82            vec![],
83            ObjectiveSense::Minimize,
84        )
85        .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
86        Ok(Self::Result {
87            target,
88            triples,
89            num_elements: self.num_elements(),
90        })
91    }
92}
93
94#[cfg(feature = "example-db")]
95pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
96    vec![crate::example_db::specs::RuleExampleSpec {
97        id: "threepartition_to_ilp",
98        build: || {
99            crate::example_db::specs::rule_example_via_ilp::<_, bool>(ThreePartition::new(
100                vec![4, 5, 6, 4, 6, 5],
101                15,
102            ))
103        },
104    }]
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/rules/threepartition_ilp.rs"]
109mod tests;
problemreductions/rules/threepartition_ilp.rs

problemreductions/rules/
threepartition_ilp.rs
