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 Ok(None);
31    }
32
33    if !is_satisfiable(&Decision::new(problem.clone(), upper))? {
34        return Ok(None);
35    }
36
37    let mut lo = lower;
38    let mut hi = upper;
39    while lo < hi {
40        let mid = lo + (hi - lo) / 2;
41        if is_satisfiable(&Decision::new(problem.clone(), mid))? {
42            hi = mid;
43        } else {
44            lo = mid + 1;
45        }
46    }
47
48    Ok(Some(lo))
49}
50
51fn solve_via_decision_max<P>(
52    problem: &P,
53    lower: i64,
54    upper: i64,
55) -> Result<Option<i64>, crate::solvers::SolveError>
56where
57    P: DecisionProblemMeta + Problem<Value = Max<i64>> + Clone + 'static,
58    P::Solution: 'static,
59{
60    if lower > upper {
61        return Ok(None);
62    }
63
64    if !is_satisfiable(&Decision::new(problem.clone(), lower))? {
65        return Ok(None);
66    }
67
68    let mut lo = lower;
69    let mut hi = upper;
70    while lo < hi {
71        let mid = lo + (hi - lo + 1) / 2;
72        if is_satisfiable(&Decision::new(problem.clone(), mid))? {
73            lo = mid;
74        } else {
75            hi = mid - 1;
76        }
77    }
78
79    Ok(Some(lo))
80}
81
82#[doc(hidden)]
83pub trait DecisionSearchValue:
84    OptimizationValue<Inner = i64> + Clone + fmt::Debug + Serialize + DeserializeOwned
85{
86    fn solve_problem<P>(
87        problem: &P,
88        lower: i64,
89        upper: i64,
90    ) -> Result<Option<i64>, crate::solvers::SolveError>
91    where
92        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
93        P::Solution: 'static;
94}
95
96impl DecisionSearchValue for Min<i64> {
97    fn solve_problem<P>(
98        problem: &P,
99        lower: i64,
100        upper: i64,
101    ) -> Result<Option<i64>, crate::solvers::SolveError>
102    where
103        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
104        P::Solution: 'static,
105    {
106        solve_via_decision_min(problem, lower, upper)
107    }
108}
109
110impl DecisionSearchValue for Max<i64> {
111    fn solve_problem<P>(
112        problem: &P,
113        lower: i64,
114        upper: i64,
115    ) -> Result<Option<i64>, crate::solvers::SolveError>
116    where
117        P: DecisionProblemMeta + Problem<Value = Self> + Clone + 'static,
118        P::Solution: 'static,
119    {
120        solve_via_decision_max(problem, lower, upper)
121    }
122}
123
124/// Recover an optimization value by querying the problem's decision wrapper.
125pub fn solve_via_decision<P>(
126    problem: &P,
127    lower: i64,
128    upper: i64,
129) -> Result<Option<i64>, crate::solvers::SolveError>
130where
131    P: DecisionProblemMeta + Clone + 'static,
132    P::Solution: 'static,
133    P::Value: DecisionSearchValue,
134{
135    <P::Value as DecisionSearchValue>::solve_problem(problem, lower, upper)
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/solvers/decision_search.rs"]
140mod tests;
problemreductions/solvers/decision_search.rs

problemreductions/solvers/
decision_search.rs
