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(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        Ok(target_solution.iter().map(|&value| value == 1).collect())
31    }
32}
33
34#[reduction(
35    transform = exact {
36        num_vars = "num_subsets",
37        num_constraints = "universe_size + 1",
38    },
39    unavailable = {
40        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
41    }
42)]
43impl ReduceTo<ILP<bool>> for ExactCoverBy3Sets {
44    type Result = ReductionX3CToILP;
45
46    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
47        let num_vars = self.num_subsets();
48        let mut constraints = Vec::new();
49
50        // For each element e: Σ_{j: e ∈ triple_j} x_j = 1
51        for element in 0..self.universe_size() {
52            let terms: Vec<(usize, i64)> = self
53                .subsets()
54                .iter()
55                .enumerate()
56                .filter(|(_, subset)| subset.contains(&element))
57                .map(|(j, _)| (j, 1))
58                .collect();
59            constraints.push(LinearConstraint::eq(terms, 1));
60        }
61
62        // Σ x_j = universe_size / 3
63        let cardinality_terms: Vec<(usize, i64)> = (0..num_vars).map(|j| (j, 1)).collect();
64        constraints.push(LinearConstraint::eq(
65            cardinality_terms,
66            <Self as ReduceTo<ILP<bool>>>::exact_i64(
67                self.universe_size() / 3,
68                "encoding the exact-cover cardinality",
69            )?,
70        ));
71
72        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
73            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
74        Ok(ReductionX3CToILP { target })
75    }
76}
77
78#[cfg(feature = "example-db")]
79pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
80    use crate::export::SolutionPair;
81    vec![crate::example_db::specs::RuleExampleSpec {
82        id: "exactcoverby3sets_to_ilp",
83        build: || {
84            let source =
85                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4], [1, 2, 5]]);
86            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
87                source,
88                SolutionPair {
89                    source_config: serde_json::json!(vec![true, true, false, false]),
90                    target_config: serde_json::json!(vec![1, 1, 0, 0]),
91                },
92            )
93        },
94    }]
95}
96
97#[cfg(test)]
98#[path = "../unit_tests/rules/exactcoverby3sets_ilp.rs"]
99mod tests;
problemreductions/rules/exactcoverby3sets_ilp.rs

problemreductions/rules/
exactcoverby3sets_ilp.rs
