Skip to content
No description, website, or topics provided.
C++ Python Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bin
include
obj
src
test
.clang_complete
.gitignore
Makefile
README.org

README.org

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:

OptionFull NameArgumentDescription
-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--summaryThe output will only be a summary without the full specification of theh optimal assignment.
-n--no-printNo output will be produced, and this also suppresses the -i option.
-p--print-matrixPrint 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:

OptionArgumentDescription
-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.
You can’t perform that action at this time.