problemreductions/rules/
cost.rs

1//! Cost functions for reduction path optimization.
2
3use crate::rules::registry::ReductionOverhead;
4use crate::types::ProblemSize;
5
6/// User-defined cost function for path optimization.
7pub trait PathCostFn {
8    /// Compute cost of taking an edge given current problem size.
9    fn edge_cost(&self, overhead: &ReductionOverhead, current_size: &ProblemSize) -> f64;
10}
11
12/// Minimize a single output field.
13pub struct Minimize(pub &'static str);
14
15impl PathCostFn for Minimize {
16    fn edge_cost(&self, overhead: &ReductionOverhead, size: &ProblemSize) -> f64 {
17        overhead.evaluate_output_size(size).get(self.0).unwrap_or(0) as f64
18    }
19}
20
21/// Minimize number of reduction steps.
22pub struct MinimizeSteps;
23
24impl PathCostFn for MinimizeSteps {
25    fn edge_cost(&self, _overhead: &ReductionOverhead, _size: &ProblemSize) -> f64 {
26        1.0
27    }
28}
29
30/// Minimize total output size (sum of all output field values).
31///
32/// Prefers reduction paths that produce smaller intermediate and final problems.
33/// Breaks ties that `MinimizeSteps` cannot resolve (e.g., two 2-step paths
34/// where one produces 144 ILP variables and the other 1,332).
35pub struct MinimizeOutputSize;
36
37impl PathCostFn for MinimizeOutputSize {
38    fn edge_cost(&self, overhead: &ReductionOverhead, size: &ProblemSize) -> f64 {
39        let output = overhead.evaluate_output_size(size);
40        output.total() as f64
41    }
42}
43
44/// Minimize steps first, then use output size as tiebreaker.
45///
46/// Each edge has a primary cost of `STEP_WEIGHT` (ensuring fewer-step paths
47/// always win) plus a small overhead-based cost that breaks ties between
48/// equal-step paths.
49pub struct MinimizeStepsThenOverhead;
50
51impl PathCostFn for MinimizeStepsThenOverhead {
52    fn edge_cost(&self, overhead: &ReductionOverhead, size: &ProblemSize) -> f64 {
53        // Use a large step weight to ensure step count dominates.
54        // The overhead tiebreaker uses log1p to compress the range,
55        // keeping it far smaller than STEP_WEIGHT for any realistic problem size.
56        const STEP_WEIGHT: f64 = 1e9;
57        let output = overhead.evaluate_output_size(size);
58        let overhead_tiebreaker = (1.0 + output.total() as f64).ln();
59        STEP_WEIGHT + overhead_tiebreaker
60    }
61}
62
63/// Custom cost function from closure.
64pub struct CustomCost<F>(pub F);
65
66impl<F: Fn(&ReductionOverhead, &ProblemSize) -> f64> PathCostFn for CustomCost<F> {
67    fn edge_cost(&self, overhead: &ReductionOverhead, size: &ProblemSize) -> f64 {
68        (self.0)(overhead, size)
69    }
70}
71
72#[cfg(test)]
73#[path = "../unit_tests/rules/cost.rs"]
74mod tests;
problemreductions/rules/cost.rs

problemreductions/rules/
cost.rs
