| Linear Bottleneck Assignment Problem > Didactic Software | ||
| The Threshold Algorithm solves instances of the linear bottleneck assignment problem. | ||
| See below the instructions. To start the execution, click here: | ||
| Download the free Java Virtual Machine: | ||
 |
||
| Instructions: | ||
| The Java Applet starts with a sample cost matrix, that can be modified by double clicking on the cells. The applet shows the various steps during the execution, both on the matrix and on the corresponding bipartite graph. It is possible to interact with the execution through the buttons: | ||
|
|
Show every step. | |
|
|
Only show the most significant steps: preprocessing, augmenting paths, assignments and updating of the dual variables. | |
|
|
Only show the selection of the next unassigned vertex. | |
|
|
Back (every step). | |
|
|
Back (most significant steps). | |
|
|
Back (vertex selection) | |
|
|
Stop the execution and allow editing of the cost matrix (double click on a cell). | |
|
|
Show the optimal solution. | |
| The command File -> Open in the menu bar allows to insert a new cost matrix, by loading a file written in xml-standard, according to the following template. The tag matrix wraps all the rows, and represents the root node of the xml tree. Each sub-node is identified by the row number (R1, R2, etc..) and has as many attributes as the number of columns, each one containing the cost value (e.g., e1="5" e2="2" e3="3" e4="4" ...). | ||
| For example, an input file can be like this one: | ||
| <Matrix> <R1 e1="5" e2="2" e3="3" e4="4"/> <R2 e1="7" e2="8" e3="4" e4="5"/> <R3 e1="6" e2="3" e3="5" e4="6"/> <R4 e1="2" e2="2" e3="3" e4="5"/> </Matrix> |
||
| The cost matrix can also be edited through the command Edit -> Cost Matrix Dimension. Once the dimension has been defined, a null cost matrix is instantiated, which can be modified by double clicking on the cells. | ||
| The command File -> Save As allows to store the cost matrix in an xml file. | ||
