The Arrow cluster and our 22 CPLEX licenses were funded under a CFI grant. This grant requires us to complete annual reports explaining how this infrastructure is being used. If you use the cluster or CPLEX licenses for a project, large or small, please enter a bullet item here that gives a short description of your project and the role the cluster played. If you used these resources for multiple projects and/or for a period of time that spans the time periods given here, please create multiple bullets.

May 2007 -- May 2008

• Sample project: description (year(s); students/faculty involved)

May 2006 -- May 2007

• Sample project: description (year(s); students/faculty involved)
• Verifying digital circuits with continuous models: We developed a reachability analysis tool for VLSI circuits modeled by non-linear, ordinary differential equations. We used CPLEX to solve the large number of LPs that arise in the verification procedure. (2007, Chao Yan, Mark Greenstreet, paper submitted to FMCAD'07).
• Modeling boundedly rational agents in a bargaining scenario: We investigated the implementation of a new opponent model for boundedly rational players in a negotiation game. Arrow was used to run simulations of bargaining scenarios formulated as POMDPs. (2006-7; Jennifer Tillett, Kevin Leyton-Brown)
• Learning network structure using L1 regularization: many machine learning algorithms are embarassingly parallel, since they involve running the same code on different subsets of the data for purposes of cross validation, estimating error bars, etc; we used many Arrow nodes to speed up the experiments described in {"Learning Graphical Model Structure using L1-Regularization Paths", M Schmidt, A Niculescu-Mizil, K Murphy. AAAI'07}, {"Fast Optimization Methods for L1-Regularization: A Comparative Study and Two New Approaches", M Schmidt, G Fung, R Rosales. ECML'07}, and {"Accelerated Training of Conditional Random Fields with Stochastic Meta-Descent", S Viswanathan, N Schraudolph, M Schmidt, K Murphy. ICML'06}
• Bayesian learning of network structure features: in a related project, we looked at new MCMC algorithms for estimating probabilities of network features. We used Arrow to speed up the experiments described in "Bayesian structure learning using dynamic programming and MCMC", D Eaton, K Murphy, UAI'07 to appear.
• Action Graph Games: Using the arrow cluster we carried out computational experiments evaluating the performance of our proposed algorithms for action graph games, which is a compact representation of game-theoretic models. (May 2006 - ongoing; Albert Xin Jiang and Kevin Leyton-Brown, CS)
• CS 540 project: obstacle navigation project which needed to solve a MILP problem to get the trajectory. Using CPLEX(and the cluster) allowed me to construct more interesting cases and get the solutions faster than the free solver GLPK. (April 2007, Alex Gukov, CS)
• TAC SCM: Used CPLEX's MILP solver to schedule production and deliveries for a SCM scenario (Sept 2006 - on going; Erik Zawadzki, CS)
• Game-Theoretic Analysis of Network Quality-of-Service Pricing: Using the Arrow cluster and action graph game solvers, we were able to find game-theoretic solutions to many previously intractable network problems. Different network structures, quality of service technologies and pricing schemes can be solved in parallel and compared to find optimal network configurations. (2007-ongoing, David R.M. Thompson, Albert Xin Jiang, Kevin Leyton-Brown)
• Exact regularization of convex programs: I used CPLEX (thanks, Kevin!) for the numerical results of a paper (see reference below). This paper gives the most general conditions possible under which a general convex program (eg, linear, quadratic, semidefinite, second-order cone, etc) can be regularized, and a solution of the original problem still be obtained.
  • Michael P. Friedlander and Paul Tseng, Exact regularization of convex programs, To appear in SIAM Journal on Optimization. Also listed as Dept. of Computer Science Tech. Rept. TR-2006-26, November 2006 (revised April 2007).
• Empirical hardness model for SAT: Using arrow cluster, we collect SAT solvers’ runtimes data and problem instances’ features data. Empirical hardness models are trained to predict a solver’s runtime for a given problem instance based on instance’s features. We can also predict the satisfiability for an instance based on those features.(May 2006 - ongoing; Lin Xu, Holger H. Hoos and Kevin Leyton-Brown, CS)
• Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms: The arrow cluster was extensively used to run randomized local search algorithms on propositional satisfiability (SAT) instances in order to learn relationships between the characteristics of the instance, search parameter settings, and the algorithm's runtime. This work extends previous work on empirical hardness models in three important ways: incomplete randomized algorithms (as opposed to complete deterministic algorithms in past work), algorithm parameters (past work held the parameter setting of each algorithm fix), and automatically setting these parameters on a per instance basis. It is published in [1] (and the AAAI workshop if you want to mention it). This research would not have been possible in its final form without the arrow cluster.

[1] @InProceedings{HutHamHooLey06b, lauthor = "Frank Hutter and Youssef Hamadi and Kevin Leyton-Brown and Holger H. Hoos", author = "F. Hutter and Y. Hamadi and K. Leyton-Brown and H.~H. Hoos", title = "Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms", booktitle = "Principles and Practice of Constraint Programming~(CP'06)", pages = {213--228}, year={2006} }

• Automatic Algorithm Configuration based on Local Search: The arrow cluster was also heavily used for developing an automated parameter tuning mechanism for arbitrary algorithms and problem instances. It was needed in this context as the evaluation of a single parameter configurationr required running an algorithm many times on thousands of instances, each run taking up to hours. This research would not have been possible in this way without the cluster. The iterated local search algorithm developed is called ParamILS and published in [2]. It was used to tune the local search algorithm SAPS and the the tree search algorithm Spear for SAT solving, the local search algorithm GLS4MPE for the most probabble explanation (MPE) problem, and CPLEX for the winner determiniation problem (this part also required CPLEX licenses).

[2] @INPROCEEDINGS{HutHooStu07, Author = {F. Hutter and H.~H. Hoos and T. St\"{u}tzle}, lAuthor = {Frank Hutter and Holger~H. Hoos and Thomas St\"{u}tzle}, title = {Automatic Algorithm Configuration based on Local Search}, BOOKTITLE = {AAAI '07: Proceedings of the Twenty-Second Conference on Artifical Intelligence}, YEAR = {2007}, note = {To appear.} }

• Algorithm tuning for SAT competition 2007: We further used the cluster for tuning several algorithms in preparation for the SAT competition 2006. In particular, we tuned the submitted versions of SAPS (getting speedups of over an order of magnitude by being able to tune on many instances at once) and Spear (getting over an order of magnitude speedup). People involved: SAPS: Frank. Spear: Frank and Domagoj.
• Case study for algorithm tuning for real-world instances: ParamILS was also used in a further case study for tuning Spear on hard real-world hardware and software verification instances. On the cluster, we needed a week of constant tuning - without the cluster, this would have taken over a year which would have made the research impossible. This case study resulted in a further submission to a hardware-oriented conference, [3].

[3] @misc{HutBabHooHu07, author = "F. Hutter and D. Babi\'c and H. Hoos and A. Hu", title = "Boosting Verification by Automatic Tuning of Decision Procedures", year = 2007, note = "Submitted to Formal Methods in Computer Aided Design (FMCAD-07)" }

-- KevinLeytonBrown - 05 May 2007