problemreductions/models/misc/
numerical_3_dimensional_matching.rs

1//! Numerical 3-Dimensional Matching (N3DM) problem implementation.
2//!
3//! Given disjoint sets W, X, Y each with m elements, positive integer sizes
4//! s(a), and a positive integer bound B where the total sum
5//! equals mB.  Decide whether W ∪ X ∪ Y can be partitioned into m triples,
6//! each containing one element from W, X, and Y, with each triple summing
7//! to exactly B.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry};
10use crate::traits::Problem;
11use crate::types::Or;
12use serde::de::Error as _;
13use serde::{Deserialize, Deserializer, Serialize};
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "Numerical3DimensionalMatching",
18        display_name: "Numerical 3-Dimensional Matching",
19        aliases: &["N3DM"],
20        dimensions: &[],
21        category: crate::registry::ProblemCategory::Misc,
22        module_path: module_path!(),
23        description: "Partition W∪X∪Y into m triples (one from each set) each summing to B",
24        fields: &[
25            FieldInfo { name: "sizes_w", type_name: "Vec<i64>", description: "Positive integer sizes for each element of W" },
26            FieldInfo { name: "sizes_x", type_name: "Vec<i64>", description: "Positive integer sizes for each element of X" },
27            FieldInfo { name: "sizes_y", type_name: "Vec<i64>", description: "Positive integer sizes for each element of Y" },
28            FieldInfo { name: "bound", type_name: "i64", description: "Target sum B for each triple" },
29        ],
30    }
31}
32
33#[derive(Debug, Clone, Serialize)]
34pub struct Numerical3DimensionalMatching {
35    sizes_w: Vec<i64>,
36    sizes_x: Vec<i64>,
37    sizes_y: Vec<i64>,
38    bound: i64,
39}
40
41impl Numerical3DimensionalMatching {
42    fn validate_inputs(
43        sizes_w: &[i64],
44        sizes_x: &[i64],
45        sizes_y: &[i64],
46        bound: i64,
47    ) -> Result<(), crate::registry::ConstructionError> {
48        let m = sizes_w.len();
49        if m == 0 {
50            return Err(
51                "Numerical3DimensionalMatching requires at least one element per set".into(),
52            );
53        }
54        if sizes_x.len() != m || sizes_y.len() != m {
55            return Err(
56                "Numerical3DimensionalMatching requires all three sets to have the same size"
57                    .into(),
58            );
59        }
60        if bound <= 0 {
61            return Err("Numerical3DimensionalMatching requires a positive bound"
62                .to_string()
63                .into());
64        }
65
66        for &size in sizes_w.iter().chain(sizes_x.iter()).chain(sizes_y.iter()) {
67            if size <= 0 {
68                return Err("All sizes must be positive (> 0)".to_string().into());
69            }
70        }
71
72        let total_sum = sizes_w
73            .iter()
74            .chain(sizes_x.iter())
75            .chain(sizes_y.iter())
76            .try_fold(0_i64, |total, &size| total.checked_add(size))
77            .ok_or("total size sum exceeds i64 range")?;
78        let group_count = i64::try_from(m).map_err(|_| "group count exceeds i64 range")?;
79        let expected_sum = bound
80            .checked_mul(group_count)
81            .ok_or("m * bound exceeds i64 range")?;
82        if total_sum != expected_sum {
83            return Err("Total sum of all sizes must equal m * bound"
84                .to_string()
85                .into());
86        }
87        Ok(())
88    }
89
90    pub fn try_new(
91        sizes_w: Vec<i64>,
92        sizes_x: Vec<i64>,
93        sizes_y: Vec<i64>,
94        bound: i64,
95    ) -> Result<Self, crate::registry::ConstructionError> {
96        Self::validate_inputs(&sizes_w, &sizes_x, &sizes_y, bound)?;
97        Ok(Self {
98            sizes_w,
99            sizes_x,
100            sizes_y,
101            bound,
102        })
103    }
104
105    /// Create a new Numerical 3-Dimensional Matching instance.
106    ///
107    /// # Panics
108    ///
109    /// Panics if the input violates the N3DM invariants.
110    pub fn new(sizes_w: Vec<i64>, sizes_x: Vec<i64>, sizes_y: Vec<i64>, bound: i64) -> Self {
111        Self::try_new(sizes_w, sizes_x, sizes_y, bound)
112            .unwrap_or_else(|message| panic!("{message}"))
113    }
114
115    pub fn sizes_w(&self) -> &[i64] {
116        &self.sizes_w
117    }
118
119    pub fn sizes_x(&self) -> &[i64] {
120        &self.sizes_x
121    }
122
123    pub fn sizes_y(&self) -> &[i64] {
124        &self.sizes_y
125    }
126
127    pub fn bound(&self) -> i64 {
128        self.bound
129    }
130
131    pub fn num_groups(&self) -> usize {
132        self.sizes_w.len()
133    }
134}
135
136#[derive(Deserialize)]
137struct Numerical3DimensionalMatchingData {
138    sizes_w: Vec<i64>,
139    sizes_x: Vec<i64>,
140    sizes_y: Vec<i64>,
141    bound: i64,
142}
143
144impl<'de> Deserialize<'de> for Numerical3DimensionalMatching {
145    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
146    where
147        D: Deserializer<'de>,
148    {
149        let data = Numerical3DimensionalMatchingData::deserialize(deserializer)?;
150        Self::try_new(data.sizes_w, data.sizes_x, data.sizes_y, data.bound)
151            .map_err(D::Error::custom)
152    }
153}
154
155impl Problem for Numerical3DimensionalMatching {
156    const NAME: &'static str = "Numerical3DimensionalMatching";
157    type Solution = Vec<usize>;
158    type Value = Or;
159
160    crate::problem_parameters![("bound", bound), ("num_groups", num_groups),];
161
162    fn variant() -> Vec<(&'static str, &'static str)> {
163        crate::variant_params![]
164    }
165
166    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
167        Ok({
168            Or({
169                let m = self.num_groups();
170                if config.len() != 2 * m {
171                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
172                        "matching permutation length does not match the instance".into(),
173                    ));
174                }
175
176                if config.iter().any(|&index| index >= m) {
177                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
178                        "matching permutation contains an out-of-range index".into(),
179                    ));
180                }
181
182                // First m values: assignment of X-elements to W-elements (must be a permutation)
183                let x_perm = &config[..m];
184                // Second m values: assignment of Y-elements to W-elements (must be a permutation)
185                let y_perm = &config[m..];
186
187                // Check that both are valid permutations of 0..m
188                let mut x_used = vec![false; m];
189                let mut y_used = vec![false; m];
190
191                for i in 0..m {
192                    if x_used[x_perm[i]] || y_used[y_perm[i]] {
193                        return Ok(Or(false));
194                    }
195                    x_used[x_perm[i]] = true;
196                    y_used[y_perm[i]] = true;
197                }
198
199                // Check that each triple sums to B
200                for i in 0..m {
201                    let sum = self.sizes_w[i]
202                        .checked_add(self.sizes_x[x_perm[i]])
203                        .and_then(|sum| sum.checked_add(self.sizes_y[y_perm[i]]))
204                        .ok_or_else(|| {
205                            crate::traits::EvaluationError::IntegerOverflow(
206                                "summing numerical three-dimensional matching triple".into(),
207                            )
208                        })?;
209                    if sum != self.bound {
210                        return Ok(Or(false));
211                    }
212                }
213                true
214            })
215        })
216    }
217}
218
219impl crate::solvers::BruteForceProblem for Numerical3DimensionalMatching {
220    fn dimensions(&self) -> Vec<usize> {
221        vec![self.num_groups(); 2 * self.num_groups()]
222    }
223}
224
225crate::declare_variants! {
226    default Numerical3DimensionalMatching => "num_groups^(2 * num_groups)",
227}
228
229crate::register_brute_force! {
230    Numerical3DimensionalMatching,
231}
232
233#[cfg(feature = "example-db")]
234pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
235    vec![crate::example_db::specs::ModelExampleSpec {
236        id: "numerical_3_dimensional_matching",
237        instance: Box::new(Numerical3DimensionalMatching::new(
238            vec![4, 5],
239            vec![4, 5],
240            vec![5, 7],
241            15,
242        )),
243        optimal_config: serde_json::json!(vec![0, 1, 1, 0]),
244        optimal_value: serde_json::json!(true),
245    }]
246}
247
248#[cfg(test)]
249#[path = "../../unit_tests/models/misc/numerical_3_dimensional_matching.rs"]
250mod tests;
problemreductions/models/misc/numerical_3_dimensional_matching.rs

problemreductions/models/misc/
numerical_3_dimensional_matching.rs
