problemreductions/models/misc/

subset_product.rs

//! Subset Product problem implementation.
//!
//! Given a set of positive integers and a target value, the problem asks whether
//! any subset's product equals exactly the target. A multiplicative analogue of
//! Subset Sum; NP-complete (see e.g. Garey & Johnson, 1979).
//!
//! This implementation uses arbitrary-precision integers (`BigUint`) so
//! reductions can construct large instances without fixed-width overflow.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use num_bigint::{BigUint, ToBigUint};
use num_traits::{One, Zero};
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "SubsetProduct",
        display_name: "Subset Product",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Find a subset of positive integers whose product equals exactly a target value",
        fields: &[
            FieldInfo { name: "sizes", type_name: "Vec<BigUint>", description: "Positive integer sizes s(a) for each element" },
            FieldInfo { name: "target", type_name: "BigUint", description: "Target product B" },
        ],
    }
}

/// The Subset Product problem.
///
/// Given a set of `n` positive integers and a target `B`, determine whether
/// there exists a subset whose elements multiply to exactly `B`.
///
/// # Representation
///
/// Each element has a binary variable: `x_i = 1` if element `i` is selected,
/// `0` otherwise. The problem is satisfiable iff `∏_{i: x_i=1} sizes[i] == target`.
///
/// # Example
///
/// ```
/// use problemreductions::models::misc::SubsetProduct;
/// use problemreductions::{Problem, BruteForce};
///
/// let problem = SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32);
/// let solver = BruteForce::new();
/// let solution = solver.solve(&problem).unwrap();
/// assert!(solution.is_some());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "SubsetProductData")]
pub struct SubsetProduct {
    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
    sizes: Vec<BigUint>,
    #[serde(with = "super::biguint_serde::decimal_biguint")]
    target: BigUint,
}

#[derive(Deserialize)]
struct SubsetProductData {
    #[serde(with = "super::biguint_serde::decimal_biguint_vec")]
    sizes: Vec<BigUint>,
    #[serde(with = "super::biguint_serde::decimal_biguint")]
    target: BigUint,
}

impl TryFrom<SubsetProductData> for SubsetProduct {
    type Error = crate::registry::ConstructionError;
    fn try_from(data: SubsetProductData) -> Result<Self, Self::Error> {
        if data.sizes.iter().any(BigUint::is_zero) {
            return Err("all sizes must be positive (> 0)".into());
        }
        if data.target.is_zero() {
            return Err("SubsetProduct target must be positive".into());
        }
        Ok(Self {
            sizes: data.sizes,
            target: data.target,
        })
    }
}

impl SubsetProduct {
    /// Create a new SubsetProduct instance.
    ///
    /// # Panics
    ///
    /// Panics if any size is not positive (must be > 0) or if target is zero.
    pub fn new<S, T>(sizes: Vec<S>, target: T) -> Self
    where
        S: ToBigUint,
        T: ToBigUint,
    {
        Self::try_new(sizes, target).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new<S, T>(sizes: Vec<S>, target: T) -> Result<Self, crate::registry::ConstructionError>
    where
        S: ToBigUint,
        T: ToBigUint,
    {
        let sizes = sizes
            .into_iter()
            .map(|size| size.to_biguint().ok_or("all sizes must be positive (> 0)"))
            .collect::<Result<Vec<_>, _>>()?;
        let target = target
            .to_biguint()
            .ok_or("SubsetProduct target must be nonnegative")?;
        SubsetProductData { sizes, target }.try_into()
    }

    /// Create a SubsetProduct without validating sizes (for testing edge cases).
    #[cfg(test)]
    pub(crate) fn new_unchecked(sizes: Vec<BigUint>, target: BigUint) -> Self {
        Self { sizes, target }
    }

    /// Returns the element sizes.
    pub fn sizes(&self) -> &[BigUint] {
        &self.sizes
    }

    /// Returns the target product.
    pub fn target(&self) -> &BigUint {
        &self.target
    }

    /// Returns the number of elements.
    pub fn num_elements(&self) -> usize {
        self.sizes.len()
    }
}

impl Problem for SubsetProduct {
    const NAME: &'static str = "SubsetProduct";
    type Solution = Vec<bool>;
    type Value = crate::types::Or;

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

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

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        Ok({
            crate::types::Or({
                if config.len() != self.num_elements() {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "subset-selection length does not match the elements".into(),
                    ));
                }
                let mut product = BigUint::one();
                for (i, &x) in config.iter().enumerate() {
                    if x {
                        product *= &self.sizes[i];
                        if product > self.target {
                            return Ok(crate::types::Or(false));
                        }
                    }
                }
                product == self.target
            })
        })
    }
}

impl crate::solvers::BruteForceProblem for SubsetProduct {
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.num_elements()]
    }
}

crate::declare_variants! {
    default SubsetProduct => "2^num_elements",
}

crate::register_brute_force! {
    SubsetProduct decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    // 6 elements [2,3,5,7,6,10], target 210 → select {2,3,5,7}
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "subset_product",
        instance: Box::new(SubsetProduct::new(vec![2u32, 3, 5, 7, 6, 10], 210u32)),
        optimal_config: serde_json::json!(vec![true, true, true, true, false, false]),
        optimal_value: serde_json::json!(true),
    }]
}

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