problemreductions/models/misc/
cosine_product_integration.rs

1//! Cosine Product Integration problem implementation.
2//!
3//! Given integer frequencies `a_1, ..., a_n`, determine whether a sign
4//! assignment `ε ∈ {-1, +1}^n` exists with `∑ εᵢ aᵢ = 0`.
5//!
6//! This is equivalent to asking whether
7//! `∫₀²π ∏ᵢ cos(aᵢ θ) dθ ≠ 0` (Garey & Johnson A7 AN14).
8//! The integral is nonzero exactly when such a balanced sign assignment
9//! exists, so the G&J question "does the integral equal zero?" is the
10//! complement of this satisfaction problem.
11
12use crate::registry::{FieldInfo, ProblemSchemaEntry};
13use crate::traits::Problem;
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "CosineProductIntegration",
19        display_name: "Cosine Product Integration",
20        aliases: &[],
21        dimensions: &[],
22        category: crate::registry::ProblemCategory::Misc,
23        module_path: module_path!(),
24        description: "Decide whether a balanced sign assignment exists for a sequence of integer frequencies",
25        fields: &[
26            FieldInfo {
27                name: "coefficients",
28                type_name: "Vec<i64>",
29                description: "Integer cosine frequencies",
30            },
31        ],
32    }
33}
34
35/// The Cosine Product Integration problem.
36///
37/// Given integer coefficients `a_1, ..., a_n`, determine whether there
38/// exists a sign assignment `ε ∈ {-1, +1}^n` with `∑ εᵢ aᵢ = 0`.
39///
40/// # Representation
41///
42/// Each variable chooses a sign: `0` means `+aᵢ`, `1` means `−aᵢ`.
43/// A configuration is satisfying when the resulting signed sum is zero.
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::misc::CosineProductIntegration;
49/// use problemreductions::{Problem, BruteForce};
50///
51/// // coefficients [2, 3, 5]: sign assignment (+2, +3, -5) = 0
52/// let problem = CosineProductIntegration::new(vec![2, 3, 5]);
53/// let solver = BruteForce::new();
54/// let solution = solver.solve(&problem).unwrap();
55/// assert!(solution.is_some());
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct CosineProductIntegration {
59    coefficients: Vec<i64>,
60}
61
62impl CosineProductIntegration {
63    /// Create a new CosineProductIntegration instance.
64    ///
65    /// # Panics
66    ///
67    /// Panics if `coefficients` is empty.
68    pub fn new(coefficients: Vec<i64>) -> Self {
69        assert!(
70            !coefficients.is_empty(),
71            "CosineProductIntegration requires at least one coefficient"
72        );
73        Self { coefficients }
74    }
75
76    /// Returns the cosine coefficients.
77    pub fn coefficients(&self) -> &[i64] {
78        &self.coefficients
79    }
80
81    /// Returns the number of coefficients.
82    pub fn num_coefficients(&self) -> usize {
83        self.coefficients.len()
84    }
85}
86
87impl Problem for CosineProductIntegration {
88    const NAME: &'static str = "CosineProductIntegration";
89    type Solution = Vec<bool>;
90    type Value = crate::types::Or;
91
92    crate::problem_parameters![("num_coefficients", num_coefficients),];
93
94    fn variant() -> Vec<(&'static str, &'static str)> {
95        crate::variant_params![]
96    }
97
98    fn evaluate(
99        &self,
100        config: &Self::Solution,
101    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
102        Ok({
103            crate::types::Or({
104                if config.len() != self.num_coefficients() {
105                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
106                        "sign-selection length does not match the coefficients".into(),
107                    ));
108                }
109                let signed_sum = self.coefficients.iter().zip(config.iter()).try_fold(
110                    0_i64,
111                    |total, (&coefficient, &bit)| {
112                        let term = if !bit {
113                            coefficient
114                        } else {
115                            coefficient.checked_neg().ok_or_else(|| {
116                                crate::traits::EvaluationError::IntegerOverflow(
117                                    "negating cosine-product coefficient".into(),
118                                )
119                            })?
120                        };
121                        total.checked_add(term).ok_or_else(|| {
122                            crate::traits::EvaluationError::IntegerOverflow(
123                                "summing signed cosine-product coefficients".into(),
124                            )
125                        })
126                    },
127                )?;
128                signed_sum == 0
129            })
130        })
131    }
132}
133
134impl crate::solvers::BruteForceProblem for CosineProductIntegration {
135    fn dimensions(&self) -> Vec<usize> {
136        vec![2; self.num_coefficients()]
137    }
138}
139
140crate::declare_variants! {
141    default CosineProductIntegration => "2^(num_coefficients / 2)",
142}
143
144crate::register_brute_force! {
145    CosineProductIntegration decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
146}
147
148#[cfg(feature = "example-db")]
149pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
150    vec![crate::example_db::specs::ModelExampleSpec {
151        id: "cosine_product_integration",
152        instance: Box::new(CosineProductIntegration::new(vec![2, 3, 5])),
153        optimal_config: serde_json::json!(vec![false, false, true]),
154        optimal_value: serde_json::json!(true),
155    }]
156}
157
158#[cfg(test)]
159#[path = "../../unit_tests/models/misc/cosine_product_integration.rs"]
160mod tests;
problemreductions/models/misc/cosine_product_integration.rs

problemreductions/models/misc/
cosine_product_integration.rs
