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(transform = {
43    exact {
44        num_vars = "num_sets",
45    },
46    upper_bound {
47        max_constraint_magnitude_bits = "1",
48        num_constraints = "universe_size",
49        num_nonzeros = "num_sets * universe_size",
50    },
51})]
52impl ReduceTo<ILP<bool>> for MaximumSetPacking<i64> {
53    type Result = ReductionSPToILP;
54
55    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
56        let num_vars = self.num_sets();
57
58        // Build element-to-sets mapping, then create one constraint per element
59        let universe = self.universe_size();
60        let mut elem_to_sets: Vec<Vec<usize>> = vec![Vec::new(); universe];
61        for (i, set) in self.sets().iter().enumerate() {
62            for &e in set {
63                elem_to_sets[e].push(i);
64            }
65        }
66        // Each set contributes once per element, irrespective of repeated input entries.
67        for sets in &mut elem_to_sets {
68            sets.dedup();
69        }
70
71        let constraints: Vec<LinearConstraint> = elem_to_sets
72            .into_iter()
73            .filter(|sets| sets.len() > 1)
74            .map(|sets| {
75                let terms: Vec<(usize, i64)> = sets.into_iter().map(|i| (i, 1)).collect();
76                LinearConstraint::le(terms, 1)
77            })
78            .collect();
79
80        let objective: Vec<(usize, i64)> = self
81            .weights_ref()
82            .iter()
83            .enumerate()
84            .map(|(set, &weight)| (set, weight))
85            .collect();
86
87        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
88            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
89
90        Ok(ReductionSPToILP { target })
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: "maximumsetpacking_to_ilp",
98        build: || {
99            let source = MaximumSetPacking::new(vec![
100                vec![0, 1, 2],
101                vec![2, 3, 4],
102                vec![4, 5, 6],
103                vec![6, 7, 0],
104                vec![1, 3, 5],
105                vec![0, 4, 7],
106            ]);
107            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/maximumsetpacking_ilp.rs"]
114mod tests;
problemreductions/rules/maximumsetpacking_ilp.rs

problemreductions/rules/
maximumsetpacking_ilp.rs
