problemreductions/models/misc/

numerical_matching_with_target_sums.rs

//! Numerical Matching with Target Sums problem implementation.
//!
//! Given two disjoint sets X and Y each with m elements, integer sizes
//! s(x) for x ∈ X and s(y) for y ∈ Y, and a multiset of m target values
//! B_1, …, B_m, decide whether X ∪ Y can be partitioned into m pairs,
//! each containing one element from X and one from Y, such that the
//! multiset of pair sums {s(x_i) + s(y_{π(i)})} equals the target multiset.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use crate::types::Or;
use serde::de::Error as _;
use serde::{Deserialize, Deserializer, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "NumericalMatchingWithTargetSums",
        display_name: "Numerical Matching with Target Sums",
        aliases: &["NMTS"],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Partition X∪Y into m pairs (one from X, one from Y) with pair sums matching targets",
        fields: &[
            FieldInfo { name: "sizes_x", type_name: "Vec<i64>", description: "Integer sizes for each element of X" },
            FieldInfo { name: "sizes_y", type_name: "Vec<i64>", description: "Integer sizes for each element of Y" },
            FieldInfo { name: "targets", type_name: "Vec<i64>", description: "Target sums for each pair" },
        ],
    }
}

#[derive(Debug, Clone, Serialize)]
pub struct NumericalMatchingWithTargetSums {
    sizes_x: Vec<i64>,
    sizes_y: Vec<i64>,
    targets: Vec<i64>,
}

impl NumericalMatchingWithTargetSums {
    fn validate_inputs(
        sizes_x: &[i64],
        sizes_y: &[i64],
        targets: &[i64],
    ) -> Result<(), crate::registry::ConstructionError> {
        let m = sizes_x.len();
        if m == 0 {
            return Err(
                "NumericalMatchingWithTargetSums requires at least one element per set".into(),
            );
        }
        if sizes_y.len() != m {
            return Err(
                "NumericalMatchingWithTargetSums requires sizes_x and sizes_y to have the same length"
                    .into(),
            );
        }
        if targets.len() != m {
            return Err(
                "NumericalMatchingWithTargetSums requires targets to have the same length as sizes_x"
                    .into(),
            );
        }
        Ok(())
    }

    pub fn try_new(
        sizes_x: Vec<i64>,
        sizes_y: Vec<i64>,
        targets: Vec<i64>,
    ) -> Result<Self, crate::registry::ConstructionError> {
        Self::validate_inputs(&sizes_x, &sizes_y, &targets)?;
        Ok(Self {
            sizes_x,
            sizes_y,
            targets,
        })
    }

    /// Create a new Numerical Matching with Target Sums instance.
    ///
    /// # Panics
    ///
    /// Panics if the input violates the NMTS invariants.
    pub fn new(sizes_x: Vec<i64>, sizes_y: Vec<i64>, targets: Vec<i64>) -> Self {
        Self::try_new(sizes_x, sizes_y, targets).unwrap_or_else(|message| panic!("{message}"))
    }

    /// Number of pairs (m).
    pub fn num_pairs(&self) -> usize {
        self.sizes_x.len()
    }

    /// Integer sizes for each element of X.
    pub fn sizes_x(&self) -> &[i64] {
        &self.sizes_x
    }

    /// Integer sizes for each element of Y.
    pub fn sizes_y(&self) -> &[i64] {
        &self.sizes_y
    }

    /// Target sums for each pair.
    pub fn targets(&self) -> &[i64] {
        &self.targets
    }
}

#[derive(Deserialize)]
struct NumericalMatchingWithTargetSumsData {
    sizes_x: Vec<i64>,
    sizes_y: Vec<i64>,
    targets: Vec<i64>,
}

impl<'de> Deserialize<'de> for NumericalMatchingWithTargetSums {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let data = NumericalMatchingWithTargetSumsData::deserialize(deserializer)?;
        Self::try_new(data.sizes_x, data.sizes_y, data.targets).map_err(D::Error::custom)
    }
}

impl Problem for NumericalMatchingWithTargetSums {
    const NAME: &'static str = "NumericalMatchingWithTargetSums";
    type Solution = Vec<usize>;
    type Value = Or;

    crate::problem_parameters![("num_pairs", num_pairs),];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }

    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
        Ok({
            Or({
                let m = self.num_pairs();
                if config.len() != m {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "matching permutation length does not match the instance".into(),
                    ));
                }

                if config.iter().any(|&index| index >= m) {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "matching permutation contains an out-of-range index".into(),
                    ));
                }

                // Check config is valid permutation of 0..m
                let mut used = vec![false; m];
                for &idx in config {
                    if idx >= m || used[idx] {
                        return Ok(Or(false));
                    }
                    used[idx] = true;
                }

                // Compute pair sums and compare multisets
                let mut pair_sums: Vec<i64> = (0..m)
                    .map(|i| self.sizes_x[i] + self.sizes_y[config[i]])
                    .collect();
                let mut sorted_targets = self.targets.clone();
                pair_sums.sort();
                sorted_targets.sort();
                pair_sums == sorted_targets
            })
        })
    }
}

impl crate::solvers::BruteForceProblem for NumericalMatchingWithTargetSums {
    fn dimensions(&self) -> Vec<usize> {
        let m = self.num_pairs();
        vec![m; m]
    }
}

crate::declare_variants! {
    default NumericalMatchingWithTargetSums => "2^num_pairs",
}

crate::register_brute_force! {
    NumericalMatchingWithTargetSums,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "numerical_matching_with_target_sums",
        instance: Box::new(NumericalMatchingWithTargetSums::new(
            vec![1, 4, 7],
            vec![2, 5, 3],
            vec![3, 7, 12],
        )),
        optimal_config: serde_json::json!(vec![0, 2, 1]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/misc/numerical_matching_with_target_sums.rs"]
mod tests;