problemreductions/models/set/
set_splitting.rs

1//! Set Splitting problem implementation.
2//!
3//! Set Splitting asks whether a universe can be 2-colored so that every
4//! specified subset is non-monochromatic (contains both colors).
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use serde::{Deserialize, Serialize};
9
10inventory::submit! {
11    ProblemSchemaEntry {
12        name: "SetSplitting",
13        display_name: "Set Splitting",
14        aliases: &[],
15        dimensions: &[],
16        category: crate::registry::ProblemCategory::Set,
17        module_path: module_path!(),
18        description: "Partition a universe into two parts so that every subset is non-monochromatic",
19        fields: &[
20            FieldInfo { name: "universe_size", type_name: "usize", description: "universe_size" },
21            FieldInfo { name: "subsets", type_name: "Vec<Vec<usize>>", description: "Subsets that must each contain elements from both parts" },
22        ],
23    }
24}
25
26/// The Set Splitting problem.
27///
28/// Given a finite universe $U = \{0, \ldots, n-1\}$ and a collection
29/// $\mathcal{C}$ of subsets of $U$, decide whether there exists a
30/// 2-coloring (partition into $S_1$ and $S_2$) of $U$ such that every
31/// subset in $\mathcal{C}$ is non-monochromatic, i.e., contains at
32/// least one element from each part.
33///
34/// # Example
35///
36/// ```
37/// use problemreductions::models::set::SetSplitting;
38/// use problemreductions::{Problem, BruteForce};
39///
40/// // Universe {0,1,2,3,4,5}, subsets that all must be split
41/// let problem = SetSplitting::new(6, vec![
42///     vec![0, 1, 2],
43///     vec![2, 3, 4],
44///     vec![0, 4, 5],
45///     vec![1, 3, 5],
46/// ]);
47///
48/// let solver = BruteForce::new();
49/// let witness = solver.solve(&problem).unwrap();
50/// assert!(witness.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53#[serde(try_from = "SetSplittingDef")]
54pub struct SetSplitting {
55    /// Size of the universe.
56    universe_size: usize,
57    /// Subsets that must each contain elements from both parts.
58    subsets: Vec<Vec<usize>>,
59}
60
61fn normalize_subsets(universe_size: usize, subsets: &[Vec<usize>]) -> (usize, Vec<Vec<usize>>) {
62    let mut next_element = universe_size;
63    let total_excess: usize = subsets
64        .iter()
65        .map(|subset| subset.len().saturating_sub(3))
66        .sum();
67    let mut normalized = Vec::with_capacity(subsets.len() + 2 * total_excess);
68
69    for subset in subsets {
70        let mut remainder = subset.clone();
71        // Repeated occurrences represent the same set element.
72        remainder.sort_unstable();
73        remainder.dedup();
74        while remainder.len() > 3 {
75            let positive_aux = next_element;
76            let negative_aux = next_element + 1;
77            next_element += 2;
78
79            normalized.push(vec![remainder[0], remainder[1], positive_aux]);
80            normalized.push(vec![positive_aux, negative_aux]);
81
82            let mut next_remainder = Vec::with_capacity(remainder.len() - 1);
83            next_remainder.push(negative_aux);
84            next_remainder.extend_from_slice(&remainder[2..]);
85            remainder = next_remainder;
86        }
87        normalized.push(remainder);
88    }
89
90    (next_element, normalized)
91}
92
93impl SetSplitting {
94    /// Create a new Set Splitting problem.
95    ///
96    /// # Panics
97    ///
98    /// Panics if any subset is empty, has fewer than 2 elements, or contains an
99    /// element outside the universe.
100    pub fn new(universe_size: usize, subsets: Vec<Vec<usize>>) -> Self {
101        Self::try_new(universe_size, subsets).unwrap_or_else(|err| panic!("{err}"))
102    }
103
104    /// Create a new Set Splitting problem, returning an error instead of panicking.
105    pub fn try_new(
106        universe_size: usize,
107        subsets: Vec<Vec<usize>>,
108    ) -> Result<Self, crate::registry::ConstructionError> {
109        for (i, subset) in subsets.iter().enumerate() {
110            if subset.len() < 2 {
111                return Err(format!(
112                    "Subset {} has {} element(s), expected at least 2",
113                    i,
114                    subset.len()
115                )
116                .into());
117            }
118            for &elem in subset {
119                if elem >= universe_size {
120                    return Err(format!(
121                        "Subset {} contains element {} which is outside universe of size {}",
122                        i, elem, universe_size
123                    )
124                    .into());
125                }
126            }
127        }
128        Ok(Self {
129            universe_size,
130            subsets,
131        })
132    }
133
134    /// Get the size of the universe.
135    pub fn universe_size(&self) -> usize {
136        self.universe_size
137    }
138
139    /// Get the number of subsets.
140    pub fn num_subsets(&self) -> usize {
141        self.subsets.len()
142    }
143
144    /// Get the subsets.
145    pub fn subsets(&self) -> &[Vec<usize>] {
146        &self.subsets
147    }
148
149    pub(crate) fn normalized_instance(&self) -> (usize, Vec<Vec<usize>>) {
150        normalize_subsets(self.universe_size, &self.subsets)
151    }
152
153    fn normalized_stats(&self) -> (usize, usize, usize) {
154        let (universe_size, subsets) = self.normalized_instance();
155        let size2 = subsets.iter().filter(|s| s.len() == 2).count();
156        let size3 = subsets.iter().filter(|s| s.len() == 3).count();
157        (universe_size, size2, size3)
158    }
159
160    /// Universe size after deduplicating subsets and decomposing sizes above 3.
161    pub fn normalized_universe_size(&self) -> usize {
162        self.normalized_stats().0
163    }
164
165    /// Number of size-2 subsets after decomposition.
166    pub fn normalized_num_size2_subsets(&self) -> usize {
167        self.normalized_stats().1
168    }
169
170    /// Number of size-3 subsets after decomposition.
171    pub fn normalized_num_size3_subsets(&self) -> usize {
172        self.normalized_stats().2
173    }
174
175    /// Check if a coloring (config) splits all subsets.
176    pub fn is_valid_solution(
177        &self,
178        config: &[bool],
179    ) -> Result<bool, crate::traits::EvaluationError> {
180        if config.len() != self.universe_size {
181            return Err(crate::traits::EvaluationError::InvalidConfiguration(
182                "partition assignment length does not match the universe".into(),
183            ));
184        }
185        Ok(self.subsets.iter().all(|subset| {
186            let has_zero = subset.iter().any(|&element| !config[element]);
187            let has_one = subset.iter().any(|&element| config[element]);
188            has_zero && has_one
189        }))
190    }
191}
192
193impl Problem for SetSplitting {
194    const NAME: &'static str = "SetSplitting";
195    type Solution = Vec<bool>;
196    type Value = crate::types::Or;
197
198    crate::problem_parameters![
199        ("num_subsets", num_subsets),
200        ("universe_size", universe_size),
201    ];
202
203    fn evaluate(
204        &self,
205        config: &Self::Solution,
206    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
207        Ok(crate::types::Or(self.is_valid_solution(config)?))
208    }
209
210    fn variant() -> Vec<(&'static str, &'static str)> {
211        crate::variant_params![]
212    }
213}
214
215impl crate::solvers::BruteForceProblem for SetSplitting {
216    fn dimensions(&self) -> Vec<usize> {
217        vec![2; self.universe_size]
218    }
219}
220
221crate::declare_variants! {
222    default SetSplitting => "2^universe_size",
223}
224
225crate::register_brute_force! {
226    SetSplitting decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
227}
228
229#[derive(Debug, Clone, Deserialize)]
230struct SetSplittingDef {
231    universe_size: usize,
232    subsets: Vec<Vec<usize>>,
233}
234
235impl TryFrom<SetSplittingDef> for SetSplitting {
236    type Error = crate::registry::ConstructionError;
237
238    fn try_from(value: SetSplittingDef) -> Result<Self, Self::Error> {
239        Self::try_new(value.universe_size, value.subsets)
240    }
241}
242
243#[cfg(feature = "example-db")]
244pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
245    vec![crate::example_db::specs::ModelExampleSpec {
246        id: "set_splitting",
247        instance: Box::new(SetSplitting::new(
248            6,
249            vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 4, 5], vec![1, 3, 5]],
250        )),
251        // config[i]=0 means element i in S1, config[i]=1 means element i in S2
252        // S1={1,3,4}, S2={0,2,5} → config [1,0,1,0,0,1]
253        optimal_config: serde_json::json!(vec![true, false, true, false, false, true]),
254        optimal_value: serde_json::json!(true),
255    }]
256}
257
258#[cfg(test)]
259#[path = "../../unit_tests/models/set/set_splitting.rs"]
260mod tests;
problemreductions/models/set/set_splitting.rs

problemreductions/models/set/
set_splitting.rs
