problemreductions/rules/
setsplitting_ilp.rs

1//! Reduction from SetSplitting to ILP (Integer Linear Programming).
2//!
3//! Binary variable $x_i \in \{0,1\}$ per universe element: 0 means element $i$
4//! is placed in part $S_1$, 1 means it is placed in part $S_2$.
5//!
6//! For each subset $C = \{i_1, \ldots, i_k\}$ we need:
7//! - At least one element in $S_2$: $\sum_{j \in C} x_j \geq 1$
8//! - At least one element in $S_1$: $\sum_{j \in C} x_j \leq k - 1$
9//!
10//! Objective: feasibility (minimize 0).
11
12use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
13use crate::models::set::SetSplitting;
14use crate::reduction;
15use crate::rules::traits::{ReduceTo, ReductionResult};
16
17/// Result of reducing SetSplitting to ILP.
18#[derive(Debug, Clone)]
19pub struct ReductionSetSplittingToILP {
20    target: ILP<bool>,
21}
22
23impl ReductionResult for ReductionSetSplittingToILP {
24    type Source = SetSplitting;
25    type Target = ILP<bool>;
26
27    fn target_problem(&self) -> &ILP<bool> {
28        &self.target
29    }
30
31    fn extract_solution(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_witness(
36            self.target_problem(),
37            target_solution,
38            |value| value.value.is_some(),
39            "target ILP assignment is infeasible",
40        )?;
41
42        Ok(target_solution.iter().map(|&value| value == 1).collect())
43    }
44}
45
46#[crate::aggregate_reduction(ilp_feasibility)]
47impl crate::rules::AggregateReductionResult for ReductionSetSplittingToILP {}
48
49#[reduction(transform = {
50    exact {
51        num_vars = "universe_size",
52        num_constraints = "2 * num_subsets",
53    },
54    upper_bound {
55        max_constraint_magnitude_bits = "universe_size + 1",
56        num_nonzeros = "universe_size * (2 * num_subsets)",
57    },
58})]
59impl ReduceTo<ILP<bool>> for SetSplitting {
60    type Result = ReductionSetSplittingToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let num_vars = self.universe_size();
64        let mut constraints = Vec::new();
65
66        for subset in self.subsets() {
67            let mut subset = subset.clone();
68            subset.sort_unstable();
69            subset.dedup();
70            let terms: Vec<(usize, i64)> = subset.iter().map(|&e| (e, 1)).collect();
71            let k = <Self as ReduceTo<ILP<bool>>>::exact_i64(
72                subset.len() - 1,
73                "encoding the split-set cardinality",
74            )?;
75
76            // At least one element in S2: sum >= 1
77            constraints.push(LinearConstraint::ge(terms.clone(), 1));
78
79            // At least one element in S1: sum <= |S| - 1
80            constraints.push(LinearConstraint::le(terms, k));
81        }
82
83        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
84            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
85        Ok(ReductionSetSplittingToILP { 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: "setsplitting_to_ilp",
93        build: || {
94            let source = SetSplitting::new(
95                6,
96                vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 4, 5], vec![1, 3, 5]],
97            );
98            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
99        },
100    }]
101}
102
103#[cfg(test)]
104#[path = "../unit_tests/rules/setsplitting_ilp.rs"]
105mod tests;
problemreductions/rules/setsplitting_ilp.rs

problemreductions/rules/
setsplitting_ilp.rs
