Downloads Related to my Research
|Show only:||Empirical Algorithmics||Computational Game Theory||Combinatorial Auction Winner Determination|
- Mechanical TA: Partially automated high-stakes peer grading. A web-based application enabling students to grade work from randomly selected peers in a class. The key difference from other peer-grading systems is that it uses TAs to perform selective spot-checks and thus incentivizes high-quality grading.
- HAL: A framework for the automated design and analysis of high-performance algorithms. An experimental management and analysis platform for empirical algorithmics, particularly targeting meta-algorithmics. HAL has been designed to facilitate the easy and correct use of a broad range of standardized, advanced empirical analysis and design methods; to design and perform computational experiments, including large-scale analysis and design tasks involving substantial amounts of computation on potentially large clusters of machines; and to support the development and critical assessment of novel empirical analysis and design techniques.
- SMAC and ROAR: Sequential model-based optimization for general algorithm configuration. Model-based active learning methods for the automatic, black-box configuration of algorithm parameters.
- Hydra: automatically configuring algorithms for portfolio-based selection. The software automatically builds an algorithm portfolio out of a single, highly-parameterized algorithm, targeting a given instance distribution and performance metric.
- SATzilla: A portfolio-based solver for SAT problems.
It won 3 gold and 2 silver in the 2009 SAT competition, and 3 gold, 1 silver, 1 bronze in the 2007 SAT competition. Based on
these results, it's arguably the strongest all-around SAT solver in the
- Paper (SATzilla-09): Xu, Hutter, Hoos & Leyton-Brown, 2009.
- Paper (Journal paper): Xu, Hutter, Hoos & Leyton-Brown, 2008.
- Paper (SATzilla-07): Xu, Hutter, Hoos & Leyton-Brown, 2007.
- Paper (SATzilla-04): Nudelman, Devkar, Shoham, Leyton-Brown & Hoos, 2004.
- Web page: SATzilla project page.
- SATenstein: A generalized, highly parameterized solver framework that can be configured to instantiate a broad range of existing high-performance SLS-based SAT solvers, and also over 1023 novel algorithms. We tuned it with ParamILS (see below), achieving state-of-the-art performance on all six of the widely-studied benchmarks we tried.
- ParamILS: Iterative local search for algorithm configuration. It can be used as an entirely automated, model-free approach for tuning an algorithm's parameters to optimize a performance measure such as runtime. We've applied it in a wide variety of domains, including to state-of-the-art SAT solvers and to CPLEX.
- Empirical Hardness Models. Code for building models
that predict an algorithm's runtime based on cheaply-computable features
describing a given instance. The papers below describe the construction
of these models for various different classes of algorithms, problem
- Paper: Leyton-Brown, Nudelman & Shoham, 2009.
- Paper: Xu, Hoos & Leyton-Brown, 2007.
- Paper: Hutter, Hamdi, Hoos & Leyton-Brown, 2006.
- Paper: Leyton-Brown, Nudelman, & Shoham, 2005.
- Paper: Nudelman, Leyton-Brown, Hoos, Devkar & Shoham, 2004.
- Paper: Leyton-Brown, Nudelman & Shoham, 2002.
- Web page: Empirical Hardness Models Project Page.
- Benchmark Generator for Security Games. This Java-based generator allows researchers to generate synthetic security game problems from the computationally hardest region where the deployment-to-saturation ratio is 0.5, for a variety of different problem domains. It also provides tools for computing Strong Stackelberg Equilibria of these games using both GLPK and CPLEX.
- Bayesian Action-Graph Games: An extension of the AGG representation to Bayesian games. The software enables the efficient computation of expected utility and of Bayes-Nash equilibria.
- Computational Analysis of Position Auctions. Software for representing position auctions as AGGs and finding their (possibly mixed-strategy) equilibria, as well as data from our published experiments.
- Action Graph Games. Code for computing expected utility in action-graph games, finding their Nash equilibria through GAMUT solvers, and for generating AGGs for computational experiments.
- Platform for the Empirical Testing of Multiagent Reinforcement Learning Algorithms. A Matlab program that allows large-scale experimentation on multiagent reinforcement learning algorithm. The platform also supports visualization of the experimental results, and is easily extensible.
- GAMUT: A test suite for game theoretic algorithms. An extensible Java package that generates games from one or more classes described in the game theoretic literature. It is intended to be used as input for the empirical testing of game theoretic algorithms, e.g., multiagent reinforcement learning; computation of Nash equilibria.
- Local Effect Game solver. Java program that
allows B-LEGs to be inputted graphically, and that uses myopic best response
dynamics to find a pure-strategy Nash equilibrium for the game, or (upon a
sufficient number of cycles detected) uses exhaustive enumeration to prove that
a PSNE does not exist.
- Paper: Leyton-Brown & Tennenholtz, 2003.
- Java JAR file:
To run it, either
double-click it (works on many operating systems including windows) or
from a console, type "java -jar LEG.jar". JAR files are
actually ZIP files, so if you want to modify or read the source code
just open the file with any UNZIP program.
- The downloads in this section could also be called Empirical Algorithmics; however, because they all specifically concern combinatorial auctions they're collected separately.
- CATS (Combinatorial Auction Test Suite).
Benchmark instances for combinatorial auction winner determination algorithms.
- Paper: Leyton-Brown & Shoham, 2006. This more recent work describes version 2.0, which contains many substantial enhancements and was released August 2003.
- Paper: Leyton-Brown, Pearson & Shoham, 2000.
- Web page: CATS website. Contains documentation, other downloads, etc.
Source code (ANSI C++).
- CASS (Combinatorial Auctions Structured Search). An algorithm for solving the winner determination problem for single-unit combinatorial auctions.
- CAMUS (Combinatorial Auction Multi-Unit Search). An algorithm for solving the winner determination problem for multi-unit combinatorial auctions.
- Combinatorial Auction
Code and Data. Instances
generated by CATS 2.0 for every distribution (including "legacy" distributions),
along with optimal revenue for the instance, runtimes for CPLEX 7.1/8.0 (depending on the dataset), CASS and
Gonen-Lehmann. Also included are feature values for the runtime prediction
models described in
Leyton-Brown, Nudelman & Shoham, 2008.
Warning: it appears that occasionally, CPLEX reported that it had run to optimality, but in fact computed a suboptimal value. As far as we know, the CASS and GL numbers are reliable.
Warning: each file represents CPU-years of data, and will take a long time to download!
- Fixed problem size:
- Archive: TAR.GZ 256 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Archive: TAR.GZ 144 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Archive: TAR.GZ 64 goods, 2000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Variable problem size:
- Archive: TAR.GZ 40-400 goods, 50-2000 non-dominated bids, 10 distributions, 800 instances per distribution. 2.4 Ghz Xeon, CPLEX 8.0.
- Archive: ZIP Objective function values, feature values and CPLEX, CASS and GL runtimes for all the instances listed above.
- Code for generating our features: TAR.GZ you only need this if you want to generate features for instances that aren't already in the above archives
- Matlab Pipeline used to generate empirical hardness models: ZIP
- Fixed problem size: