This package contains the source and the test data for a solver for the Kemeny Consensus problem, based on data reduction rules, dynamic programming, search tree techniques, and Integer Linear Programming. More details can be found in the following publications: 1. Robert Bredereck: Fixed-Parameter Algorithms for Computing Kemeny scores - Theory and Practice Studienarbeit (Pre Diploma Thesis), Department of Mathematics and Computer Science, University of Jena, October 2009. 2. Nadja Betzler, Robert Bredereck, and Rolf Niedermeier: Partial Kernelization for Rank Aggregation: Theory and Experiments. Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC '10) (Vol. 6478, pp. 26-37). Springer, 2010. doi:10.1007/978-3-642-17493-3_5 The current version can be obtained at http://fpt.akt.tu-berlin.de/kconsens/. It is distributed under the terms of the GNU General Public License (GPL) version 3. (See COPYING file.) The solver is written in C++. To build the program, you need the GNU gcc compiler, GNU make, cmake, and the Boost C++ Libraries (http://www.boost.org). Using other compilers or makes, or building on a non-Unix system, will probably require changes to the Makefile and the source. To build from source extract the files from [source.tar.gz] and run within the source dir: cmake . make If you don't want to build or if you don't want to get all necessary tools feel free to use the prepared binaries for 32 bit and 64 bit Linux operation systems. However, we can not guarantee that our binaries are compatible with your specific distribution. We created the binaries on Debian 6.0 (32bit and 64bit) and linked boost statically. Compiling from source has been successfully tested (without any chances in source files) on: * Ubuntu (64bit) 12.04 with gcc 4.6.3 and boost 1.48 * Ubuntu (64bit) 11.10 with gcc 4.6.1 and boost 1.46 * Debian GNU/Linux (64bit) 6.0 with gcc 4.4.5 and boost 1.42 * Debian GNU/Linux (32bit) 6.0 with gcc 4.4.5 and boost 1.42 Kconsens -- Kemeny consensus finder =================================== The program is called "kconsens". It reads an election from a file and writes the kemeny score, an optimal kemeny consensus and some computation information to the file system. Starting "kconsens" without any (or invalid) arguments print a short help text. Options ------- Option "-e" followed by name of the input election file. The election format is a simple text format, where each line describes one vote, given by its candidates separated by '>' in the preferred order. Example: 'foo.election' a>b>c>d a>b>d>c b>a>c>d The candidate names can be any combination of letters, digits, and standard special characters (as '=', space, '+', '/', ':', and so on.). Note that this election format is able to take names like 'John Doe' or even web urls like 'http://akt.tu-berlin.de/' as candidate names. The program will filter the input file with the following steps: 1. Cleaning: Each vote will contain each candidate at least once. If any vote ranks a candidate in more than one position, then the cleaned files take only the best position for each candidate. Example: a>b>a a>b Cleaned: a>b a>b The result will be written into "[inputfilename].clean" 2. Cutting: Since our implementation is not able to handle ties yet we cut all candidate out that are not ranked in all votes. Example: a>c>b b>a Cutted: a>b b>a The result will be written into "[inputfilename].complete" 3. Anonymizing: Each candidate name will to translated into a unique integer value corresponding the ranking position in the first vote. Example: a>b>c c>a>b Anonymized: 1>2>3 3>1>2 The (overall) result will be written into "[inputfilename].anoncomplete". (It contains only anonymized and complete (not partially) votes.) The anonymization dictionaly will be written to "[inputfilename].dict", where each line contains the candidate name followed by a space followed by the unique integer value. (Note: Spaces in candidate names are still no problem, because the seperating space is always the last in each line.) Example: a 1 b 2 c 3 Option "-i" prints a table (or with --verbose a human readable text) with the election attributes. The colums of the table are in the same order as the results in verbose output. Option "-s [modus]" starts the solver with modus [modus] to find an optimal kemeny consensus. modus | algorithm ----------------------------------------- -3* | gurobi ILP solution -2* | cplex ILP solution -1* | glkp ILP solution 0 | Take the cheapest vote as consensus 1 | Dynamic programming algorithm X>1 | Search tree algorithm with dirty set size X The output format of the resulting consensus is analogous to the input format. For our example above: 'foo.election.consensus' a>b>c>d * In this modus kconsens solves the Kemeny Score problem by calling the curresponding ILP solver. Option "-p" turn on the data reduction rules. This option is hightly recommented. With "--verbose", one gets human readable status output. However, both verbose and non-verbose output are written to the filsystem: [inputfilename].anoncomplete.consensus[modus].verbose [inputfilename].anoncomplete.consensus[modus].table Test data ========= The archive "testdata" contains some assorted test instances. Version history =============== 1.2 2013-March-18 improved release - more efficient data reduction (standard if you use -p) 1.1 2012-Aug-01 improved release - minor bug fixes - linking boost statically 1.0 2011-Aug-12 improved release - added cplex and gurobi as ILP solvers - computation of the consensus list from ILP solution (not only the score) - minor bug fixing - changed build system from autotools to cmake (which is much easier to use) 0.9 2010-May-01 initial public release -- Robert Bredereck (robert.bredereck@tu-berlin.de) 2012-August-01