problemreductions/models/
decision.rs

1//! Generic decision wrapper for optimization problems.
2
3use crate::rules::{AggregateReductionResult, ReduceTo, ReduceToAggregate, ReductionResult};
4use crate::traits::Problem;
5use crate::types::{OptimizationValue, Or};
6use serde::de::DeserializeOwned;
7use serde::{Deserialize, Deserializer, Serialize};
8
9/// Metadata for concrete optimization problems that expose a decision wrapper.
10pub trait DecisionProblemMeta: Problem
11where
12    Self::Value: OptimizationValue,
13{
14    /// Problem name used by the corresponding `Decision<Self>` variant.
15    const DECISION_NAME: &'static str;
16}
17
18/// Register the decision problem name for a concrete optimization problem.
19#[macro_export]
20macro_rules! decision_problem_meta {
21    ($inner:ty, $name:literal) => {
22        impl $crate::models::decision::DecisionProblemMeta for $inner {
23            const DECISION_NAME: &'static str = $name;
24        }
25    };
26}
27
28/// Register the boilerplate inventory entries for a concrete `Decision<P>` variant.
29///
30/// Optional `additional: [Inner => "complexity", ...]` entries share the primary
31/// variant's construction fields and decoder without adding another schema or default.
32/// Both decision/optimization edges derive their identity parameter transforms directly
33/// from the inner problem's canonical parameter schema.
34#[macro_export]
35macro_rules! register_decision_variant {
36    (
37        $inner:ty,
38        $name:literal,
39        $complexity:literal,
40        $aliases:expr,
41        $description:literal,
42        category: $category:expr,
43        dims: [$($dim:expr),* $(,)?],
44        fields: [$($field:expr),* $(,)?],
45        $(additional: [$($additional:ty => $additional_complexity:literal),* $(,)?],)?
46        decode: $decoder:expr
47        $(, $random:ident)?
48    ) => {
49        $crate::register_decision_variant!(@declare $inner, $complexity, $decoder, [$($($additional => $additional_complexity),*)?] $(, $random)?);
50
51        $crate::inventory::submit! {
52            $crate::registry::ProblemSchemaEntry {
53                name: $name,
54                display_name: $crate::register_decision_variant!(@display_name $name),
55                aliases: $aliases,
56                dimensions: &[$($dim),*],
57                category: $category,
58                module_path: module_path!(),
59                description: $description,
60                fields: &[$($field),*],
61            }
62        }
63
64        $crate::register_decision_variant!(@edges $inner, $name);
65        $($(
66            $crate::register_brute_force! {
67                $crate::models::decision::Decision<$additional> decode $decoder,
68            }
69            $crate::register_decision_variant!(@edges $additional, $name);
70        )*)?
71    };
72
73    (@edges $inner:ty, $name:literal) => {
74        // Decision<P> → P: both witness (identity config) and aggregate (solve + compare)
75        $crate::inventory::submit! {
76            $crate::rules::ReductionEntry {
77                source_name: $name,
78                target_name: <$inner as $crate::traits::Problem>::NAME,
79                source_variant_fn: <$crate::models::decision::Decision<$inner> as $crate::traits::Problem>::variant,
80                target_variant_fn: <$inner as $crate::traits::Problem>::variant,
81                parameter_declarations_fn: || $crate::rules::registry::ReductionParameterDeclarations {
82                    fields: <$inner as $crate::traits::Problem>::parameter_names()
83                        .iter()
84                        .map(|&name| (name, $crate::parameters::ParameterRelation::Exact, $crate::expr::Expr::variable(name)))
85                        .collect(),
86                    unavailable: vec![],
87                },
88                module_path: module_path!(),
89                reduce_fn: Some(|any| {
90                    let source = any
91                        .downcast_ref::<$crate::models::decision::Decision<$inner>>()
92                        .ok_or_else($crate::rules::ReductionError::source_type_mismatch::<
93                            $crate::models::decision::Decision<$inner>,
94                            $inner,
95                        >)?;
96                    let result =
97                        <$crate::models::decision::Decision<$inner> as $crate::rules::ReduceTo<$inner>>::reduce_to(source)?;
98                    Ok(Box::new(result))
99                }),
100                reduce_aggregate_fn: Some(|any| {
101                    let source = any
102                        .downcast_ref::<$crate::models::decision::Decision<$inner>>()
103                        .ok_or_else($crate::rules::ReductionError::source_type_mismatch::<
104                            $crate::models::decision::Decision<$inner>,
105                            $inner,
106                        >)?;
107                    let result =
108                        <$crate::models::decision::Decision<$inner> as $crate::rules::ReduceToAggregate<$inner>>::reduce_to_aggregate(source)?;
109                    Ok(Box::new(result))
110                }),
111                aggregate_view_fn: Some($crate::rules::aggregate_view::<
112                    $crate::models::decision::DecisionToOptimizationResult<$inner>
113                >),
114                turing: false,
115            }
116        }
117
118        // Reverse edge: P → Decision<P> (Turing/multi-query reduction via binary search)
119        $crate::inventory::submit! {
120            $crate::rules::ReductionEntry {
121                source_name: <$inner as $crate::traits::Problem>::NAME,
122                target_name: $name,
123                source_variant_fn: <$inner as $crate::traits::Problem>::variant,
124                target_variant_fn: <$crate::models::decision::Decision<$inner> as $crate::traits::Problem>::variant,
125                parameter_declarations_fn: || $crate::rules::registry::ReductionParameterDeclarations {
126                    fields: <$inner as $crate::traits::Problem>::parameter_names()
127                        .iter()
128                        .map(|&name| (name, $crate::parameters::ParameterRelation::Exact, $crate::expr::Expr::variable(name)))
129                        .collect(),
130                    unavailable: vec![],
131                },
132                module_path: module_path!(),
133                reduce_fn: None,
134                reduce_aggregate_fn: None,
135                aggregate_view_fn: None,
136                turing: true,
137            }
138        }
139    };
140
141    (@declare $inner:ty, $complexity:literal, $decoder:expr, [$($additional:ty => $additional_complexity:literal),*], random) => {
142        $crate::declare_variants! {
143            default $crate::models::decision::Decision<$inner> => $complexity create $crate::models::decision::DecisionCreateSpec<$inner> random,
144            $($crate::models::decision::Decision<$additional> => $additional_complexity create $crate::models::decision::DecisionCreateSpec<$additional>,)*
145        }
146        $crate::register_brute_force! {
147            $crate::models::decision::Decision<$inner> decode $decoder,
148        }
149    };
150    (@declare $inner:ty, $complexity:literal, $decoder:expr, [$($additional:ty => $additional_complexity:literal),*]) => {
151        $crate::declare_variants! {
152            default $crate::models::decision::Decision<$inner> => $complexity create $crate::models::decision::DecisionCreateSpec<$inner>,
153            $($crate::models::decision::Decision<$additional> => $additional_complexity create $crate::models::decision::DecisionCreateSpec<$additional>,)*
154        }
155        $crate::register_brute_force! {
156            $crate::models::decision::Decision<$inner> decode $decoder,
157        }
158    };
159    (@display_name "DecisionMinimumVertexCover") => {
160        "Decision Minimum Vertex Cover"
161    };
162    (@display_name "DecisionMinimumDominatingSet") => {
163        "Decision Minimum Dominating Set"
164    };
165    (@display_name "DecisionMaximumIndependentSet") => {
166        "Decision Maximum Independent Set"
167    };
168    (@display_name $name:literal) => {
169        $name
170    };
171}
172
173/// Flat construction DTO used by [`register_decision_variant!`].
174///
175/// Persisted decision problems remain `{ "inner": ..., "bound": ... }`, while
176/// construction inputs expose the inner problem's fields beside `bound`.
177#[doc(hidden)]
178pub struct DecisionCreateSpec<P>
179where
180    P: Problem,
181    P::Value: OptimizationValue,
182{
183    inner: P,
184    bound: <P::Value as OptimizationValue>::Inner,
185}
186
187impl<P> crate::registry::CreateSpec for DecisionCreateSpec<P>
188where
189    P: Problem,
190    P::Value: OptimizationValue,
191{
192    const FIELDS: &'static [crate::registry::FieldInfo] = &[];
193
194    fn inputs() -> Vec<crate::registry::CreateInputInfo> {
195        let variant = P::variant()
196            .into_iter()
197            .map(|(k, v)| (k.to_string(), v.to_string()))
198            .collect();
199        let entry = crate::registry::find_variant_entry(P::NAME, &variant)
200            .expect("decision inner variant must be registered");
201        let mut inputs = entry.inputs();
202        inputs.push(crate::registry::CreateInputInfo {
203            name: "bound",
204            type_name: std::any::type_name::<<P::Value as OptimizationValue>::Inner>(),
205            description: "Decision objective bound",
206            required: true,
207            codec: crate::registry::CreateInputCodec::Scalar,
208        });
209        inputs
210    }
211}
212
213impl<'de, P> Deserialize<'de> for DecisionCreateSpec<P>
214where
215    P: Problem + 'static,
216    P::Value: OptimizationValue,
217    <P::Value as OptimizationValue>::Inner: DeserializeOwned,
218{
219    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
220    where
221        D: Deserializer<'de>,
222    {
223        let value = serde_json::Value::deserialize(deserializer)?;
224        let mut inputs = value.as_object().cloned().ok_or_else(|| {
225            serde::de::Error::custom("decision construction inputs must be an object")
226        })?;
227        let bound = inputs
228            .remove("bound")
229            .ok_or_else(|| serde::de::Error::missing_field("bound"))?;
230        let variant = P::variant()
231            .into_iter()
232            .map(|(k, v)| (k.to_string(), v.to_string()))
233            .collect();
234        let entry = crate::registry::find_variant_entry(P::NAME, &variant)
235            .expect("decision inner variant must be registered");
236        let constructed = (entry.construct_fn)(serde_json::Value::Object(inputs))
237            .map_err(serde::de::Error::custom)?;
238        let inner = *(constructed as Box<dyn std::any::Any>)
239            .downcast::<P>()
240            .expect("registered constructor must return the declared inner type");
241        let bound = serde_json::from_value(bound).map_err(serde::de::Error::custom)?;
242        Ok(Self { inner, bound })
243    }
244}
245
246impl<P> From<DecisionCreateSpec<P>> for Decision<P>
247where
248    P: Problem,
249    P::Value: OptimizationValue,
250{
251    fn from(spec: DecisionCreateSpec<P>) -> Self {
252        Self::new(spec.inner, spec.bound)
253    }
254}
255
256/// Decision version of an optimization problem with a fixed objective bound.
257#[derive(Debug, Clone, Serialize, Deserialize)]
258pub struct Decision<P: Problem>
259where
260    P::Value: OptimizationValue,
261{
262    inner: P,
263    bound: <P::Value as OptimizationValue>::Inner,
264}
265
266impl<P: Problem> Decision<P>
267where
268    P::Value: OptimizationValue,
269{
270    /// Create a decision wrapper around `inner` with the provided bound.
271    pub fn new(inner: P, bound: <P::Value as OptimizationValue>::Inner) -> Self {
272        Self { inner, bound }
273    }
274
275    /// Borrow the wrapped optimization problem.
276    pub fn inner(&self) -> &P {
277        &self.inner
278    }
279
280    /// Borrow the decision bound.
281    pub fn bound(&self) -> &<P::Value as OptimizationValue>::Inner {
282        &self.bound
283    }
284}
285
286impl<P> Problem for Decision<P>
287where
288    P: DecisionProblemMeta,
289    P::Value: OptimizationValue,
290{
291    const NAME: &'static str = P::DECISION_NAME;
292    type Solution = P::Solution;
293    type Value = Or;
294
295    fn parameter_names() -> &'static [&'static str] {
296        P::parameter_names()
297    }
298
299    fn parameters(&self) -> crate::types::ProblemParameters {
300        self.inner.parameters()
301    }
302
303    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
304        Ok({
305            Or(<P::Value as OptimizationValue>::meets_bound(
306                &self.inner.evaluate(config)?,
307                &self.bound,
308            ))
309        })
310    }
311
312    fn variant() -> Vec<(&'static str, &'static str)> {
313        P::variant()
314    }
315}
316
317impl<P> crate::solvers::BruteForceProblem for Decision<P>
318where
319    P: DecisionProblemMeta + crate::solvers::BruteForceProblem,
320    P::Value: OptimizationValue,
321{
322    fn dimensions(&self) -> Vec<usize> {
323        self.inner.dimensions()
324    }
325}
326
327/// Witness and aggregate reduction result for `Decision<P> -> P`.
328///
329/// An optimum value decides the bound; a witness is recovered only when its
330/// value meets the bound. Both mappings use the same constructed target.
331///
332/// ```
333/// use problemreductions::models::{Decision, MinimumVertexCover};
334/// use problemreductions::rules::{AggregateReductionResult, ReduceTo, ReductionResult};
335/// use problemreductions::solvers::BruteForce;
336/// use problemreductions::topology::SimpleGraph;
337/// use problemreductions::types::Or;
338///
339/// let cover = MinimumVertexCover::new(
340///     SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
341///     vec![1_i64; 3],
342/// );
343/// let source = Decision::new(cover, 1);
344/// let reduction = ReduceTo::<MinimumVertexCover<SimpleGraph, i64>>::reduce_to(&source)?;
345/// let (optimum, witnesses) = BruteForce::new()
346///     .solve_with_witnesses(ReductionResult::target_problem(&reduction))?;
347/// let answer = reduction.extract_value(optimum);
348/// assert_eq!(answer, Or(false)); // Minimum cover size is 2, above the bound.
349/// if answer.0 {
350///     let source_witness = reduction.extract_solution(&witnesses[0])?;
351/// }
352/// # Ok::<(), Box<dyn std::error::Error>>(())
353/// ```
354#[derive(Debug, Clone)]
355pub struct DecisionToOptimizationResult<P>
356where
357    P: Problem,
358    P::Value: OptimizationValue,
359{
360    target: P,
361    bound: <P::Value as OptimizationValue>::Inner,
362}
363
364impl<P> AggregateReductionResult for DecisionToOptimizationResult<P>
365where
366    P: DecisionProblemMeta + 'static,
367    P::Value: OptimizationValue + Serialize + DeserializeOwned,
368{
369    type Source = Decision<P>;
370    type Target = P;
371
372    fn target_problem(&self) -> &Self::Target {
373        &self.target
374    }
375
376    fn extract_value(&self, target_value: P::Value) -> Or {
377        Or(<P::Value as OptimizationValue>::meets_bound(
378            &target_value,
379            &self.bound,
380        ))
381    }
382}
383
384impl<P> ReduceToAggregate<P> for Decision<P>
385where
386    P: DecisionProblemMeta + Clone + 'static,
387    P::Value: OptimizationValue + Serialize + DeserializeOwned,
388{
389    type Result = DecisionToOptimizationResult<P>;
390
391    fn reduce_to_aggregate(&self) -> Result<Self::Result, crate::rules::ReductionError> {
392        Ok(DecisionToOptimizationResult {
393            target: self.inner.clone(),
394            bound: self.bound.clone(),
395        })
396    }
397}
398
399impl<P> ReductionResult for DecisionToOptimizationResult<P>
400where
401    P: DecisionProblemMeta + 'static,
402    P::Solution: Clone,
403    P::Value: OptimizationValue + Serialize + DeserializeOwned,
404{
405    type Source = Decision<P>;
406    type Target = P;
407
408    fn target_problem(&self) -> &Self::Target {
409        &self.target
410    }
411
412    fn extract_solution(
413        &self,
414        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
415    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
416        let value = crate::rules::validate_target_solution(&self.target, target_solution)?;
417        if !self.extract_value(value).0 {
418            return Err(crate::rules::ExtractionError::invalid(
419                "target witness does not meet the decision bound",
420            ));
421        }
422
423        Ok(target_solution.clone())
424    }
425}
426
427impl<P> ReduceTo<P> for Decision<P>
428where
429    P: DecisionProblemMeta + Clone + 'static,
430    P::Solution: Clone,
431    P::Value: OptimizationValue + Serialize + DeserializeOwned,
432{
433    type Result = DecisionToOptimizationResult<P>;
434
435    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
436        self.reduce_to_aggregate()
437    }
438}
439
440#[cfg(test)]
441#[path = "../unit_tests/models/decision.rs"]
442mod tests;
problemreductions/models/decision.rs

problemreductions/models/
decision.rs
