problemreductions/rules/
maximumsetpacking_ilp.rs

1//! Reduction from MaximumSetPacking to ILP (Integer Linear Programming).
2//!
3//! The Set Packing problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per set (0 = not selected, 1 = selected)
5//! - Constraints: For each element e, Σ_{i : e ∈ S_i} x_i ≤ 1
6//! - Objective: Maximize the sum of weights of selected sets
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::set::MaximumSetPacking;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing MaximumSetPacking to ILP.
14///
15/// This reduction creates a binary ILP where:
16/// - Each set corresponds to a binary variable
17/// - Element constraints ensure at most one set per element is selected
18/// - The objective maximizes the total weight of selected sets
19#[derive(Debug, Clone)]
20pub struct ReductionSPToILP {
21    target: ILP<bool>,
22}
23
24impl ReductionResult for ReductionSPToILP {
25    type Source = MaximumSetPacking<i64>;
26    type Target = ILP<bool>;
27
28    fn target_problem(&self) -> &ILP<bool> {
29        &self.target
30    }
31
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        Ok(target_solution.iter().map(|&value| value == 1).collect())
39    }
40}
41
42#[reduction(
43    transform = exact {
44        num_vars = "num_sets",
45        num_constraints = "universe_size",
46    },
47    unavailable = {
48        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
49    }
50)]
51impl ReduceTo<ILP<bool>> for MaximumSetPacking<i64> {
52    type Result = ReductionSPToILP;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let num_vars = self.num_sets();
56
57        // Build element-to-sets mapping, then create one constraint per element
58        let universe = self.universe_size();
59        let mut elem_to_sets: Vec<Vec<usize>> = vec![Vec::new(); universe];
60        for (i, set) in self.sets().iter().enumerate() {
61            for &e in set {
62                elem_to_sets[e].push(i);
63            }
64        }
65
66        let constraints: Vec<LinearConstraint> = elem_to_sets
67            .into_iter()
68            .filter(|sets| sets.len() > 1)
69            .map(|sets| {
70                let terms: Vec<(usize, i64)> = sets.into_iter().map(|i| (i, 1)).collect();
71                LinearConstraint::le(terms, 1)
72            })
73            .collect();
74
75        let objective: Vec<(usize, i64)> = self
76            .weights_ref()
77            .iter()
78            .enumerate()
79            .map(|(set, &weight)| (set, weight))
80            .collect();
81
82        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
83            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
84
85        Ok(ReductionSPToILP { target })
86    }
87}
88
89#[cfg(feature = "example-db")]
90pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
91    vec![crate::example_db::specs::RuleExampleSpec {
92        id: "maximumsetpacking_to_ilp",
93        build: || {
94            let source = MaximumSetPacking::new(vec![
95                vec![0, 1, 2],
96                vec![2, 3, 4],
97                vec![4, 5, 6],
98                vec![6, 7, 0],
99                vec![1, 3, 5],
100                vec![0, 4, 7],
101            ]);
102            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
103        },
104    }]
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/rules/maximumsetpacking_ilp.rs"]
109mod tests;
problemreductions/rules/maximumsetpacking_ilp.rs

problemreductions/rules/
maximumsetpacking_ilp.rs
