NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## WHAT IS IT?

A special algorithm for the assignment problem. (Hungarian method)

Theorem:
If a number is added to or subtracted from all
of the entries of any one row or column of a cost matrix,
then on optimal assignment for the resulting cost matrix
is also an optimal assignment for the original cost matrix.

The Hungarian Method:
The following algorithm applies the above theorem to a given n * n cost matrix to find an optimal assignment.
Step 1.
Subtract the smallest entry in each row from all the entries of its row.
Step 2.
Subtract the smallest entry in each column from all the entries of its column.
Step 3.
Draw lines through appropriate rows and columns so that all the zero entries of the cost matrix are covered and the minimum number of such lines is used.
Step 4.
Test for Optimality:
(i) If the minimum number of covering lines is n, an optimal assignment of zeros is possible and we are finished.
(ii) If the minimum number of covering lines is less than n, an optimal assignment of zeros is not yet possible. In that case, proceed to Step 5.
Step 5.
Determine the smallest 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.

EXAMPLE: A construction company has four large
bulldozers located at four different garages. The bulldozers
are to be moved to four different construction sites. The
distances in miles between the bulldozers and the
construction sites are given below.

How should the bulldozers be moved to the construction sites
in order to minimize the total distance traveled?

NB: The system provides a general model for the Hungarian method.

## HOW IT WORKS

The cost matrix is made visible in the habitat.
There are some breeds of turtles; mainly handlers and records.

Records are used to store the cost matrix and to perform the calculations.
We manage the original matrix, which remains constant with its cost data cells; and a clone which evolves over time to carry the heuristics so to search the solution.

Handlers are used either to manage exceptions, and also to drive the evolution of the system state over time by emulating the typical artifact of a Future Event List.

## HOW TO USE IT

Before pressing the setup button you decide if you want to run a FAT test (predefined tests used to verify the system behavior because we know the result the system must discover). You can also decide the dimension of the cost matrix, and choose to enter data manually or ask it to be created randomly.

You can also decide with a switch is you want to track in the command center (log) all the details of what the system is doing. This is specially useful to debug the code.

You the press setup followed by the go button.

The system will evolve by showing the calculation matrix, and finally will halt by showing back the original cost matrix with the selected cells in green color for the optimal solution achieved.

## THINGS TO NOTICE

Look at the code so to see the orientation to preventive quality in software developing.

You will see the managing exceptions applied policy.

You can also get interested in the way of emulating a future event list with a breed of turtles.

You can also get interested in the way of using sort of lambdas (command tasks and reporter tasks) so to emulate to some extent the polimorphism that we have in OOP languages.

## THINGS TO TRY

Use data that can provoke malconditioned matrix or non feasible solutions.
Explote the system with acid testing and try to find potential system malfunctions.

Use examples with known solution for additional SAT testing.

Use the SOLVER of a spreadsheet to cross check results.

## EXTENDING THE MODEL

You can readjust the placement of the matrix so to be able to manage larger cost matrices. Dimension could be arbitrary, but is here limited by the presentation layer, so that the observer can see the overall matrix with a glance.

## NETLOGO FEATURES

Managing exceptions, lambdas, future event list, cohorts of breeds to discriminate among subsets of breed populations.

## RELATED MODELS

NetLogo Models Library is a powerful source for learning many of the features used here in this work.

## CREDITS AND REFERENCES

http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf

http://ia700502.us.archive.org/15/items/algorithmfortrav00litt/algorithmfortrav00litt_bw.pdf

http://www.youtube.com/watch?v=LjvdXKsvUpU

http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

http://www.universalteacherpublications.com/univ/ebooks/or/Ch6/hungar.htm

Hillier, F. S. and Lieberman, G. J. Introduction to Operations Research, 8th ed. New York: McGraw-Hill, 1990.

Author: Jose Costas. September, 2013.