converge_optimization/assignment/
auction.rs

1//! Auction Algorithm for the Linear Assignment Problem
2//!
3//! The auction algorithm uses a market-based approach where agents
4//! "bid" for tasks. It's particularly efficient for sparse problems.
5//!
6//! ## Algorithm Overview
7//!
8//! 1. Agents bid on preferred tasks
9//! 2. Tasks are "sold" to highest bidder
10//! 3. Prices increase for contested tasks
11//! 4. Repeat until all agents assigned
12//!
13//! Time complexity: O(n³) worst case, often faster in practice.
14
15use super::{AssignmentProblem, AssignmentSolution, AssignmentSolver};
16use crate::{Cost, Result, SolverParams, SolverStats, SolverStatus};
17use std::time::Instant;
18
19/// Auction algorithm solver
20pub struct AuctionSolver {
21    /// Epsilon for ε-complementary slackness (default: 1)
22    pub epsilon: i64,
23}
24
25impl Default for AuctionSolver {
26    fn default() -> Self {
27        Self { epsilon: 1 }
28    }
29}
30
31impl AssignmentSolver for AuctionSolver {
32    fn solve(
33        &self,
34        problem: &AssignmentProblem,
35        params: &SolverParams,
36    ) -> Result<AssignmentSolution> {
37        solve_auction(problem, params, self.epsilon)
38    }
39
40    fn name(&self) -> &'static str {
41        "auction"
42    }
43}
44
45/// Solve using auction algorithm with default epsilon
46pub fn solve(problem: &AssignmentProblem) -> Result<AssignmentSolution> {
47    solve_auction(problem, &SolverParams::default(), 1)
48}
49
50fn solve_auction(
51    problem: &AssignmentProblem,
52    params: &SolverParams,
53    epsilon: i64,
54) -> Result<AssignmentSolution> {
55    let start = Instant::now();
56    let n = problem.num_agents;
57
58    if n == 0 || problem.num_tasks == 0 {
59        return Err(crate::Error::invalid_input("empty problem"));
60    }
61
62    if !problem.is_square() {
63        // For now, fall back to Hungarian for non-square
64        return super::hungarian::solve(problem);
65    }
66
67    // Convert to benefits (negate costs for maximization)
68    let max_cost: i64 = problem
69        .costs
70        .iter()
71        .flat_map(|row| row.iter())
72        .max()
73        .copied()
74        .unwrap_or(0);
75
76    let benefit: Vec<Vec<i64>> = problem
77        .costs
78        .iter()
79        .map(|row| row.iter().map(|&c| max_cost - c).collect())
80        .collect();
81
82    // Prices of tasks
83    let mut prices = vec![0i64; n];
84
85    // Assignment: assignment[agent] = task (-1 means unassigned)
86    let mut assignment = vec![-1i32; n];
87
88    // Reverse assignment: task_owner[task] = agent (-1 means unowned)
89    let mut task_owner = vec![-1i32; n];
90
91    let mut iterations = 0;
92    let mut unassigned: Vec<usize> = (0..n).collect();
93
94    while !unassigned.is_empty() {
95        iterations += 1;
96
97        // Check timeout
98        if params.has_time_limit() && start.elapsed().as_secs_f64() > params.time_limit_seconds {
99            return Err(crate::Error::timeout(params.time_limit_seconds));
100        }
101
102        // Process one unassigned agent
103        let agent = unassigned.pop().unwrap();
104
105        // Find best and second-best task values
106        let mut best_task = 0;
107        let mut best_value = i64::MIN;
108        let mut second_best_value = i64::MIN;
109
110        for task in 0..n {
111            let value = benefit[agent][task] - prices[task];
112            if value > best_value {
113                second_best_value = best_value;
114                best_value = value;
115                best_task = task;
116            } else if value > second_best_value {
117                second_best_value = value;
118            }
119        }
120
121        // Handle case where there's only one task
122        if second_best_value == i64::MIN {
123            second_best_value = best_value;
124        }
125
126        // Calculate bid increment
127        let bid_increment = best_value - second_best_value + epsilon;
128
129        // If task is owned by another agent, unassign them
130        let prev_owner = task_owner[best_task];
131        if prev_owner >= 0 {
132            assignment[prev_owner as usize] = -1;
133            unassigned.push(prev_owner as usize);
134        }
135
136        // Assign agent to task
137        assignment[agent] = best_task as i32;
138        task_owner[best_task] = agent as i32;
139        prices[best_task] += bid_increment;
140    }
141
142    // Convert assignment to solution
143    let assignments: Vec<usize> = assignment.iter().map(|&t| t as usize).collect();
144    let total_cost: Cost = assignments
145        .iter()
146        .enumerate()
147        .map(|(agent, &task)| problem.costs[agent][task])
148        .sum();
149
150    let elapsed = start.elapsed().as_secs_f64();
151
152    Ok(AssignmentSolution {
153        assignments,
154        total_cost,
155        status: SolverStatus::Optimal,
156        stats: SolverStats {
157            solve_time_seconds: elapsed,
158            iterations,
159            objective_value: Some(total_cost as f64),
160            ..Default::default()
161        },
162    })
163}
164
165#[cfg(test)]
166mod tests {
167    use super::*;
168
169    #[test]
170    fn test_3x3_auction() {
171        let problem =
172            AssignmentProblem::from_costs(vec![vec![10, 5, 13], vec![3, 9, 18], vec![14, 8, 7]]);
173        let solution = solve(&problem).unwrap();
174        assert_eq!(solution.total_cost, 15);
175    }
176
177    #[test]
178    fn test_2x2_auction() {
179        let problem = AssignmentProblem::from_costs(vec![vec![1, 2], vec![3, 4]]);
180        let solution = solve(&problem).unwrap();
181        assert_eq!(solution.total_cost, 5);
182    }
183}
converge_optimization/assignment/auction.rs

converge_optimization/assignment/
auction.rs
