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<i32>;
26    type Target = ILP<bool>;
27
28    fn target_problem(&self) -> &ILP<bool> {
29        &self.target
30    }
31
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution.to_vec()
34    }
35}
36
37#[reduction(
38    overhead = {
39        num_vars = "num_sets",
40        num_constraints = "universe_size",
41    }
42)]
43impl ReduceTo<ILP<bool>> for MaximumSetPacking<i32> {
44    type Result = ReductionSPToILP;
45
46    fn reduce_to(&self) -> Self::Result {
47        let num_vars = self.num_sets();
48
49        // Build element-to-sets mapping, then create one constraint per element
50        let universe = self.universe_size();
51        let mut elem_to_sets: Vec<Vec<usize>> = vec![Vec::new(); universe];
52        for (i, set) in self.sets().iter().enumerate() {
53            for &e in set {
54                elem_to_sets[e].push(i);
55            }
56        }
57
58        let constraints: Vec<LinearConstraint> = elem_to_sets
59            .into_iter()
60            .filter(|sets| sets.len() > 1)
61            .map(|sets| {
62                let terms: Vec<(usize, f64)> = sets.into_iter().map(|i| (i, 1.0)).collect();
63                LinearConstraint::le(terms, 1.0)
64            })
65            .collect();
66
67        let objective: Vec<(usize, f64)> = self
68            .weights_ref()
69            .iter()
70            .enumerate()
71            .map(|(i, &w)| (i, w as f64))
72            .collect();
73
74        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
75
76        ReductionSPToILP { target }
77    }
78}
79
80#[cfg(test)]
81#[path = "../unit_tests/rules/maximumsetpacking_ilp.rs"]
82mod tests;
problemreductions/rules/maximumsetpacking_ilp.rs

problemreductions/rules/
maximumsetpacking_ilp.rs
