Parallel Auction Algorithm

This is a C++ implementation of a hybrid (with both Gauss-Seidel and Jacobi components) parallel auction algorithm. Click here for the report of the project.

Compile

To compile, simply execute

make

By default, clang++ is used, and C++14 flag is turned on. To use g++ instead, you can do

make GCC=1

To turn on the debug flag -g :

make PROFILE=1

Simple Usage

This program uses the max-payoff formulation of the linear assignment problem. The min-cost formulation can be easily adapted.

bin/pauc [options]

All options are optinal:

Option	Full Name	Argument	Description
-b	--block	<nblock>	Specify the number of partitions/blocks to use for the Gauss-Seidel component. Default is 1.
-f	--file	<file>	Specify the input file. Default is ./graph.in.
-i	--summary		The output will only be a summary without the full specification of theh optimal assignment.
-n	--no-print		No output will be produced, and this also suppresses the -i option.
-p	--print-matrix		Print the full payoff matrix. Disallowed pair is denoted by -.
-s	--sim	<nsim>	Specify the number of bidders to simultaneously update on one iteration (the Jacobi component). Default is 1.

So far, only edge specification of the graph is accepted: the first line of an input file is n, the number of bidders/items; each of the following lines is of the form i j a, which means the payoff of j to i is a. All edges not present are assumed to be disallowed. See test/graph.in0 for an example. Also see the next section for a way to generate a random graph.

Example usage:

bin/pauc -f test/graph.in0

which will generate

0 gets 7
1 gets 2
2 gets 0
3 gets 1
4 gets 8
5 gets 6
6 gets 9
7 gets 5
8 gets 4
9 gets 3
Total payoff is 873
The algorithm takes a total of 21 iterations.

Test Scripts

test/genGraph.py generates a fully dense graph, with each (integer) payoff drawn uniformly from <low> to <high>. All options are optional:

Option	Argument	Description
-f	<file>	Specify the name of the generated file. Default is ./graph.in.
-h	<high>	Specify the maximum payoff. Default is 100.
-l	<low>	Specify the minimum payoff. Default is 1.
-n	<number>	Specify the number of bidders/items. Default is 100.