problemreductions/models/misc/
ensemble_computation.rs

1//! Ensemble Computation problem implementation.
2
3use crate::registry::{FieldInfo, ProblemSchemaEntry};
4use crate::traits::Problem;
5use crate::types::Min;
6use serde::{Deserialize, Serialize};
7
8inventory::submit! {
9    ProblemSchemaEntry {
10        name: "EnsembleComputation",
11        display_name: "Ensemble Computation",
12        aliases: &[],
13        dimensions: &[],
14        category: crate::registry::ProblemCategory::Misc,
15        module_path: module_path!(),
16        description: "Find the minimum-length sequence of disjoint unions that builds all required subsets",
17        fields: &[
18            FieldInfo { name: "universe_size", type_name: "usize", description: "Number of elements in the universe A" },
19            FieldInfo { name: "subsets", type_name: "Vec<Vec<usize>>", description: "Required subsets that must appear among the computed z_i values" },
20            FieldInfo { name: "budget", type_name: "usize", description: "Maximum number of union operations J" },
21        ],
22    }
23}
24
25#[derive(Debug, Clone, Serialize, Deserialize)]
26#[serde(try_from = "EnsembleComputationDef")]
27pub struct EnsembleComputation {
28    universe_size: usize,
29    subsets: Vec<Vec<usize>>,
30    budget: usize,
31}
32
33impl EnsembleComputation {
34    pub fn new(universe_size: usize, subsets: Vec<Vec<usize>>, budget: usize) -> Self {
35        Self::try_new(universe_size, subsets, budget).unwrap_or_else(|err| panic!("{err}"))
36    }
37
38    /// Create with an automatically derived search-space bound.
39    ///
40    /// The default budget is the sum of all subset sizes (worst-case without
41    /// intermediate-set reuse). This is always sufficient for the optimal
42    /// solution to fit within the search space.
43    pub fn with_default_budget(universe_size: usize, subsets: Vec<Vec<usize>>) -> Self {
44        let budget = Self::default_budget(&subsets);
45        Self::new(universe_size, subsets, budget)
46    }
47
48    /// Compute a default search-space bound from the subsets.
49    ///
50    /// Returns the sum of all subset sizes, clamped to at least 1.
51    pub fn default_budget(subsets: &[Vec<usize>]) -> usize {
52        subsets.iter().map(|s| s.len()).sum::<usize>().max(1)
53    }
54
55    pub fn try_new(
56        universe_size: usize,
57        subsets: Vec<Vec<usize>>,
58        budget: usize,
59    ) -> Result<Self, crate::registry::ConstructionError> {
60        if budget == 0 {
61            return Err("budget must be positive".to_string().into());
62        }
63        let subsets = subsets
64            .into_iter()
65            .enumerate()
66            .map(|(subset_index, subset)| {
67                Self::normalize_subset(universe_size, subset).ok_or_else(|| {
68                    format!(
69                        "subset {subset_index} contains element outside universe of size {universe_size}"
70                    )
71                })
72            })
73            .collect::<Result<Vec<_>, _>>()?;
74        Ok(Self {
75            universe_size,
76            subsets,
77            budget,
78        })
79    }
80
81    pub fn universe_size(&self) -> usize {
82        self.universe_size
83    }
84
85    pub fn subsets(&self) -> &[Vec<usize>] {
86        &self.subsets
87    }
88
89    pub fn num_subsets(&self) -> usize {
90        self.subsets.len()
91    }
92
93    pub fn budget(&self) -> usize {
94        self.budget
95    }
96
97    fn normalize_subset(universe_size: usize, mut subset: Vec<usize>) -> Option<Vec<usize>> {
98        if subset.iter().any(|&element| element >= universe_size) {
99            return None;
100        }
101        subset.sort_unstable();
102        subset.dedup();
103        Some(subset)
104    }
105
106    fn decode_operand(&self, operand: usize, computed: &[Vec<usize>]) -> Option<Vec<usize>> {
107        if operand < self.universe_size {
108            return Some(vec![operand]);
109        }
110        computed.get(operand - self.universe_size).cloned()
111    }
112
113    fn are_disjoint(left: &[usize], right: &[usize]) -> bool {
114        let mut i = 0;
115        let mut j = 0;
116
117        while i < left.len() && j < right.len() {
118            match left[i].cmp(&right[j]) {
119                std::cmp::Ordering::Less => i += 1,
120                std::cmp::Ordering::Greater => j += 1,
121                std::cmp::Ordering::Equal => return false,
122            }
123        }
124
125        true
126    }
127
128    fn union_disjoint(left: &[usize], right: &[usize]) -> Vec<usize> {
129        let mut union = Vec::with_capacity(left.len() + right.len());
130        let mut i = 0;
131        let mut j = 0;
132
133        while i < left.len() && j < right.len() {
134            if left[i] < right[j] {
135                union.push(left[i]);
136                i += 1;
137            } else {
138                union.push(right[j]);
139                j += 1;
140            }
141        }
142
143        union.extend_from_slice(&left[i..]);
144        union.extend_from_slice(&right[j..]);
145        union
146    }
147
148    fn required_subsets(&self) -> Option<Vec<Vec<usize>>> {
149        self.subsets
150            .iter()
151            .cloned()
152            .map(|subset| Self::normalize_subset(self.universe_size, subset))
153            .collect()
154    }
155
156    fn all_required_subsets_present(
157        required_subsets: &[Vec<usize>],
158        computed: &[Vec<usize>],
159    ) -> bool {
160        required_subsets
161            .iter()
162            .all(|subset| computed.iter().any(|candidate| candidate == subset))
163    }
164}
165
166impl Problem for EnsembleComputation {
167    const NAME: &'static str = "EnsembleComputation";
168    type Solution = Vec<usize>;
169    type Value = Min<i64>;
170
171    crate::problem_parameters![
172        ("budget", budget),
173        ("num_subsets", num_subsets),
174        ("universe_size", universe_size),
175    ];
176
177    fn evaluate(
178        &self,
179        config: &Self::Solution,
180    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
181        Ok({
182            if config.len() != 2 * self.budget {
183                return Err(crate::traits::EvaluationError::InvalidConfiguration(
184                    "ensemble program length does not match the operation budget".into(),
185                ));
186            }
187
188            let Some(required_subsets) = self.required_subsets() else {
189                return Ok(Min(None));
190            };
191            if required_subsets.is_empty() {
192                return Ok(Min(Some(0)));
193            }
194
195            let mut computed = Vec::with_capacity(self.budget);
196            for step in 0..self.budget {
197                let left_operand = config[2 * step];
198                let right_operand = config[2 * step + 1];
199
200                let Some(left) = self.decode_operand(left_operand, &computed) else {
201                    return Ok(Min(None));
202                };
203                let Some(right) = self.decode_operand(right_operand, &computed) else {
204                    return Ok(Min(None));
205                };
206
207                if !Self::are_disjoint(&left, &right) {
208                    return Ok(Min(None));
209                }
210
211                computed.push(Self::union_disjoint(&left, &right));
212                if Self::all_required_subsets_present(&required_subsets, &computed) {
213                    return Ok(Min(Some(i64::try_from(step + 1).map_err(|_| {
214                        crate::traits::EvaluationError::IntegerOverflow(
215                            "converting union-operation count to i64".into(),
216                        )
217                    })?)));
218                }
219            }
220
221            Min(None)
222        })
223    }
224
225    fn variant() -> Vec<(&'static str, &'static str)> {
226        crate::variant_params![]
227    }
228}
229
230impl crate::solvers::BruteForceProblem for EnsembleComputation {
231    fn dimensions(&self) -> Vec<usize> {
232        vec![self.universe_size + self.budget; 2 * self.budget]
233    }
234}
235
236crate::declare_variants! {
237    default EnsembleComputation => "(universe_size + budget)^(2 * budget)",
238}
239
240crate::register_brute_force! {
241    EnsembleComputation,
242}
243
244#[derive(Debug, Clone, Deserialize)]
245struct EnsembleComputationDef {
246    universe_size: usize,
247    subsets: Vec<Vec<usize>>,
248    budget: usize,
249}
250
251impl TryFrom<EnsembleComputationDef> for EnsembleComputation {
252    type Error = crate::registry::ConstructionError;
253
254    fn try_from(value: EnsembleComputationDef) -> Result<Self, Self::Error> {
255        Self::try_new(value.universe_size, value.subsets, value.budget)
256    }
257}
258
259#[cfg(feature = "example-db")]
260pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
261    // Keep the canonical example small enough for the example-db optimality check to solve
262    // it via brute force, while still demonstrating reuse of a previously computed set.
263    vec![crate::example_db::specs::ModelExampleSpec {
264        id: "ensemble_computation",
265        instance: Box::new(EnsembleComputation::new(
266            3,
267            vec![vec![0, 1], vec![0, 1, 2]],
268            2,
269        )),
270        optimal_config: serde_json::json!(vec![0, 1, 3, 2]),
271        optimal_value: serde_json::json!(2),
272    }]
273}
274
275#[cfg(test)]
276#[path = "../../unit_tests/models/misc/ensemble_computation.rs"]
277mod tests;
problemreductions/models/misc/ensemble_computation.rs

problemreductions/models/misc/
ensemble_computation.rs
