problemreductions/models/misc/
integer_expression_membership.rs

1//! Integer Expression Membership problem implementation.
2//!
3//! Given a recursive integer expression tree built from singleton positive integers
4//! combined with union (∪) and Minkowski sum (+) operations, and a target integer K,
5//! decide whether K belongs to the set represented by the expression.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Or;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "IntegerExpressionMembership",
15        display_name: "Integer Expression Membership",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Decide whether a target integer belongs to the set represented by an expression tree over union and Minkowski sum",
21        fields: &[
22            FieldInfo { name: "expression", type_name: "IntExpr", description: "Recursive expression tree" },
23            FieldInfo { name: "target", type_name: "i64", description: "Target integer K" },
24        ],
25    }
26}
27
28/// A recursive integer expression tree.
29///
30/// Represents a set of positive integers built from:
31/// - `Atom(n)`: the singleton set {n}
32/// - `Union(f, g)`: set union F ∪ G
33/// - `Sum(f, g)`: Minkowski sum {m + n : m ∈ F, n ∈ G}
34#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
35pub enum IntExpr {
36    /// Singleton set {n} for a positive integer n.
37    Atom(i64),
38    /// Set union: F ∪ G.
39    Union(Box<IntExpr>, Box<IntExpr>),
40    /// Minkowski sum: {m + n : m ∈ F, n ∈ G}.
41    Sum(Box<IntExpr>, Box<IntExpr>),
42}
43
44impl IntExpr {
45    /// Returns true if all atoms in the expression are positive (> 0).
46    pub fn all_atoms_positive(&self) -> bool {
47        match self {
48            IntExpr::Atom(n) => *n > 0,
49            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => {
50                l.all_atoms_positive() && r.all_atoms_positive()
51            }
52        }
53    }
54
55    /// Count the total number of nodes in the expression tree.
56    pub fn size(&self) -> usize {
57        match self {
58            IntExpr::Atom(_) => 1,
59            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => 1 + l.size() + r.size(),
60        }
61    }
62
63    /// Count the number of Union nodes in the expression tree.
64    pub fn count_union_nodes(&self) -> usize {
65        match self {
66            IntExpr::Atom(_) => 0,
67            IntExpr::Union(l, r) => 1 + l.count_union_nodes() + r.count_union_nodes(),
68            IntExpr::Sum(l, r) => l.count_union_nodes() + r.count_union_nodes(),
69        }
70    }
71
72    /// Count the number of Atom nodes in the expression tree.
73    pub fn count_atoms(&self) -> usize {
74        match self {
75            IntExpr::Atom(_) => 1,
76            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => l.count_atoms() + r.count_atoms(),
77        }
78    }
79
80    /// Compute the depth of the expression tree (0 for a single Atom).
81    pub fn depth(&self) -> usize {
82        match self {
83            IntExpr::Atom(_) => 0,
84            IntExpr::Union(l, r) | IntExpr::Sum(l, r) => 1 + l.depth().max(r.depth()),
85        }
86    }
87
88    /// Evaluate the expression given union choices from config.
89    ///
90    /// `counter` tracks which union node we are at (DFS order).
91    /// Returns `Some(value)` if the config is valid, `None` otherwise.
92    fn evaluate_with_config(&self, config: &[bool], counter: &mut usize) -> Option<i64> {
93        match self {
94            IntExpr::Atom(n) => Some(*n),
95            IntExpr::Union(left, right) => {
96                let idx = *counter;
97                *counter += 1;
98                if idx >= config.len() {
99                    return None;
100                }
101                if config[idx] {
102                    right.evaluate_with_config(config, counter)
103                } else {
104                    left.evaluate_with_config(config, counter)
105                }
106            }
107            IntExpr::Sum(left, right) => {
108                let l = left.evaluate_with_config(config, counter)?;
109                let r = right.evaluate_with_config(config, counter)?;
110                l.checked_add(r)
111            }
112        }
113    }
114}
115
116/// The Integer Expression Membership problem.
117///
118/// Given an integer expression `e` over union (∪) and Minkowski sum (+)
119/// operations on singleton positive integers, and a target integer `K`,
120/// decide whether `K ∈ eval(e)`.
121///
122/// # Configuration
123///
124/// Each Union node has a binary variable (0 = left, 1 = right).
125/// A configuration assigns a branch choice to every Union node in DFS order.
126/// The expression then collapses to a chain of Sum and Atom nodes,
127/// evaluating to a single integer.
128///
129/// # Example
130///
131/// ```
132/// use problemreductions::models::misc::{IntegerExpressionMembership, IntExpr};
133/// use problemreductions::{Problem, BruteForce};
134///
135/// // e = (1 ∪ 4) + (3 ∪ 6) + (2 ∪ 5), target K = 12
136/// let expr = IntExpr::Sum(
137///     Box::new(IntExpr::Sum(
138///         Box::new(IntExpr::Union(
139///             Box::new(IntExpr::Atom(1)),
140///             Box::new(IntExpr::Atom(4)),
141///         )),
142///         Box::new(IntExpr::Union(
143///             Box::new(IntExpr::Atom(3)),
144///             Box::new(IntExpr::Atom(6)),
145///         )),
146///     )),
147///     Box::new(IntExpr::Union(
148///         Box::new(IntExpr::Atom(2)),
149///         Box::new(IntExpr::Atom(5)),
150///     )),
151/// );
152/// let problem = IntegerExpressionMembership::new(expr, 12);
153/// let solver = BruteForce::new();
154/// let solution = solver.solve(&problem).unwrap();
155/// assert!(solution.is_some());
156/// ```
157#[derive(Debug, Clone, Serialize, Deserialize)]
158#[serde(try_from = "IntegerExpressionMembershipData")]
159pub struct IntegerExpressionMembership {
160    /// The recursive expression tree.
161    expression: IntExpr,
162    /// The target integer K.
163    target: i64,
164}
165
166#[derive(Deserialize)]
167struct IntegerExpressionMembershipData {
168    expression: IntExpr,
169    target: i64,
170}
171
172impl TryFrom<IntegerExpressionMembershipData> for IntegerExpressionMembership {
173    type Error = crate::registry::ConstructionError;
174
175    fn try_from(data: IntegerExpressionMembershipData) -> Result<Self, Self::Error> {
176        Self::try_new(data.expression, data.target)
177    }
178}
179
180impl IntegerExpressionMembership {
181    /// Create a new IntegerExpressionMembership instance.
182    ///
183    /// # Arguments
184    /// * `expression` - The integer expression tree
185    /// * `target` - The target integer K
186    pub fn new(expression: IntExpr, target: i64) -> Self {
187        Self::try_new(expression, target).unwrap_or_else(|error| panic!("{error}"))
188    }
189
190    fn try_new(
191        expression: IntExpr,
192        target: i64,
193    ) -> Result<Self, crate::registry::ConstructionError> {
194        if target <= 0 {
195            return Err("target must be a positive integer (got 0)".into());
196        }
197        if !expression.all_atoms_positive() {
198            return Err("all Atom values must be positive (> 0)".into());
199        }
200        Ok(Self { expression, target })
201    }
202
203    /// Returns a reference to the expression tree.
204    pub fn expression(&self) -> &IntExpr {
205        &self.expression
206    }
207
208    /// Returns the target integer K.
209    pub fn target(&self) -> i64 {
210        self.target
211    }
212
213    /// Returns the total number of nodes in the expression tree.
214    pub fn expression_size(&self) -> usize {
215        self.expression.size()
216    }
217
218    /// Returns the number of Union nodes in the expression tree.
219    pub fn num_union_nodes(&self) -> usize {
220        self.expression.count_union_nodes()
221    }
222
223    /// Returns the number of Atom nodes in the expression tree.
224    pub fn num_atoms(&self) -> usize {
225        self.expression.count_atoms()
226    }
227
228    /// Returns the depth of the expression tree.
229    pub fn expression_depth(&self) -> usize {
230        self.expression.depth()
231    }
232
233    /// Evaluate the expression for a given config and return the resulting integer.
234    ///
235    /// Returns `Some(value)` if the config is valid, `None` otherwise.
236    pub fn evaluate_config(&self, config: &[bool]) -> Option<i64> {
237        let mut counter = 0;
238        self.expression.evaluate_with_config(config, &mut counter)
239    }
240}
241
242impl Problem for IntegerExpressionMembership {
243    const NAME: &'static str = "IntegerExpressionMembership";
244    type Solution = Vec<bool>;
245    type Value = Or;
246
247    crate::problem_parameters![("num_union_nodes", num_union_nodes),];
248
249    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
250        Ok({
251            Or({
252                if config.len() != self.num_union_nodes() {
253                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
254                        "union-choice length does not match the expression".into(),
255                    ));
256                }
257                match self.evaluate_config(config) {
258                    Some(value) => value == self.target,
259                    None => false,
260                }
261            })
262        })
263    }
264
265    fn variant() -> Vec<(&'static str, &'static str)> {
266        crate::variant_params![]
267    }
268}
269
270impl crate::solvers::BruteForceProblem for IntegerExpressionMembership {
271    fn dimensions(&self) -> Vec<usize> {
272        vec![2; self.num_union_nodes()]
273    }
274}
275
276crate::declare_variants! {
277    default IntegerExpressionMembership => "2^num_union_nodes",
278}
279
280crate::register_brute_force! {
281    IntegerExpressionMembership decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
282}
283
284#[cfg(feature = "example-db")]
285pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
286    // e = (1 ∪ 4) + (3 ∪ 6) + (2 ∪ 5), K = 12
287    // 3 union nodes → 8 configs. Set = {6, 9, 12, 15}.
288    // Witness: choose right(4), right(6), left(2) → 4+6+2=12, config=[1,1,0]
289    let expr = IntExpr::Sum(
290        Box::new(IntExpr::Sum(
291            Box::new(IntExpr::Union(
292                Box::new(IntExpr::Atom(1)),
293                Box::new(IntExpr::Atom(4)),
294            )),
295            Box::new(IntExpr::Union(
296                Box::new(IntExpr::Atom(3)),
297                Box::new(IntExpr::Atom(6)),
298            )),
299        )),
300        Box::new(IntExpr::Union(
301            Box::new(IntExpr::Atom(2)),
302            Box::new(IntExpr::Atom(5)),
303        )),
304    );
305    vec![crate::example_db::specs::ModelExampleSpec {
306        id: "integer_expression_membership",
307        instance: Box::new(IntegerExpressionMembership::new(expr, 12)),
308        optimal_config: serde_json::json!(vec![true, true, false]),
309        optimal_value: serde_json::json!(true),
310    }]
311}
312
313#[cfg(test)]
314#[path = "../../unit_tests/models/misc/integer_expression_membership.rs"]
315mod tests;
problemreductions/models/misc/integer_expression_membership.rs

problemreductions/models/misc/
integer_expression_membership.rs
