problemreductions/solvers/
decision_search.rs

1//! Decision-guided binary search for optimization via decision queries.
2
3use crate::models::decision::{Decision, DecisionProblemMeta};
4use crate::solvers::{BruteForce, Solver};
5use crate::traits::Problem;
6use crate::types::{Max, Min, OptimizationValue, Or};
7use serde::de::DeserializeOwned;
8use serde::Serialize;
9use std::fmt;
10
11/// Whether a decision problem has at least one satisfying configuration.
12fn is_satisfiable<P>(problem: &P) -> bool
13where
14    P: Problem<Value = Or>,
15{
16    BruteForce::new().solve(problem).0
17}
18
19fn solve_via_decision_min<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
20where
21    P: DecisionProblemMeta + Problem<Value = Min<i32>> + Clone,
22{
23    if lower > upper {
24        return None;
25    }
26
27    if !is_satisfiable(&Decision::new(problem.clone(), upper)) {
28        return None;
29    }
30
31    let mut lo = lower;
32    let mut hi = upper;
33    while lo < hi {
34        let mid = lo + (hi - lo) / 2;
35        if is_satisfiable(&Decision::new(problem.clone(), mid)) {
36            hi = mid;
37        } else {
38            lo = mid + 1;
39        }
40    }
41
42    Some(lo)
43}
44
45fn solve_via_decision_max<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
46where
47    P: DecisionProblemMeta + Problem<Value = Max<i32>> + Clone,
48{
49    if lower > upper {
50        return None;
51    }
52
53    if !is_satisfiable(&Decision::new(problem.clone(), lower)) {
54        return None;
55    }
56
57    let mut lo = lower;
58    let mut hi = upper;
59    while lo < hi {
60        let mid = lo + (hi - lo + 1) / 2;
61        if is_satisfiable(&Decision::new(problem.clone(), mid)) {
62            lo = mid;
63        } else {
64            hi = mid - 1;
65        }
66    }
67
68    Some(lo)
69}
70
71#[doc(hidden)]
72pub trait DecisionSearchValue:
73    OptimizationValue<Inner = i32> + Clone + fmt::Debug + Serialize + DeserializeOwned
74{
75    fn solve_problem<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
76    where
77        P: DecisionProblemMeta + Problem<Value = Self> + Clone;
78}
79
80impl DecisionSearchValue for Min<i32> {
81    fn solve_problem<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
82    where
83        P: DecisionProblemMeta + Problem<Value = Self> + Clone,
84    {
85        solve_via_decision_min(problem, lower, upper)
86    }
87}
88
89impl DecisionSearchValue for Max<i32> {
90    fn solve_problem<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
91    where
92        P: DecisionProblemMeta + Problem<Value = Self> + Clone,
93    {
94        solve_via_decision_max(problem, lower, upper)
95    }
96}
97
98/// Recover an optimization value by querying the problem's decision wrapper.
99pub fn solve_via_decision<P>(problem: &P, lower: i32, upper: i32) -> Option<i32>
100where
101    P: DecisionProblemMeta + Clone,
102    P::Value: DecisionSearchValue,
103{
104    <P::Value as DecisionSearchValue>::solve_problem(problem, lower, upper)
105}
106
107#[cfg(test)]
108#[path = "../unit_tests/solvers/decision_search.rs"]
109mod tests;
problemreductions/solvers/decision_search.rs

problemreductions/solvers/
decision_search.rs
