Browse Prior Art Database

Algorithm for Many To One Assignment Problems

IP.com Disclosure Number: IPCOM000079182D
Original Publication Date: 1973-May-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 4 page(s) / 40K

Publishing Venue

IBM

Related People

Bahl, LR: AUTHOR [+2]

Abstract

I. THE PROBLEM: Given a teleprocessing network consisting of n terminals and m(

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 48% of the total text.

Page 1 of 4

Algorithm for Many To One Assignment Problems

I. THE PROBLEM: Given a teleprocessing network consisting of n terminals and m(<n) concentrators. It is desired that the terminals be connected to the concentrators in an optimal (minimum cost) fashion. The following data is available. i) c. - the cost of a link between terminal i and

concentrator j.

ii) a - the capacity of concentrator j (i.e., the maximum

number of terminals that may be connected to it).

Each terminal must be connected to some concentrator. If there were no capacity constraints, each terminal could be assigned to its nearest concentrator to obtain the minimum cost network. However, such an assignment may violate the capacity constraints, so a different method for configuring the network must be found.

More generally, two sets U = u(1),u(2),...,u(n) and V = v(1),v(2),...,v(m) are present. Associated with each v(j) is a capacity a(j). The cost of designing u(i) to v(j) is c(ij). It is desired that the u(i)'s be assigned to the v(j)'s at minimum cost. Each member of U is to be assigned to a member of V and the number of u(i)'s assigned to v(j) must not exceed the capacity a(j).

The variable x(ij) is defined for ail i=1,2,...,n and j=l,2,...,m.

(Image Omitted)

The problem is a zero-one integer programming problem. It can be considered as a special case of the transportation problem, the assignment problem or the generalized matching problem for weighted bipartite graphs. It can be solved by any number of well-known techniques such as the stepping stone method [1], Hungarian method and allied techniques [2,3], etc. Presented here is an algorithm which is computationally more efficient than other methods for solving this problem. It is somewhat similar in concept to the algorithm of Desler and Hakimi [4], but improves on it in terms of speed. The algorithm utilizes the labeling technique [5,6] which is central to most algorithms of this type.

II. THE ALGORITHM: As a vehicle for explaining the algorithm, the terminal and concentrator example mentioned in section I is used. It is, of course, assumed that the total capacity of the concentrators is at least equal to the number of terminals, otherwise a solution does not exist.

The algorithm proposed here is an iterative one. Starting with all terminals unassigned, at each iteration, one more terminal is assigned: thus exactly n iterations are necessary.

An exemplary iteration is now described. Assume that terminals 1,2,....,k-1
have been assigned in an optimal fashion and terminal K is to be assigned. At this point some concentrators may be loaded to capacity, others not. Let F = (j

1

Page 2 of 4

Integral concentrator j is loaded to capacity) E = (j Integral concentrator j is not loaded to capacity)

The costs of assigning terminal k to each of the concentrators are now examined. These costs are given by c(kj),j=1,2,....,m.

Let c - min(c(kj)) and J(k) = (j absolute c(kj) = c) J(k) is index set of concentrators to which terminal...