problemreductions/models/misc/
numerical_matching_with_target_sums.rs

1//! Numerical Matching with Target Sums problem implementation.
2//!
3//! Given two disjoint sets X and Y each with m elements, integer sizes
4//! s(x) for x ∈ X and s(y) for y ∈ Y, and a multiset of m target values
5//! B_1, …, B_m, decide whether X ∪ Y can be partitioned into m pairs,
6//! each containing one element from X and one from Y, such that the
7//! multiset of pair sums {s(x_i) + s(y_{π(i)})} equals the target multiset.
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: "NumericalMatchingWithTargetSums",
18        display_name: "Numerical Matching with Target Sums",
19        aliases: &["NMTS"],
20        dimensions: &[],
21        category: crate::registry::ProblemCategory::Misc,
22        module_path: module_path!(),
23        description: "Partition X∪Y into m pairs (one from X, one from Y) with pair sums matching targets",
24        fields: &[
25            FieldInfo { name: "sizes_x", type_name: "Vec<i64>", description: "Integer sizes for each element of X" },
26            FieldInfo { name: "sizes_y", type_name: "Vec<i64>", description: "Integer sizes for each element of Y" },
27            FieldInfo { name: "targets", type_name: "Vec<i64>", description: "Target sums for each pair" },
28        ],
29    }
30}
31
32#[derive(Debug, Clone, Serialize)]
33pub struct NumericalMatchingWithTargetSums {
34    sizes_x: Vec<i64>,
35    sizes_y: Vec<i64>,
36    targets: Vec<i64>,
37}
38
39impl NumericalMatchingWithTargetSums {
40    fn validate_inputs(
41        sizes_x: &[i64],
42        sizes_y: &[i64],
43        targets: &[i64],
44    ) -> Result<(), crate::registry::ConstructionError> {
45        let m = sizes_x.len();
46        if m == 0 {
47            return Err(
48                "NumericalMatchingWithTargetSums requires at least one element per set".into(),
49            );
50        }
51        if sizes_y.len() != m {
52            return Err(
53                "NumericalMatchingWithTargetSums requires sizes_x and sizes_y to have the same length"
54                    .into(),
55            );
56        }
57        if targets.len() != m {
58            return Err(
59                "NumericalMatchingWithTargetSums requires targets to have the same length as sizes_x"
60                    .into(),
61            );
62        }
63        Ok(())
64    }
65
66    pub fn try_new(
67        sizes_x: Vec<i64>,
68        sizes_y: Vec<i64>,
69        targets: Vec<i64>,
70    ) -> Result<Self, crate::registry::ConstructionError> {
71        Self::validate_inputs(&sizes_x, &sizes_y, &targets)?;
72        Ok(Self {
73            sizes_x,
74            sizes_y,
75            targets,
76        })
77    }
78
79    /// Create a new Numerical Matching with Target Sums instance.
80    ///
81    /// # Panics
82    ///
83    /// Panics if the input violates the NMTS invariants.
84    pub fn new(sizes_x: Vec<i64>, sizes_y: Vec<i64>, targets: Vec<i64>) -> Self {
85        Self::try_new(sizes_x, sizes_y, targets).unwrap_or_else(|message| panic!("{message}"))
86    }
87
88    /// Number of pairs (m).
89    pub fn num_pairs(&self) -> usize {
90        self.sizes_x.len()
91    }
92
93    /// Integer sizes for each element of X.
94    pub fn sizes_x(&self) -> &[i64] {
95        &self.sizes_x
96    }
97
98    /// Integer sizes for each element of Y.
99    pub fn sizes_y(&self) -> &[i64] {
100        &self.sizes_y
101    }
102
103    /// Target sums for each pair.
104    pub fn targets(&self) -> &[i64] {
105        &self.targets
106    }
107}
108
109#[derive(Deserialize)]
110struct NumericalMatchingWithTargetSumsData {
111    sizes_x: Vec<i64>,
112    sizes_y: Vec<i64>,
113    targets: Vec<i64>,
114}
115
116impl<'de> Deserialize<'de> for NumericalMatchingWithTargetSums {
117    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
118    where
119        D: Deserializer<'de>,
120    {
121        let data = NumericalMatchingWithTargetSumsData::deserialize(deserializer)?;
122        Self::try_new(data.sizes_x, data.sizes_y, data.targets).map_err(D::Error::custom)
123    }
124}
125
126impl Problem for NumericalMatchingWithTargetSums {
127    const NAME: &'static str = "NumericalMatchingWithTargetSums";
128    type Solution = Vec<usize>;
129    type Value = Or;
130
131    crate::problem_parameters![("num_pairs", num_pairs),];
132
133    fn variant() -> Vec<(&'static str, &'static str)> {
134        crate::variant_params![]
135    }
136
137    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
138        Ok({
139            Or({
140                let m = self.num_pairs();
141                if config.len() != m {
142                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
143                        "matching permutation length does not match the instance".into(),
144                    ));
145                }
146
147                if config.iter().any(|&index| index >= m) {
148                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
149                        "matching permutation contains an out-of-range index".into(),
150                    ));
151                }
152
153                // Check config is valid permutation of 0..m
154                let mut used = vec![false; m];
155                for &idx in config {
156                    if used[idx] {
157                        return Ok(Or(false));
158                    }
159                    used[idx] = true;
160                }
161
162                // Compute pair sums and compare multisets
163                let mut pair_sums: Vec<i128> = (0..m)
164                    .map(|i| i128::from(self.sizes_x[i]) + i128::from(self.sizes_y[config[i]]))
165                    .collect();
166                let mut sorted_targets: Vec<_> = self
167                    .targets
168                    .iter()
169                    .map(|&value| i128::from(value))
170                    .collect();
171                pair_sums.sort();
172                sorted_targets.sort();
173                pair_sums == sorted_targets
174            })
175        })
176    }
177}
178
179impl crate::solvers::BruteForceProblem for NumericalMatchingWithTargetSums {
180    fn dimensions(&self) -> Vec<usize> {
181        let m = self.num_pairs();
182        vec![m; m]
183    }
184}
185
186crate::declare_variants! {
187    default NumericalMatchingWithTargetSums => "2^num_pairs",
188}
189
190crate::register_brute_force! {
191    NumericalMatchingWithTargetSums,
192}
193
194#[cfg(feature = "example-db")]
195pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
196    vec![crate::example_db::specs::ModelExampleSpec {
197        id: "numerical_matching_with_target_sums",
198        instance: Box::new(NumericalMatchingWithTargetSums::new(
199            vec![1, 4, 7],
200            vec![2, 5, 3],
201            vec![3, 7, 12],
202        )),
203        optimal_config: serde_json::json!(vec![0, 2, 1]),
204        optimal_value: serde_json::json!(true),
205    }]
206}
207
208#[cfg(test)]
209#[path = "../../unit_tests/models/misc/numerical_matching_with_target_sums.rs"]
210mod tests;
problemreductions/models/misc/numerical_matching_with_target_sums.rs

problemreductions/models/misc/
numerical_matching_with_target_sums.rs
