cpm_planner/
compare.rs

1//! Compare plan variants on the scorecard: Pareto front and weighted rank.
2
3use crate::lint::{Severity, lint};
4use crate::metrics::{Scorecard, scorecard};
5use crate::monte_carlo::{MAX_WORK, MonteCarloRequest, monte_carlo, work_size};
6use crate::plan::{PlanGraph, PlanId, PlannerError};
7use crate::planner::canonical_deliverable;
8use crate::resource_schedule::{ScheduleRequest, resource_schedule};
9use crate::revise::RevisionDiff;
10use serde::{Deserialize, Serialize};
11use std::collections::BTreeMap;
12
13fn w1() -> f32 {
14    1.0
15}
16fn w05() -> f32 {
17    0.5
18}
19
20/// Per-criterion weights for the combined score (lower score is better).
21#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
22#[serde(deny_unknown_fields)]
23pub struct CompareWeights {
24    #[serde(default = "w1")]
25    pub makespan: f32,
26    #[serde(default = "w1")]
27    pub p80: f32,
28    #[serde(default = "w1")]
29    pub criticality_risk: f32,
30    #[serde(default = "w05")]
31    pub total_effort: f32,
32    #[serde(default = "w05")]
33    pub peak_load: f32,
34}
35
36impl Default for CompareWeights {
37    fn default() -> Self {
38        Self {
39            makespan: w1(),
40            p80: w1(),
41            criticality_risk: w1(),
42            total_effort: w05(),
43            peak_load: w05(),
44        }
45    }
46}
47
48/// What to compute for every variant.
49#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
50#[serde(deny_unknown_fields)]
51pub struct CompareRequest {
52    /// Resource-level every variant against these capacities.
53    #[serde(default)]
54    pub schedule: Option<ScheduleRequest>,
55    /// Run Monte Carlo on every variant; P80 then comes from it.
56    #[serde(default)]
57    pub monte_carlo: Option<MonteCarloRequest>,
58    #[serde(default)]
59    pub weights: CompareWeights,
60}
61
62#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
63pub struct VariantComparison {
64    pub plan_id: PlanId,
65    pub variant: String,
66    pub scorecard: Scorecard,
67    /// Structural difference against the first input variant: `added`,
68    /// `removed` and `changed` (canonical definition differs) deliverable ids.
69    /// A comparison carries no runtime state, so `reopened` and
70    /// `released_locks` are always empty.
71    pub diff_vs_first: RevisionDiff,
72    pub pareto_optimal: bool,
73    pub score: f32,
74    pub rank: u32,
75    pub rationale: String,
76}
77
78#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
79pub struct Comparison {
80    /// In input order; `rank` gives the ordering.
81    pub variants: Vec<VariantComparison>,
82    pub recommended: PlanId,
83}
84
85/// Most variants one comparison accepts.
86pub const MAX_COMPARE_VARIANTS: usize = 16;
87
88/// `INVALID_GRAPH` unless `2..=MAX_COMPARE_VARIANTS` variants are given.
89pub(crate) fn check_variant_count(n: usize) -> Result<(), PlannerError> {
90    if n < 2 {
91        return Err(PlannerError::InvalidGraph {
92            reason: "compare needs at least two variants".to_string(),
93        });
94    }
95    if n > MAX_COMPARE_VARIANTS {
96        return Err(PlannerError::InvalidGraph {
97            reason: format!("compare accepts at most {MAX_COMPARE_VARIANTS} variants"),
98        });
99    }
100    Ok(())
101}
102
103/// The Monte Carlo budget is shared: `iterations × (deliverables + edges)`
104/// summed over every variant must not exceed [`MAX_WORK`].
105fn check_shared_budget(
106    inputs: &[(PlanId, String, PlanGraph)],
107    req: &MonteCarloRequest,
108) -> Result<(), PlannerError> {
109    let iterations = u64::from(req.iterations);
110    let total = inputs.iter().fold(0u64, |sum, (_, _, g)| {
111        sum.saturating_add(iterations.saturating_mul(work_size(g) as u64))
112    });
113    if total > MAX_WORK {
114        return Err(PlannerError::InvalidGraph {
115            reason: format!(
116                "compare monte carlo budget exceeded ({} iterations × nodes+edges summed over \
117                 {} variants = {total} > {MAX_WORK})",
118                req.iterations,
119                inputs.len()
120            ),
121        });
122    }
123    Ok(())
124}
125
126const CRITERIA: [&str; 5] = [
127    "makespan",
128    "p80",
129    "criticality_risk",
130    "total_effort",
131    "peak_load",
132];
133
134fn criteria(card: &Scorecard) -> [f32; 5] {
135    let makespan = card.resource_makespan.unwrap_or(card.makespan);
136    let p80 = card.monte_carlo.as_ref().map_or(makespan, |m| m.p80);
137    [
138        makespan,
139        p80,
140        card.criticality_risk as f32,
141        card.total_effort,
142        card.peak_load.unwrap_or(0.0),
143    ]
144}
145
146fn dominates(a: &[f32; 5], b: &[f32; 5]) -> bool {
147    a.iter().zip(b).all(|(x, y)| x <= y) && a.iter().zip(b).any(|(x, y)| x < y)
148}
149
150fn diff(first: &PlanGraph, other: &PlanGraph) -> RevisionDiff {
151    let canon = |g: &PlanGraph| -> BTreeMap<String, serde_json::Value> {
152        g.deliverables
153            .iter()
154            .map(|d| (d.id.clone(), canonical_deliverable(d)))
155            .collect()
156    };
157    let (a, b) = (canon(first), canon(other));
158    RevisionDiff {
159        added: b.keys().filter(|k| !a.contains_key(*k)).cloned().collect(),
160        removed: a.keys().filter(|k| !b.contains_key(*k)).cloned().collect(),
161        changed: a
162            .iter()
163            .filter(|(k, v)| b.get(*k).is_some_and(|o| o != *v))
164            .map(|(k, _)| k.clone())
165            .collect(),
166        reopened: Vec::new(),
167        released_locks: Vec::new(),
168    }
169}
170
171fn rationale(i: usize, all: &[[f32; 5]]) -> String {
172    let (mut best, mut worst) = (Vec::new(), Vec::new());
173    for (c, name) in CRITERIA.iter().enumerate() {
174        let min = all.iter().map(|v| v[c]).fold(f32::INFINITY, f32::min);
175        let max = all.iter().map(|v| v[c]).fold(f32::NEG_INFINITY, f32::max);
176        if min < max {
177            if all[i][c] <= min {
178                best.push(*name);
179            }
180            if all[i][c] >= max {
181                worst.push(*name);
182            }
183        }
184    }
185    let list = |v: &[&str]| {
186        if v.is_empty() {
187            "none".to_string()
188        } else {
189            v.join(", ")
190        }
191    };
192    format!("best: {}; worst: {}", list(&best), list(&worst))
193}
194
195/// Compare `inputs` (plan id, variant name, graph) on the scorecard.
196///
197/// Accepts 2..=[`MAX_COMPARE_VARIANTS`] inputs (`INVALID_GRAPH` otherwise).
198/// With `monte_carlo`, the work budget is shared across variants (see
199/// [`MAX_WORK`]). Pure and CPU-bound: the server runs it off the async
200/// runtime.
201pub fn compare(
202    inputs: &[(PlanId, String, PlanGraph)],
203    req: &CompareRequest,
204) -> Result<Comparison, PlannerError> {
205    check_variant_count(inputs.len())?;
206    if let Some(mc) = &req.monte_carlo {
207        check_shared_budget(inputs, mc)?;
208    }
209
210    let mut cards: Vec<Scorecard> = Vec::with_capacity(inputs.len());
211    for (_, variant, graph) in inputs {
212        let report = lint(graph);
213        if let Some(f) = report
214            .findings
215            .iter()
216            .find(|f| f.severity == Severity::Error)
217        {
218            return Err(PlannerError::InvalidGraph {
219                reason: format!("variant {variant}: {} {}", f.code, f.message),
220            });
221        }
222        let cpm = crate::schedule::compute_cpm(graph)?;
223        let sched = req
224            .schedule
225            .as_ref()
226            .map(|s| resource_schedule(graph, s))
227            .transpose()?;
228        let mut card = scorecard(graph, &cpm, sched.as_ref(), &report);
229        card.monte_carlo = req
230            .monte_carlo
231            .as_ref()
232            .map(|m| monte_carlo(graph, m))
233            .transpose()?;
234        cards.push(card);
235    }
236
237    let values: Vec<[f32; 5]> = cards.iter().map(criteria).collect();
238    let w = &req.weights;
239    let weights = [
240        w.makespan,
241        w.p80,
242        w.criticality_risk,
243        w.total_effort,
244        w.peak_load,
245    ];
246    let mins: Vec<f32> = (0..5)
247        .map(|c| values.iter().map(|v| v[c]).fold(f32::INFINITY, f32::min))
248        .collect();
249    let scores: Vec<f32> = values
250        .iter()
251        .map(|v| {
252            (0..5)
253                .filter(|&c| mins[c] > 0.0)
254                .map(|c| weights[c] * (v[c] / mins[c]))
255                .sum()
256        })
257        .collect();
258
259    let mut order: Vec<usize> = (0..inputs.len()).collect();
260    order.sort_by(|&a, &b| {
261        scores[a]
262            .total_cmp(&scores[b])
263            .then_with(|| inputs[a].0.0.cmp(&inputs[b].0.0))
264    });
265    let mut ranks = vec![0u32; inputs.len()];
266    for (pos, &i) in order.iter().enumerate() {
267        ranks[i] = u32::try_from(pos + 1).unwrap_or(u32::MAX);
268    }
269
270    let variants = cards
271        .into_iter()
272        .enumerate()
273        .map(|(i, card)| VariantComparison {
274            plan_id: inputs[i].0.clone(),
275            variant: inputs[i].1.clone(),
276            scorecard: card,
277            diff_vs_first: diff(&inputs[0].2, &inputs[i].2),
278            pareto_optimal: !values.iter().any(|o| dominates(o, &values[i])),
279            score: scores[i],
280            rank: ranks[i],
281            rationale: rationale(i, &values),
282        })
283        .collect();
284
285    Ok(Comparison {
286        variants,
287        recommended: inputs[order[0]].0.clone(),
288    })
289}
cpm_planner/compare.rs

cpm_planner/
compare.rs
