problemreductions/solvers/
brute_force.rs

1//! Brute force solver that enumerates all configurations.
2
3use crate::config::ConfigIterator;
4use crate::solvers::Solver;
5use crate::traits::Problem;
6use crate::types::SolutionSize;
7
8/// A brute force solver that enumerates all possible configurations.
9///
10/// This solver is exponential in the number of variables but guarantees
11/// finding all optimal solutions.
12#[derive(Debug, Clone)]
13pub struct BruteForce {
14    /// Absolute tolerance for comparing objective values.
15    pub atol: f64,
16    /// Relative tolerance for comparing objective values.
17    pub rtol: f64,
18    /// If true, only return valid solutions.
19    pub valid_only: bool,
20}
21
22impl Default for BruteForce {
23    fn default() -> Self {
24        Self {
25            atol: 1e-10,
26            rtol: 1e-10,
27            valid_only: true,
28        }
29    }
30}
31
32impl BruteForce {
33    /// Create a new brute force solver with default tolerances.
34    pub fn new() -> Self {
35        Self::default()
36    }
37
38    /// Create a brute force solver with custom tolerances.
39    pub fn with_tolerance(atol: f64, rtol: f64) -> Self {
40        Self {
41            atol,
42            rtol,
43            valid_only: true,
44        }
45    }
46
47    /// Set whether to only return valid solutions.
48    pub fn valid_only(mut self, valid_only: bool) -> Self {
49        self.valid_only = valid_only;
50        self
51    }
52
53    /// Check if two floating point values are approximately equal.
54    fn approx_equal(&self, a: f64, b: f64) -> bool {
55        let diff = (a - b).abs();
56        diff <= self.atol || diff <= self.rtol * b.abs().max(a.abs())
57    }
58}
59
60impl Solver for BruteForce {
61    fn find_best<P: Problem>(&self, problem: &P) -> Vec<Vec<usize>> {
62        self.find_best_with_size(problem)
63            .into_iter()
64            .map(|(config, _)| config)
65            .collect()
66    }
67
68    fn find_best_with_size<P: Problem>(
69        &self,
70        problem: &P,
71    ) -> Vec<(Vec<usize>, SolutionSize<P::Size>)> {
72        let num_variables = problem.num_variables();
73        let num_flavors = problem.num_flavors();
74
75        if num_variables == 0 {
76            return vec![];
77        }
78
79        let iter = ConfigIterator::new(num_variables, num_flavors);
80        let energy_mode = problem.energy_mode();
81
82        let mut best_solutions: Vec<(Vec<usize>, SolutionSize<P::Size>)> = vec![];
83        let mut best_size: Option<P::Size> = None;
84
85        for config in iter {
86            let solution = problem.solution_size(&config);
87
88            // Skip invalid solutions if valid_only is true
89            if self.valid_only && !solution.is_valid {
90                continue;
91            }
92
93            let is_new_best = match &best_size {
94                None => true,
95                Some(current_best) => energy_mode.is_better(&solution.size, current_best),
96            };
97
98            if is_new_best {
99                best_size = Some(solution.size.clone());
100                best_solutions.clear();
101                best_solutions.push((config, solution));
102            } else if let Some(current_best) = &best_size {
103                // Check if equal to best (for collecting all optimal solutions)
104                if self.is_equal_size(&solution.size, current_best) {
105                    best_solutions.push((config, solution));
106                }
107            }
108        }
109
110        best_solutions
111    }
112}
113
114impl BruteForce {
115    /// Check if two sizes are equal (with tolerance for floating point).
116    #[allow(clippy::neg_cmp_op_on_partial_ord)]
117    fn is_equal_size<T: PartialOrd + Clone>(&self, a: &T, b: &T) -> bool {
118        // For exact types, use exact comparison via partial_cmp
119        // This works for integers and handles incomparable values correctly
120        matches!(a.partial_cmp(b), Some(std::cmp::Ordering::Equal))
121    }
122}
123
124/// Extension trait for floating point comparisons in brute force solver.
125pub trait BruteForceFloat {
126    /// Find best solutions with floating point tolerance.
127    fn find_best_float<P: Problem<Size = f64>>(
128        &self,
129        problem: &P,
130    ) -> Vec<(Vec<usize>, SolutionSize<f64>)>;
131}
132
133impl BruteForceFloat for BruteForce {
134    fn find_best_float<P: Problem<Size = f64>>(
135        &self,
136        problem: &P,
137    ) -> Vec<(Vec<usize>, SolutionSize<f64>)> {
138        let num_variables = problem.num_variables();
139        let num_flavors = problem.num_flavors();
140
141        if num_variables == 0 {
142            return vec![];
143        }
144
145        let iter = ConfigIterator::new(num_variables, num_flavors);
146        let energy_mode = problem.energy_mode();
147
148        let mut best_solutions: Vec<(Vec<usize>, SolutionSize<f64>)> = vec![];
149        let mut best_size: Option<f64> = None;
150
151        for config in iter {
152            let solution = problem.solution_size(&config);
153
154            if self.valid_only && !solution.is_valid {
155                continue;
156            }
157
158            let is_new_best = match &best_size {
159                None => true,
160                Some(current_best) => energy_mode.is_better(&solution.size, current_best),
161            };
162
163            if is_new_best {
164                best_size = Some(solution.size);
165                best_solutions.clear();
166                best_solutions.push((config, solution));
167            } else if let Some(current_best) = &best_size {
168                if self.approx_equal(solution.size, *current_best) {
169                    best_solutions.push((config, solution));
170                }
171            }
172        }
173
174        best_solutions
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181    use crate::graph_types::SimpleGraph;
182    use crate::types::{EnergyMode, ProblemSize};
183
184    // Simple maximization problem: maximize sum of selected weights
185    #[derive(Clone)]
186    struct MaxSumProblem {
187        weights: Vec<i32>,
188    }
189
190    impl Problem for MaxSumProblem {
191        const NAME: &'static str = "MaxSumProblem";
192        type GraphType = SimpleGraph;
193        type Weight = i32;
194        type Size = i32;
195
196        fn num_variables(&self) -> usize {
197            self.weights.len()
198        }
199
200        fn num_flavors(&self) -> usize {
201            2
202        }
203
204        fn problem_size(&self) -> ProblemSize {
205            ProblemSize::new(vec![("variables", self.weights.len())])
206        }
207
208        fn energy_mode(&self) -> EnergyMode {
209            EnergyMode::LargerSizeIsBetter
210        }
211
212        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
213            let sum: i32 = config
214                .iter()
215                .zip(&self.weights)
216                .map(|(&c, &w)| if c == 1 { w } else { 0 })
217                .sum();
218            SolutionSize::valid(sum)
219        }
220    }
221
222    // Simple minimization problem: minimize sum of selected weights
223    #[derive(Clone)]
224    struct MinSumProblem {
225        weights: Vec<i32>,
226    }
227
228    impl Problem for MinSumProblem {
229        const NAME: &'static str = "MinSumProblem";
230        type GraphType = SimpleGraph;
231        type Weight = i32;
232        type Size = i32;
233
234        fn num_variables(&self) -> usize {
235            self.weights.len()
236        }
237
238        fn num_flavors(&self) -> usize {
239            2
240        }
241
242        fn problem_size(&self) -> ProblemSize {
243            ProblemSize::new(vec![("variables", self.weights.len())])
244        }
245
246        fn energy_mode(&self) -> EnergyMode {
247            EnergyMode::SmallerSizeIsBetter
248        }
249
250        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
251            let sum: i32 = config
252                .iter()
253                .zip(&self.weights)
254                .map(|(&c, &w)| if c == 1 { w } else { 0 })
255                .sum();
256            SolutionSize::valid(sum)
257        }
258    }
259
260    // Problem with validity constraint: select at most one
261    #[derive(Clone)]
262    struct SelectAtMostOneProblem {
263        weights: Vec<i32>,
264    }
265
266    impl Problem for SelectAtMostOneProblem {
267        const NAME: &'static str = "SelectAtMostOneProblem";
268        type GraphType = SimpleGraph;
269        type Weight = i32;
270        type Size = i32;
271
272        fn num_variables(&self) -> usize {
273            self.weights.len()
274        }
275
276        fn num_flavors(&self) -> usize {
277            2
278        }
279
280        fn problem_size(&self) -> ProblemSize {
281            ProblemSize::new(vec![("variables", self.weights.len())])
282        }
283
284        fn energy_mode(&self) -> EnergyMode {
285            EnergyMode::LargerSizeIsBetter
286        }
287
288        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
289            let selected: usize = config.iter().sum();
290            let sum: i32 = config
291                .iter()
292                .zip(&self.weights)
293                .map(|(&c, &w)| if c == 1 { w } else { 0 })
294                .sum();
295            SolutionSize::new(sum, selected <= 1)
296        }
297    }
298
299    #[test]
300    fn test_brute_force_maximization() {
301        let problem = MaxSumProblem {
302            weights: vec![1, 2, 3],
303        };
304        let solver = BruteForce::new();
305
306        let best = solver.find_best(&problem);
307        assert_eq!(best.len(), 1);
308        assert_eq!(best[0], vec![1, 1, 1]); // Select all for max sum = 6
309    }
310
311    #[test]
312    fn test_brute_force_minimization() {
313        let problem = MinSumProblem {
314            weights: vec![1, 2, 3],
315        };
316        let solver = BruteForce::new();
317
318        let best = solver.find_best(&problem);
319        assert_eq!(best.len(), 1);
320        assert_eq!(best[0], vec![0, 0, 0]); // Select none for min sum = 0
321    }
322
323    #[test]
324    fn test_brute_force_with_validity() {
325        let problem = SelectAtMostOneProblem {
326            weights: vec![1, 5, 3],
327        };
328        let solver = BruteForce::new();
329
330        let best = solver.find_best(&problem);
331        assert_eq!(best.len(), 1);
332        assert_eq!(best[0], vec![0, 1, 0]); // Select weight 5 (max single)
333    }
334
335    #[test]
336    fn test_brute_force_multiple_optimal() {
337        let problem = MaxSumProblem {
338            weights: vec![1, 1, 1],
339        };
340        let solver = BruteForce::new();
341
342        let best = solver.find_best(&problem);
343        assert_eq!(best.len(), 1);
344        assert_eq!(best[0], vec![1, 1, 1]); // All equal, so only one optimal
345
346        // Problem with multiple optimal solutions
347        let problem2 = SelectAtMostOneProblem {
348            weights: vec![5, 5, 3],
349        };
350        let best2 = solver.find_best(&problem2);
351        assert_eq!(best2.len(), 2); // Both [1,0,0] and [0,1,0] give weight 5
352    }
353
354    #[test]
355    fn test_brute_force_with_size() {
356        let problem = MaxSumProblem {
357            weights: vec![1, 2, 3],
358        };
359        let solver = BruteForce::new();
360
361        let best = solver.find_best_with_size(&problem);
362        assert_eq!(best.len(), 1);
363        assert_eq!(best[0].0, vec![1, 1, 1]);
364        assert_eq!(best[0].1.size, 6);
365        assert!(best[0].1.is_valid);
366    }
367
368    #[test]
369    fn test_brute_force_empty_problem() {
370        let problem = MaxSumProblem { weights: vec![] };
371        let solver = BruteForce::new();
372
373        let best = solver.find_best(&problem);
374        assert!(best.is_empty());
375    }
376
377    #[test]
378    fn test_brute_force_valid_only_false() {
379        let problem = SelectAtMostOneProblem {
380            weights: vec![1, 2, 3],
381        };
382        let solver = BruteForce::new().valid_only(false);
383
384        let best = solver.find_best(&problem);
385        // With valid_only=false, the best is selecting all (sum=6) even though invalid
386        assert_eq!(best.len(), 1);
387        assert_eq!(best[0], vec![1, 1, 1]);
388    }
389
390    #[test]
391    fn test_brute_force_with_tolerance() {
392        let solver = BruteForce::with_tolerance(0.01, 0.01);
393        assert_eq!(solver.atol, 0.01);
394        assert_eq!(solver.rtol, 0.01);
395    }
396
397    // Float problem for testing BruteForceFloat
398    #[derive(Clone)]
399    struct FloatProblem {
400        weights: Vec<f64>,
401    }
402
403    impl Problem for FloatProblem {
404        const NAME: &'static str = "FloatProblem";
405        type GraphType = SimpleGraph;
406        type Weight = f64;
407        type Size = f64;
408
409        fn num_variables(&self) -> usize {
410            self.weights.len()
411        }
412
413        fn num_flavors(&self) -> usize {
414            2
415        }
416
417        fn problem_size(&self) -> ProblemSize {
418            ProblemSize::new(vec![("variables", self.weights.len())])
419        }
420
421        fn energy_mode(&self) -> EnergyMode {
422            EnergyMode::LargerSizeIsBetter
423        }
424
425        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
426            let sum: f64 = config
427                .iter()
428                .zip(&self.weights)
429                .map(|(&c, &w)| if c == 1 { w } else { 0.0 })
430                .sum();
431            SolutionSize::valid(sum)
432        }
433    }
434
435    #[test]
436    fn test_brute_force_float() {
437        use super::BruteForceFloat;
438
439        let problem = FloatProblem {
440            weights: vec![1.0, 2.0, 3.0],
441        };
442        let solver = BruteForce::new();
443
444        let best = solver.find_best_float(&problem);
445        assert_eq!(best.len(), 1);
446        assert_eq!(best[0].0, vec![1, 1, 1]);
447        assert!((best[0].1.size - 6.0).abs() < 1e-10);
448    }
449
450    #[test]
451    fn test_brute_force_float_tolerance() {
452        use super::BruteForceFloat;
453
454        // Problem where multiple solutions have nearly equal values
455        #[derive(Clone)]
456        struct NearlyEqualProblem;
457
458        impl Problem for NearlyEqualProblem {
459            const NAME: &'static str = "NearlyEqualProblem";
460            type GraphType = SimpleGraph;
461            type Weight = f64;
462            type Size = f64;
463
464            fn num_variables(&self) -> usize {
465                2
466            }
467
468            fn num_flavors(&self) -> usize {
469                2
470            }
471
472            fn problem_size(&self) -> ProblemSize {
473                ProblemSize::new(vec![("variables", 2)])
474            }
475
476            fn energy_mode(&self) -> EnergyMode {
477                EnergyMode::LargerSizeIsBetter
478            }
479
480            fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
481                let size = match (config.first(), config.get(1)) {
482                    (Some(1), Some(0)) => 10.0,
483                    (Some(0), Some(1)) => 10.0 + 1e-12, // Nearly equal
484                    _ => 0.0,
485                };
486                SolutionSize::valid(size)
487            }
488        }
489
490        let problem = NearlyEqualProblem;
491        let solver = BruteForce::with_tolerance(1e-10, 1e-10);
492
493        let best = solver.find_best_float(&problem);
494        // Both should be considered optimal due to tolerance
495        assert_eq!(best.len(), 2);
496    }
497
498    #[test]
499    fn test_brute_force_float_empty() {
500        use super::BruteForceFloat;
501
502        let problem = FloatProblem { weights: vec![] };
503        let solver = BruteForce::new();
504
505        let best = solver.find_best_float(&problem);
506        assert!(best.is_empty());
507    }
508}
problemreductions/solvers/brute_force.rs

problemreductions/solvers/
brute_force.rs
