converge-optimization 3.7.6

Optimization algorithms for converge.zone - Rust reimplementation of OR-Tools subset
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

//! Solver for Task Assignment pack
//!
//! Delegates to the Hungarian algorithm from `crate::assignment::hungarian`
//! for optimal O(n³) assignment.

use super::types::*;
use crate::assignment::{self, AssignmentProblem};
use converge_pack::gate::GateResult as Result;
use converge_pack::gate::{ProblemSpec, ReplayEnvelope, SolverReport};

/// Optimal assignment solver (Hungarian algorithm wrapper)
pub struct HungarianAssignmentSolver;

impl HungarianAssignmentSolver {
    pub fn solve(
        &self,
        input: &AssignmentInput,
        spec: &ProblemSpec,
    ) -> Result<(AssignmentOutput, SolverReport)> {
        let n = input.cost_matrix.len();

        // Convert f64 cost matrix to i64 for the Hungarian solver.
        // Scale by 1000 to preserve 3 decimal places of precision.
        let scale = 1000i64;
        let int_costs: Vec<Vec<i64>> = input
            .cost_matrix
            .iter()
            .map(|row| {
                row.iter()
                    .map(|&c| (c * scale as f64).round() as i64)
                    .collect()
            })
            .collect();

        let problem = AssignmentProblem::from_costs(int_costs);
        let solution = assignment::solve(&problem)
            .map_err(|e| converge_pack::GateError::invalid_input(e.to_string()))?;

        // Convert back: assignments[agent] = task → Vec<(agent, task)>
        let assignments: Vec<(usize, usize)> = solution
            .assignments
            .iter()
            .enumerate()
            .filter(|&(agent, _)| agent < n)
            .map(|(agent, &task)| (agent, task))
            .collect();

        let total_cost: f64 = assignments
            .iter()
            .map(|&(a, t)| input.cost_matrix[a][t])
            .sum();

        let output = AssignmentOutput {
            assignments,
            total_cost,
        };

        let replay = ReplayEnvelope::minimal(spec.seed());
        let report = SolverReport::optimal("hungarian-assignment-v1", total_cost, replay);

        Ok((output, report))
    }
}