#+OPTIONS: toc:nil #+TITLE: @@html:@@P@@html:@@arallel @@html:@@Auc@@html:@@tion Algorithm

This is a C++ implementation of a hybrid (with both Gauss-Seidel and Jacobi components) parallel auction algorithm. [[http://stanford.edu/~rezab/classes/cme323/S16/projects_reports/jin.pdf][Click here for the report of the project]].

• Compile To compile, simply execute #+BEGIN_SRC sh make #+END_SRC By default, clang++ is used, and C++14 flag is turned on. To use g++ instead, you can do #+BEGIN_SRC sh make GCC=1 #+END_SRC To turn on the debug flag ~-g~ : #+BEGIN_SRC sh make PROFILE=1 #+END_SRC
• Simple Usage This program uses the max-payoff formulation of the linear assignment problem. The min-cost formulation can be easily adapted. #+BEGIN_SRC sh bin/pauc [options] #+END_SRC All options are optinal: | Option | Full Name | Argument | Description | |--------+------------------+------------+---------------------------------------------------------------------------------------------------------------| | ~-b~ | ~--block~ | ~~ | Specify the number of partitions/blocks to use for the Gauss-Seidel component. Default is 1. | | ~-f~ | ~--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~ | ~~ | 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: #+BEGIN_SRC sh bin/pauc -f test/graph.in0 #+END_SRC which will generate #+BEGIN_SRC sh 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. #+END_SRC

- ~-b, --block ~ :

- ~-f, --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 ~ : Specify the number of bidders to simultaneously update on one iteration (the Jacobi component). Default is 1.

• Test Scripts ~test/genGraph.py~ generates a fully dense graph, with each (integer) payoff drawn uniformly from ~~ to ~~. All options are optional: | Option | Argument | Description | |--------+------------+------------------------------------------------------------------| | ~-f~ | ~~ | Specify the name of the generated file. Default is ~./graph.in~. | | ~-h~ | ~~ | Specify the maximum payoff. Default is 100. | | ~-l~ | ~~ | Specify the minimum payoff. Default is 1. | | ~-n~ | ~~ | Specify the number of bidders/items. Default is 100. | |--------+------------+------------------------------------------------------------------|