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)]
58#[serde(try_from = "CosineProductIntegrationData")]
59pub struct CosineProductIntegration {
60    coefficients: Vec<i64>,
61}
62
63#[derive(Deserialize)]
64struct CosineProductIntegrationData {
65    coefficients: Vec<i64>,
66}
67
68impl TryFrom<CosineProductIntegrationData> for CosineProductIntegration {
69    type Error = crate::registry::ConstructionError;
70
71    fn try_from(data: CosineProductIntegrationData) -> Result<Self, Self::Error> {
72        Self::try_new(data.coefficients)
73    }
74}
75
76impl CosineProductIntegration {
77    /// Create a new CosineProductIntegration instance.
78    ///
79    /// # Panics
80    ///
81    /// Panics if `coefficients` is empty.
82    pub fn new(coefficients: Vec<i64>) -> Self {
83        Self::try_new(coefficients).unwrap_or_else(|error| panic!("{error}"))
84    }
85
86    fn try_new(coefficients: Vec<i64>) -> Result<Self, crate::registry::ConstructionError> {
87        if coefficients.is_empty() {
88            return Err("CosineProductIntegration requires at least one coefficient".into());
89        }
90        Ok(Self { coefficients })
91    }
92
93    /// Returns the cosine coefficients.
94    pub fn coefficients(&self) -> &[i64] {
95        &self.coefficients
96    }
97
98    /// Returns the number of coefficients.
99    pub fn num_coefficients(&self) -> usize {
100        self.coefficients.len()
101    }
102}
103
104impl Problem for CosineProductIntegration {
105    const NAME: &'static str = "CosineProductIntegration";
106    type Solution = Vec<bool>;
107    type Value = crate::types::Or;
108
109    crate::problem_parameters![("num_coefficients", num_coefficients),];
110
111    fn variant() -> Vec<(&'static str, &'static str)> {
112        crate::variant_params![]
113    }
114
115    fn evaluate(
116        &self,
117        config: &Self::Solution,
118    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
119        Ok({
120            crate::types::Or({
121                if config.len() != self.num_coefficients() {
122                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
123                        "sign-selection length does not match the coefficients".into(),
124                    ));
125                }
126                let signed_sum = self.coefficients.iter().zip(config.iter()).try_fold(
127                    0_i64,
128                    |total, (&coefficient, &bit)| {
129                        let term = if !bit {
130                            coefficient
131                        } else {
132                            coefficient.checked_neg().ok_or_else(|| {
133                                crate::traits::EvaluationError::IntegerOverflow(
134                                    "negating cosine-product coefficient".into(),
135                                )
136                            })?
137                        };
138                        total.checked_add(term).ok_or_else(|| {
139                            crate::traits::EvaluationError::IntegerOverflow(
140                                "summing signed cosine-product coefficients".into(),
141                            )
142                        })
143                    },
144                )?;
145                signed_sum == 0
146            })
147        })
148    }
149}
150
151impl crate::solvers::BruteForceProblem for CosineProductIntegration {
152    fn dimensions(&self) -> Vec<usize> {
153        vec![2; self.num_coefficients()]
154    }
155}
156
157crate::declare_variants! {
158    default CosineProductIntegration => "2^(num_coefficients / 2)",
159}
160
161crate::register_brute_force! {
162    CosineProductIntegration decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
163}
164
165#[cfg(feature = "example-db")]
166pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
167    vec![crate::example_db::specs::ModelExampleSpec {
168        id: "cosine_product_integration",
169        instance: Box::new(CosineProductIntegration::new(vec![2, 3, 5])),
170        optimal_config: serde_json::json!(vec![false, false, true]),
171        optimal_value: serde_json::json!(true),
172    }]
173}
174
175#[cfg(test)]
176#[path = "../../unit_tests/models/misc/cosine_product_integration.rs"]
177mod tests;
problemreductions/models/misc/cosine_product_integration.rs

problemreductions/models/misc/
cosine_product_integration.rs
