6.2 Assignment problem and Hungarian algorithm

The assignment problem tackles matching tasks to agents efficiently. It's a special case of transportation problems, with one-to-one matching and equal-sized sets. The cost matrix represents assignment costs, and the goal is to minimize total cost.

The Hungarian algorithm solves assignment problems step-by-step. It creates a reduced cost matrix, finds zeros, and iteratively improves the solution. This method guarantees an optimal assignment, making it a powerful tool for solving real-world matching problems.

Assignment Problem and Hungarian Algorithm

Assignment problem as transportation subset

• One-to-one matching between equal-sized sets assigns tasks to agents efficiently
• Supply nodes (agents) and demand nodes (tasks) all have values of 1
• Cost matrix represents assignment costs for each agent-task pair
• Balanced problem guarantees integer solution unlike general transportation problems

Linear programming for assignments

• Decision variables $x_{ij}$ (1 if agent i assigned to task j, 0 otherwise) determine optimal assignments
• Objective function minimizes total assignment cost $\sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij}$
• Constraints ensure each agent and task assigned once $\sum_{j=1}^n x_{ij} = 1$, $\sum_{i=1}^n x_{ij} = 1$
• Non-negativity and binary constraints maintain feasibility $x_{ij} \geq 0$, $x_{ij} \in \{0,1\}$

Hungarian algorithm application

1. Subtract row minima from each row in cost matrix
2. Subtract column minima from each column
3. Draw minimum lines covering all zeros
4. Create additional zeros by subtracting smallest uncovered element
5. Find complete assignment using covered zeros

• Iterative process improves solution until optimal assignment found
• Optimality proof uses dual variables and complementary slackness conditions

Reduced cost matrices in assignments

• Subtracting row and column minima creates reduced cost matrix preserving optimal solution
• Non-negative elements with at least one zero per row and column
• Reduced costs show potential objective value improvements
• Zero reduced costs indicate potentially optimal assignments
• Simplifies optimal solution search in Hungarian algorithm
• Allows visual identification of potential assignments (matching zeros)