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        while remainder.len() > 3 {
72            let positive_aux = next_element;
73            let negative_aux = next_element + 1;
74            next_element += 2;
75
76            normalized.push(vec![remainder[0], remainder[1], positive_aux]);
77            normalized.push(vec![positive_aux, negative_aux]);
78
79            let mut next_remainder = Vec::with_capacity(remainder.len() - 1);
80            next_remainder.push(negative_aux);
81            next_remainder.extend_from_slice(&remainder[2..]);
82            remainder = next_remainder;
83        }
84        normalized.push(remainder);
85    }
86
87    (next_element, normalized)
88}
89
90impl SetSplitting {
91    /// Create a new Set Splitting problem.
92    ///
93    /// # Panics
94    ///
95    /// Panics if any subset is empty, has fewer than 2 elements, or contains an
96    /// element outside the universe.
97    pub fn new(universe_size: usize, subsets: Vec<Vec<usize>>) -> Self {
98        Self::try_new(universe_size, subsets).unwrap_or_else(|err| panic!("{err}"))
99    }
100
101    /// Create a new Set Splitting problem, returning an error instead of panicking.
102    pub fn try_new(
103        universe_size: usize,
104        subsets: Vec<Vec<usize>>,
105    ) -> Result<Self, crate::registry::ConstructionError> {
106        for (i, subset) in subsets.iter().enumerate() {
107            if subset.len() < 2 {
108                return Err(format!(
109                    "Subset {} has {} element(s), expected at least 2",
110                    i,
111                    subset.len()
112                )
113                .into());
114            }
115            for &elem in subset {
116                if elem >= universe_size {
117                    return Err(format!(
118                        "Subset {} contains element {} which is outside universe of size {}",
119                        i, elem, universe_size
120                    )
121                    .into());
122                }
123            }
124        }
125        Ok(Self {
126            universe_size,
127            subsets,
128        })
129    }
130
131    /// Get the size of the universe.
132    pub fn universe_size(&self) -> usize {
133        self.universe_size
134    }
135
136    /// Get the number of subsets.
137    pub fn num_subsets(&self) -> usize {
138        self.subsets.len()
139    }
140
141    /// Get the subsets.
142    pub fn subsets(&self) -> &[Vec<usize>] {
143        &self.subsets
144    }
145
146    pub(crate) fn normalized_instance(&self) -> (usize, Vec<Vec<usize>>) {
147        normalize_subsets(self.universe_size, &self.subsets)
148    }
149
150    fn normalized_stats(&self) -> (usize, usize, usize) {
151        let (universe_size, subsets) = self.normalized_instance();
152        let size2 = subsets.iter().filter(|s| s.len() == 2).count();
153        let size3 = subsets.iter().filter(|s| s.len() == 3).count();
154        (universe_size, size2, size3)
155    }
156
157    /// Universe size after decomposing all subsets to size 2 or 3.
158    pub fn normalized_universe_size(&self) -> usize {
159        self.normalized_stats().0
160    }
161
162    /// Number of size-2 subsets after decomposition.
163    pub fn normalized_num_size2_subsets(&self) -> usize {
164        self.normalized_stats().1
165    }
166
167    /// Number of size-3 subsets after decomposition.
168    pub fn normalized_num_size3_subsets(&self) -> usize {
169        self.normalized_stats().2
170    }
171
172    /// Check if a coloring (config) splits all subsets.
173    pub fn is_valid_solution(
174        &self,
175        config: &[bool],
176    ) -> Result<bool, crate::traits::EvaluationError> {
177        if config.len() != self.universe_size {
178            return Err(crate::traits::EvaluationError::InvalidConfiguration(
179                "partition assignment length does not match the universe".into(),
180            ));
181        }
182        Ok(self.subsets.iter().all(|subset| {
183            let has_zero = subset.iter().any(|&element| !config[element]);
184            let has_one = subset.iter().any(|&element| config[element]);
185            has_zero && has_one
186        }))
187    }
188}
189
190impl Problem for SetSplitting {
191    const NAME: &'static str = "SetSplitting";
192    type Solution = Vec<bool>;
193    type Value = crate::types::Or;
194
195    crate::problem_parameters![
196        ("num_subsets", num_subsets),
197        ("universe_size", universe_size),
198    ];
199
200    fn evaluate(
201        &self,
202        config: &Self::Solution,
203    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
204        Ok(crate::types::Or(self.is_valid_solution(config)?))
205    }
206
207    fn variant() -> Vec<(&'static str, &'static str)> {
208        crate::variant_params![]
209    }
210}
211
212impl crate::solvers::BruteForceProblem for SetSplitting {
213    fn dimensions(&self) -> Vec<usize> {
214        vec![2; self.universe_size]
215    }
216}
217
218crate::declare_variants! {
219    default SetSplitting => "2^universe_size",
220}
221
222crate::register_brute_force! {
223    SetSplitting decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
224}
225
226#[derive(Debug, Clone, Deserialize)]
227struct SetSplittingDef {
228    universe_size: usize,
229    subsets: Vec<Vec<usize>>,
230}
231
232impl TryFrom<SetSplittingDef> for SetSplitting {
233    type Error = crate::registry::ConstructionError;
234
235    fn try_from(value: SetSplittingDef) -> Result<Self, Self::Error> {
236        Self::try_new(value.universe_size, value.subsets)
237    }
238}
239
240#[cfg(feature = "example-db")]
241pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
242    vec![crate::example_db::specs::ModelExampleSpec {
243        id: "set_splitting",
244        instance: Box::new(SetSplitting::new(
245            6,
246            vec![vec![0, 1, 2], vec![2, 3, 4], vec![0, 4, 5], vec![1, 3, 5]],
247        )),
248        // config[i]=0 means element i in S1, config[i]=1 means element i in S2
249        // S1={1,3,4}, S2={0,2,5} → config [1,0,1,0,0,1]
250        optimal_config: serde_json::json!(vec![true, false, true, false, false, true]),
251        optimal_value: serde_json::json!(true),
252    }]
253}
254
255#[cfg(test)]
256#[path = "../../unit_tests/models/set/set_splitting.rs"]
257mod tests;
problemreductions/models/set/set_splitting.rs

problemreductions/models/set/
set_splitting.rs
