A parallel implementation of the Bertsekas (1979) auction algoritm for the maximum matching problem (on bipartite graphs, as in Vasconcelos and Rosenhahn 2009). The code was realized for a University project.
To compile the source code, a Makefile is provided, allowing for individual or cumulative compilation of the files for executing the auction algorithm. By default, the Makefile provides executables for gpu auction, gpu auction deterministic, gpu auction graph, and cpu auction, corresponding to the three parallel versions and the serial version. The interface for using these executables is the same, allowing for standalone usage in the following ways:
-
By providing the executable with the name of a binary file containing m, n, and an m × n integer matrix representing the graph weights, along with a value for ϵ, one can obtain the assignment found along with the final prices of each bidder and the total cost of the solution.
-
Using the arguments
-generate m n d eps [seed], you can specify the same parameters, where d indicates the edge density, to pseudo-randomly generate an instance with integer weights limited to 10000, saved in both textual and binary formats, on which the algorithm is executed, returning the results similarly to the previous case.
To generate instances in bulk from a configuration file, you can call the test case generator executable, which saves the results in binary files placed in the current folder or the destination indicated as the second parameter. In this case, the configuration files must have the following structure:
SEED [LIMIT]on the first line to determine the generation seed and optionally a limit for the maximum weight size to use (otherwise, the maximum possible value is chosen).- A series of lines, one per instance, with the format
m n densityto indicate the corresponding initialization parameters.
To generate test cases and run the algorithms to obtain the results discussed in section B previously, you can sequentially invoke the commands make generate testcases (which will use approximately 14 GB of disk space) and make run tests to start the computation. The results are saved in the current folder in JSON format.
For compiling the standalone executables, the presence of the CUDA compiler nvcc is required, while running the tests requires having Python version 3 installed, callable through the python3 command.