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;
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) -> Result<bool, crate::solvers::SolveError>
13where
14    P: Problem<Value = Or> + 'static,
15    P::Solution: 'static,
16{
17    Ok(BruteForce::new().solve(problem)?.is_some())
18}
19
20fn solve_via_decision_min<P>(
21    problem: &P,
22    lower: i64,
23    upper: i64,
24) -> Result<Option<i64>, crate::solvers::SolveError>
25where
26    P: DecisionProblemMeta + Problem<Value = Min<i64>> + Clone + 'static,
27    P::Solution: 'static,
28{
29    if lower > upper {
30        return Err(crate::solvers::SolveError::InvalidSearchInterval { lower, upper });
31    }
32
33    if !is_satisfiable(&Decision::new(problem.clone(), upper))? {
34        if upper != i64::MAX && is_satisfiable(&Decision::new(problem.clone(), i64::MAX))? {
35            return Err(crate::solvers::SolveError::OptimumOutsideSearchInterval { lower, upper });
36        }
37        return Ok(None);
38    }
39    if let Some(bound) = lower.checked_sub(1) {
40        if is_satisfiable(&Decision::new(problem.clone(), bound))? {
41            return Err(crate::solvers::SolveError::OptimumOutsideSearchInterval { lower, upper });
42        }
43    }
44
45    let mut lo = lower;
46    let mut hi = upper;
47    while lo < hi {
48        let mid = i64::try_from((i128::from(lo) + i128::from(hi)).div_euclid(2))
49            .expect("midpoint lies within the i64 interval");
50        if is_satisfiable(&Decision::new(problem.clone(), mid))? {
51            hi = mid;
52        } else {
53            lo = mid + 1;
54        }
55    }
56
57    Ok(Some(lo))
58}
59
60fn solve_via_decision_max<P>(
61    problem: &P,
62    lower: i64,
63    upper: i64,
64) -> Result<Option<i64>, crate::solvers::SolveError>
65where
66    P: DecisionProblemMeta + Problem<Value = Max<i64>> + Clone + 'static,
67    P::Solution: 'static,
68{
69    if lower > upper {
70        return Err(crate::solvers::SolveError::InvalidSearchInterval { lower, upper });
71    }
72
73    if !is_satisfiable(&Decision::new(problem.clone(), lower))? {
74        if lower != i64::MIN && is_satisfiable(&Decision::new(problem.clone(), i64::MIN))? {
75            return Err(crate::solvers::SolveError::OptimumOutsideSearchInterval { lower, upper });
76        }
77        return Ok(None);
78    }
79    if let Some(bound) = upper.checked_add(1) {
80        if is_satisfiable(&Decision::new(problem.clone(), bound))? {
81            return Err(crate::solvers::SolveError::OptimumOutsideSearchInterval { lower, upper });
82        }
83    }
84
85    let mut lo = lower;
86    let mut hi = upper;
87    while lo < hi {
88        let mid = i64::try_from((i128::from(lo) + i128::from(hi)).div_euclid(2) + 1)
89            .expect("midpoint lies within the i64 interval");
90        if is_satisfiable(&Decision::new(problem.clone(), mid))? {
91            lo = mid;
92        } else {
93            hi = mid - 1;
94        }
95    }
96
97    Ok(Some(lo))
98}
99
100#[doc(hidden)]
101pub trait DecisionSearchValue:
102    OptimizationValue<Inner = i64> + Clone + fmt::Debug + Serialize + DeserializeOwned
103{
104    fn solve_problem<P>(
105        problem: &P,
106        lower: i64,
107        upper: i64,
108    ) -> Result<Option<i64>, crate::solvers::SolveError>
109    where
110        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
111        P::Solution: 'static;
112}
113
114impl DecisionSearchValue for Min<i64> {
115    fn solve_problem<P>(
116        problem: &P,
117        lower: i64,
118        upper: i64,
119    ) -> Result<Option<i64>, crate::solvers::SolveError>
120    where
121        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
122        P::Solution: 'static,
123    {
124        solve_via_decision_min(problem, lower, upper)
125    }
126}
127
128impl DecisionSearchValue for Max<i64> {
129    fn solve_problem<P>(
130        problem: &P,
131        lower: i64,
132        upper: i64,
133    ) -> Result<Option<i64>, crate::solvers::SolveError>
134    where
135        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
136        P::Solution: 'static,
137    {
138        solve_via_decision_max(problem, lower, upper)
139    }
140}
141
142/// Recover an optimization value by querying the problem's decision wrapper.
143///
144/// Uses the brute-force reference solver. Returns `None` only for infeasibility;
145/// an invalid interval or an optimum outside `[lower, upper]` is an error.
146pub fn solve_via_decision<P>(
147    problem: &P,
148    lower: i64,
149    upper: i64,
150) -> Result<Option<i64>, crate::solvers::SolveError>
151where
152    P: DecisionProblemMeta + Clone + 'static,
153    P::Solution: 'static,
154    P::Value: DecisionSearchValue,
155{
156    <P::Value as DecisionSearchValue>::solve_problem(problem, lower, upper)
157}
158
159#[cfg(test)]
160#[path = "../unit_tests/solvers/decision_search.rs"]
161mod tests;
problemreductions/solvers/decision_search.rs

problemreductions/solvers/
decision_search.rs
