Innovative and Efficient Methods for Optimal Assignments
Abstract
The Assignment Problem (AP) is a fundamental combinatorial optimization problem in Operations Research (OR) that deals with the optimal one-to-one allocation of resources to activities while minimizing total cost or time or maximizing total profit. This study presents a comparative investigation of different approaches for solving the Assignment Problem, including the Complete Enumeration (Brute Force) method, Hungarian method, Linear Programming (LP), and a proposed Alternate Method. The study also incorporates Python programming to enable the computational implementation and verification of the obtained solutions. Numerical examples of different dimensions are considered to examine the effectiveness and computational suitability of these approaches. The results demonstrate that the Complete Enumeration method is simple and useful for small-sized problems but becomes computationally inefficient as the problem dimension increases due to the factorial growth in the number of possible assignments. In contrast, the Hungarian method provides a systematic procedure for obtaining optimal solutions efficiently. The study further validates that Linear Programming produces optimal solutions consistent with those obtained using the Hungarian method. The proposed Alternate Method provides a simple and convenient computational framework for solving Assignment Problems and can be effectively supported by Python programming. The findings highlight the practical usefulness of combining analytical and computational approaches for obtaining and verifying optimal assignment solutions and provide a basis for further investigation of efficient methods for larger-scale Assignment Problems.
Full Text
Tables and figures are in the full-text PDF.
Introduction
Assignment problem is a special LPP which deals with assignment of workers to machines, clerks to various checkout counters, salesman to diverse sales areas, and service crews to different districts and so on. Assignment is a problem because people possess varying abilities for carrying out different jobs and therefore, the costs of performing those jobs by different people are different. Obviously, if all persons could do a job in the same time or at the same cost then it would not matter who among them is assigned the job. Thus, in an assignment problem, the question is how the assignments should be made in order that the total cost involved is minimized (or the total value is maximized when pay offs are given in terms of, say, profits) [1] .
There are four methods of solving an assignment problem namely • Complete enumeration method.
• Hungarian assignment method.
The first three methods are not efficient in handling assignment problems. Aringhieri et al. (2015) presented a two-stage heuristic algorithm for the assignment problem. The algorithm was tested using real data collected from a state hospital in Genova, Italy. The results show that the proposed method performs well in terms of both solution quality and computation time [2] . The AP is a special structure of transportation problem, in which number of jobs (task) is equal to number of persons (facilities). Thus, the objective of the problem is how the assignment should be made to achieved allocation. In the assignment model worker represent source and jobs represent destination. The supply amount at each source exactly 1.for example if 𝑛 = 5 person can be assigned to 5 jobs. Then the number of such possible ways is 5! = 120. This allocation will take a large time. There are many methods to develop an easy computational technique for such problem. Hungarian method is one of them See [6,7] for the history of this method.
Mathematical Formulation:
Suppose there are 𝑛-jobs which are to be performed by 𝑛persons, each of whom can perform each of the jobs with varying of efficiency. Suppose 𝑖 𝑡ℎ person is assigned to job 𝐽 𝑖 . The problem then is to find a permutation (𝐽 1 , 𝐽 2 , … … , 𝐽 𝑛 ) from the set of 𝑛! permutation such that the total assignment cost is minimum. Thus, the cost matrix accompanying with the problem is given as under [8] .
Problem Overview
The AP is a foundational combinatorial optimization model used in OR. The primary objective is to allocate a set of n resources (e.g., workers, machines, or vehicles) to an equal number of 𝑛 activities (e.g., jobs, tasks, or routes) on a strict one-to-one basis. The ultimate goal is to minimize total operational cost/time or maximize total profit/efficiency.
Model Components
The model formulation consists of three core components: indices, parameters, and decision variables. The indices define the respective counts of available resources and activities. The parameters consist of both predefined input values and those derived internally within the model. Finally, thedecision variable represents the actual sharing or distribution of resources to the activities.
Indices
𝑖: Index for resources (𝑖 = 1, 2, . , 𝑛) 𝑗: Index for activities (𝑖 = 1, 2, . , 𝑛)
Parameters
𝑐 𝑖𝑗: The cost, time, or penalty associated with assigning resource 𝑖 to activity 𝑗. 𝑝 𝑖𝑗: The profit, rating, or efficiency associated with assigning resource 𝑖 to activity 𝑗.
Decision Variables
The problem utilizes binary decision variables (𝑥 𝑖𝑗 ) to represent the allocation strategy:
1, if resource 𝑖 is assigned to activity 𝑗 0, otherwise.
The Linear Programming Model
Objective Functions: For cost minimization problems: Minimize
For profit maximization problems: Maximize
Constraints
• Resource Constraints (Row Constraints):Each resource must be assigned to exactly one activity.
• Activity Constraints (Column Constraints):Each activity must receive exactly one resource.
• Integrity Constraints: Decision variables are strictly binary.
𝑥 𝑖𝑗 = { 1, if resource 𝑖 is assigned to activity 𝑗 0, otherwise.
Matrix Formulation
The mathematical elements can be structured as an 𝑛 × 𝑛cost matrix mapped alongside the decision variable matrix:
Mathematical Properties
The AP is a fundamental combinatorial optimization problem with several elegant mathematical properties. Here is a summary of its key characteristics.
Total Unimodularity
The constraint matrix of a standard assignment problem is totally unimodular. This guarantees that if the binary restriction (𝑥 𝑖𝑗 ∈ [0, 1]) is relaxed to a continuous bound(0 ≤ 𝑥 𝑖𝑗 ≤ 1) regular linear programming methods (like the Simplex algorithm) will inherently generate integer optimal values at the extreme points.
Degeneracy
Because the total number of resource sharing in a valid solution is always exactly 𝑛, any assignment problem modelled as a transportation framework will lead to severe structural mathematical degeneracy (2𝑛 -1 expected basic variables vs. only 𝑛 actual assignments). This makes specialized algorithms like the Hungarian method vastly more efficient than general transportation matrix routines.
Complete enumeration method
The complete enumeration method is a brute-force approach to solving an assignment problem by listing every single possible combination of allocations, calculating the total cost (or time) for each, and selecting the absolute best option.
Core Mathematical Concept
For a balanced assignment problem with 𝑛resources (e.g., workers) and 𝑛tasks (e.g., jobs), the total number of unique feasible assignments is always𝑛!.
• A 3 × 3 problem results in 3! = 6 combinations.
• A 4 × 4 problem jumps to 4! = 24 combinations.
• A 5 × 5 problem expands to 5! = 120combinations.
• A6 × 6 problem expands to 6! = 720 combinations.
Step-by-Step Procedure To evaluate the 720 options for a 6 × 6assignment, a specific cost or distance matrix is required.
Without your matrix values, it is impossible to calculate the total cost for the allocation plan (A→1, B→2, C→3, D→4, E→5, F→6) or find the optimal solution.
Why 6×6 Highlights the Limit of Enumeration
Manual Impossibility: Writing down all 720 permutations by hand would take hours and lead to calculation errors. Algorithmic Alternative: A script can check all 720 paths in less than a millisecond, but the Hungarian algorithm is still preferred as it scales efficiently to larger matrices.
Please provide your 6 × 6 grid or table values. Once provided, the absolute optimal assignment path can be calculated instantly.
Python Programming
Since you said yes, here is a python script that uses the SciPy library to solve any 6 × 6 assignment problem using the highly efficient Hungarian algorithm (Linear Sum Assignment), rather than manually writing out all 720 combinations. You can copy this code and replace the dummy numbers inside the matrix with your actual problem values. The optimal minimum cost for your matrix is 210.
Algorithm
Because you provided 6 Workers but only 3 Jobs, this is an unbalanced assignment problem. To solve it properly, 3 "Dummy Jobs" with a cost of 0 were introduced so every worker could be accounted for, leaving 3 workers unassigned. The step-by-step matrix reduction process using the Hungarian Method. Here is the step-by-step matrix reduction process for your data using the Hungarian Method.The given steps are applied to the 𝑛 × 𝑛 cost matrix to find the optimal assignment [3] .
Optimal Assignment Breakdown
Step 1: The smallest element in each row is subtracted from all elements in the row.
Step 2: The smallest element in each column is subtracted from all elements in the column.
Step 3: A minimum number of lines are drawn to cover all 0 in the cost matrix.
Step 4: Test for Optimality 1. If the minimum number of lines is 𝑛, an optimal assignment and we are finished. 2. If lines are less than 𝑛, an optimal assignment is not yet possible. In that case, go to Step 5.
Step 5: Determine the slightest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to Step 3. If the number of rows and columns in the cost matrix are unequal, the assignment problem is unbalanced. In this case it is not appropriate to use the Hungarian algorithm. Thus, any AP should be balanced before it is solved by the Hungarian method [4,5] .Because your matrix is unbalanced (6 Workers, 3 Jobs), the very first rule of the assignment problem is to make it balanced by introducing three "Dummy" columns (Job 4, Job 5, Job 6) with a cost of 0.
Step Step 2: Row Reduction Subtract the smallest element of each row from all elements in that row. Note: Since every single row already contains a 0 (in the dummy columns), subtracting 0 does not change any numbers. The matrix remains exactly the same as Step 1.
Step 3: Column Reduction Find the smallest number in each column of the current matrix, and subtract it from every number in that column.
• Step 4: Draw Minimum Lines to Cover All Zeros We must draw the absolute minimum number of horizontal or vertical lines to cover all the 0 values in the matrix.
• Draw 1 vertical line through Dummy 4.
• Draw 1 vertical line through Dummy 5.
• Draw 1 vertical line through Dummy 6.
• Draw 1 horizontal line through Row B (covers two remaining zeros). • Draw 1 horizontal line through Row F (covers one remaining zero).
Total Lines Drawn = 5 Matrix Size (N) = 6
Since the number of lines ( 5) is less than the matrix size (6), the optimal assignment cannot be made yet. We must modify the matrix.
Step To solve an assignment problem for maximizing profit instead of minimizing cost or time, you use the exact same Hungarian Method, but with one critical introductory step: creating an Opportunity Loss Matrix [1,2,3] . Because the Hungarian Method is natively designed to find the lowest numbers, you must convert your highest profit values into the "smallest losses".
The Conversion Rule
Find the absolute largest number in your entire starting profit matrix. Then, subtract every single cell value in the matrix from that largest number [4,5,6] . This flips the problem: the maximum profit cell becomes 0 (the minimum possible loss), and the lowest profit cell becomes the largest value [7,8] .
References
- Güneri Öİ, Durmuş B, Aydın D. Different approaches to solution of the assignment problem using R program. J Math Stat Sci. 2019;5:129-145.
- Aringhieri R, Landa P, Soriano P, Tanfani E, Testi A. A two level metaheuristic for the operating room scheduling and assignment problem. Comput Oper Res. 2015;54:2134.
- Amponsah SK, Otoo D, Salhi S, Quayson E. Proposed heuristic method for solving assignment problems. Am J Oper Res. 2016;6(6):436-441.
- Winston WL. Operations research: applications and algorithms. 4th ed. Belmont: Thomson Brooks/Cole; 2004.
- Gillett BE. Introduction to operations research: a computer-oriented algorithmic approach. New York: McGraw-Hill; 1976.
- Bazaraa MS, Jarvis JJ, Sherali HD. Linear programming and network flows. 4th ed. Hoboken: John Wiley & Sons; 2010. p. 513-542.
- Gupta PK. Operations research. Meerut: Krishna Prakashan Media; 2008. p. 485-534.
- Rana SS. New proposed approach for solving assignment problem and a comparative study with Hungarian method. Int J Interdiscipl Res Innov. 2018;6(3):717-721.
How this paper connects to the literature. Drag to explore, click any node to open that paper.