problemreductions/rules/
exactcoverby3sets_ilp.rs

1//! Reduction from ExactCoverBy3Sets to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_j per triple; for each element e, require Σ x_j = 1
4//! (exact cover). Additional constraint Σ x_j = universe_size/3.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::set::ExactCoverBy3Sets;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11#[derive(Debug, Clone)]
12pub struct ReductionX3CToILP {
13    target: ILP<bool>,
14}
15
16impl ReductionResult for ReductionX3CToILP {
17    type Source = ExactCoverBy3Sets;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &ILP<bool> {
21        &self.target
22    }
23
24    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
25        target_solution.to_vec()
26    }
27}
28
29#[reduction(
30    overhead = {
31        num_vars = "num_subsets",
32        num_constraints = "universe_size + 1",
33    }
34)]
35impl ReduceTo<ILP<bool>> for ExactCoverBy3Sets {
36    type Result = ReductionX3CToILP;
37
38    fn reduce_to(&self) -> Self::Result {
39        let num_vars = self.num_subsets();
40        let mut constraints = Vec::new();
41
42        // For each element e: Σ_{j: e ∈ triple_j} x_j = 1
43        for element in 0..self.universe_size() {
44            let terms: Vec<(usize, f64)> = self
45                .subsets()
46                .iter()
47                .enumerate()
48                .filter(|(_, subset)| subset.contains(&element))
49                .map(|(j, _)| (j, 1.0))
50                .collect();
51            constraints.push(LinearConstraint::eq(terms, 1.0));
52        }
53
54        // Σ x_j = universe_size / 3
55        let cardinality_terms: Vec<(usize, f64)> = (0..num_vars).map(|j| (j, 1.0)).collect();
56        constraints.push(LinearConstraint::eq(
57            cardinality_terms,
58            (self.universe_size() / 3) as f64,
59        ));
60
61        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
62        ReductionX3CToILP { target }
63    }
64}
65
66#[cfg(feature = "example-db")]
67pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
68    use crate::export::SolutionPair;
69    vec![crate::example_db::specs::RuleExampleSpec {
70        id: "exactcoverby3sets_to_ilp",
71        build: || {
72            let source =
73                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4], [1, 2, 5]]);
74            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
75                source,
76                SolutionPair {
77                    source_config: vec![1, 1, 0, 0],
78                    target_config: vec![1, 1, 0, 0],
79                },
80            )
81        },
82    }]
83}
84
85#[cfg(test)]
86#[path = "../unit_tests/rules/exactcoverby3sets_ilp.rs"]
87mod tests;
problemreductions/rules/exactcoverby3sets_ilp.rs

problemreductions/rules/
exactcoverby3sets_ilp.rs
