Uni-Logo

AI for Automated Algorithm Design

News

  • Feb. 9: Added slides of last meeting
  • Nov. 4: Added two more entries to our schedule
  • Oct. 22: Added slides of first meeting
  • Oct. 1.: Added Schedule

Background

Boolean constraint solving technology has made tremendous progress over the last decade, leading to industrial-strength solvers. Although this advance in technology has occurred to a large extent in the area of propositional satisfiability (SAT), it also led to significant boosts in neighboring areas, such as Answer Set Programming (ASP), Pseudo-Boolean Solving (PB), and even (multi-valued) Constraint Solving (CSP). However, in all these areas multiple solving strategies exist that are complementary to each other, that is, no strategy dominates all other strategies on all kind of problems. This holds in many sub-communities of artificial intelligence and is well supported by empirical results in the literature, for example, propositional satisfiability (SAT), constraint satisfaction (CSP), AI planning, and supervised machine learning.

There exist several meta-solving approaches to address this problem, which we will discuss in this seminar. First, algorithm configuration considers the problem of automatically looking for a configuration of an algorithm. Second, algorithm portfolio solvers do not consist of only one solver but consider several solvers. Some portfolio solvers are running their portfolio in parallel, run a sequence of solvers (algorithm schedules) or select the right solver for a given instance (algorithm selection). Third, techniques from algorithm configuration and portfolio solvers can be combined to automatically generate state-of-the-art solvers.

In this seminar, we will discuss both foundations of these meta-solving techniques and their applications. Foundations include concepts from artificial intelligence (local search, population-based methods), optimization (mixed continuous/discrete optimization, stochastic optimization, global optimization), machine learning (regression, classification, clustering), and statistics (experimental design, statistical tests).

Possible applications span algorithms in most areas of computer science, including, e.g.: Planning, SAT, ASP, QBF, CSP, MAXSAT, machine learning and more.

Algorithm configuration is also a young and dynamic field of research, full of interesting questions for practica, semester projects, MSc theses, and so on. (If you're interested in any of these during/after the course, let me know.)

Dynamics

We will meet weekly (Wednesday 10:00-12:00 s.t., in building 051, room HS 03-026) to discuss research papers from the following list of available papers. For each paper, one participant will have the lead and give a presentation. All participants will read each paper and 3 questions about it. Furthermore, all participants will write 3 summaries of the presented papers; these will be due 2 days before the presentation (to give the presenter time to take them into account). After the presentation, all participants will discuss the paper, and its merits and limitations. This discussion will in part be guided by the questions submitted by the participants.

Towards the end of term, each participant will hand in a (relatively brief) written report, typically on the topic of the paper they presented (although a related subject is a possibility). Final marks will be formed using a combination of marks for the oral presentation and written report, quality of summaries and questions submitted, and class participation.

Overall, next to the seminar topic, you will learn several soft-skills necessary in academia: to read and understand research papers and assess their strengths and weaknesses; to orally present in front of your peers; to discuss with your peers; and to summarize on a high level a piece of research you are not intimately familiar with.

Resources

What to put into the final report?

In a nutshell, we think of this report as a detailed summary of the paper you presented that also covers points that would come up in a research discussion about the paper. (We say "paper" here even though technically, you are not restricted to write about the paper you present.) E.g., some questions that should be discussed at some point in the report next to a detailed summary are the following:

  • What is the paper's main contribution and why is it important?
  • How does it relate to other techniques in the literature?
  • What are strong and what are weak points about the paper?
  • What would be interesting follow-up work? Any possible improvements in the methods? Any further interesting applications?

Formatting and length of the final report

Final reports have to be typeset in LaTeX. We will use the formatting guidelines and electronic templates from the AI conference IJCAI: http://ijcai13.org/files/ijcai13.zip. Reports do not have to be long; 2 pages in IJCAI style are appropriate. (It is OK if it is a bit longer, but please do not go beyond 4 pages - you might not be able to include everything you would like to include, but such is life in academic writing.)