Browse Prior Art Database

Heuristic Algorithm for Solving the Linear Assignment Problem

IP.com Disclosure Number: IPCOM000078567D
Original Publication Date: 1973-Jan-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Raymond, TC: AUTHOR

Abstract

The linear assignment problem can be stated as follows: given (1) N men and N jobs to accomplish; and (2) the cost of having each man do each job; find the assignment of individual men to individual jobs, such that the total cost of doing all jobs is minimized. The constraints are that each man can be assigned exactly one job, and each job can be accomplished by exactly one man. (Image Omitted)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 3

Heuristic Algorithm for Solving the Linear Assignment Problem

The linear assignment problem can be stated as follows: given (1) N men and N jobs to accomplish; and (2) the cost of having each man do each job; find the assignment of individual men to individual jobs, such that the total cost of doing all jobs is minimized. The constraints are that each man can be assigned exactly one job, and each job can be accomplished by exactly one man.

(Image Omitted)

The problem is commonly encountered in computer packaging. For example, one might wish to assign the input/output tabs of a printed-circuit card to electrical networks within the card, such that wire lengths are minimized. The problem can also appear when determining the placement of modules on a printed circuit card.

There are several known methods of obtaining solutions to the problem. Methods such as the Hungarian Assignment Algorithm obtain an optimum solution, but their running times on a digital computer are normally a function of N/3/. Thus for very large N, they become impractical to apply. The approximation method known as row scan (or column scan) have running times proportional to N/2/, but the solution obtained is relatively poor, and gets worse as N gets larger. Another method, described by F. S. Hillier and M. M. Connors in Management Science, September 1966, gets a significantly better answer and retains dependence on N/2/.

New steps can be added to Hillier-Connor process to produce answers that are even closer to optimum, at little additional cost in computer running time. The running time retains dependence on N/2/, and the quality of the solution does not ordinarily get worse with increasing N.

The algorithm can be stated as follows: At the start, no rows or columns are assigned.

Step 1: Consider a row of the cost matrix. Subtract from each element in this row the smallest element of this row.

Repeat for each row. With the resulting matrix,

subtract from each column its smallest element. At least

one zero now exists in each row and column.

Step 2: While ignoring elements in assigned rows or columns, scan each row...