Sarntal Ferienakademie, Kurs 1: Moderne Suchmethoden der Informatik: Trends und Potenzial

Introduction

Since 1984, the Ferienakademie offers a variety of courses for the talented and interested students of the three universities. This years Course 1 has taken place at the inn Feldrand, where it has been accomodated together with Course 4 (Fluid-Structure Interaction from the Nano- to the Macroscale).

During the first part of the course, we studied the most important results about combinatorial optimization. Most combinatorial optimization problems are NP-complete or even more complex and therefore no efficient algorithms that calculate the optimal solutions are known. In the course, we studied how to find not optimal but still good solutions for such problems.

In the second part of the course, we studied nature-inspired methods for blackbox optimization. In contrary to the first part where we had focused on very well-studied problems with sophisticated, problem specific algorithms, we have seen the actual problem as a black box during the second part of the course. Such methods apply in cases where information about the shape of the function to be optimized is not available. Despite the fact that formal proofs on this field are rare, we have seen and proved some facts about the behavior of such algorithms and approached the bound of current research.

As a practical component, the students of the course programmed several of these nature-inspired algorithms and observed the phenomena described by the analysis. Also the efficiencies of different methods were compared.

Lecturers

The course has been held by Prof. Ernst W. Mayr from Technische Universität München and Prof. Rolf Wanka from Friedrich-Alexander-Universität Erlangen-Nürnberg. The course has been accompanied by Manuel Schmitt from Friedrich-Alexander-Universität Erlangen-Nürnberg.

Presentations

Each student had 90 minutes for the presentation which could be organised quite freely. There were, among others, the following possibilities:

After the talk, there was time for questions and discussions, usually lasting another 30 minutes.

Thus, in each session we had about 2 presentations. The language for presentations was either English or German.

Each participant also wrote a paper (of about 10 pages) giving an introduction to the subject of the associated talk on the level of the course.

Topics

An overview of methods of organic computing and the techniques to analyze them is given by Frank Neumann and Carsten Witt. Deeper knowledge about PSO can be found in the PhD-Thesis of Sabine Helwig.
Topic Student Literature
1. Fundamentals of Optimization Problems Ernst W. Mayr

Slides
  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
    Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Problems, pp. 22-38 pdf, 87-152 pdf
    Springer-Verlag: Berlin-Heidelberg-New York, 1999

  • J. Hromkovič:
    Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, pp. 213-238
    Springer-Verlag: Berlin-Heidelberg-New York, 2001
    pdf

  • R. Wanka:
    Approximationsalgorithmen - Eine Einführung, pp. 81-85
    B.G. Teubner Verlag: Wiesbaden, 2006
    pdf
2. The Knapsack Problem Florian Pawlik

Slides, Paper
  • J. Hromkovič:
    Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, pp. 238-248
    Springer-Verlag: Berlin-Heidelberg-New York, 2001
    pdf
3. Dynamic Programming for Counting the Number of Knapsack Solutions Julius Kobold

Slides, Paper
  • M. Dyer.
    Approximate counting by dynamic programming.
    in: Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 693-699, 2003.
    10.1145/780542.780643
    pdf

  • P. Gopalan, A. Klivans, R. Meka, D. Stefankovic, S. Vempala, E. Vigoda.
    An FPTAS for #Knapsack and Related Counting Problems.
    in: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), pp. 817-826, 2011
    doi:10.1109/FOCS.2011.32
    pdf
4. Blind Search Sophia Koch

Slides, Paper
  • M. Dietzfelbinger, J. E. Rowe, I. Wegener, Ph. Woelfel:
    Tight Bounds for Blind Search on the Integers and the Reals.
    in: Combinatorics, Probability and Computing 19 (2010) 711-728.
    doi:10.1017/S0963548309990599
    pdf
5. Particle Swarm Optimization (PSO) and Parameter Selection Christoph Strößner

Slides, Paper
  • M. Jiang, Y. P. Luo, S. Y. Yang:
    Particle swarm optimization - stochastic trajectory analysis and parameter selection.
    In Felix T. S. Chan and Manoj Kumar Tiwari, editors, Swarm Intelligence - Focus on Ant and Particle Swarm Optimization, chapter 17, pages 179-198. I-TECH Education and Publishing, Vienna, 2007.
    doi:10.5772/5104
    pdf

    For background information, also refer to:
    Sabine Helwig.
    Particle Swarms for Constrained Optimization.
    Ph.D. Thesis, University of Erlangen-Nuremberg, 2010. (full text is available here)

6. Particle Swarm Optimization for Discrete Problems (PSO) Yushan Liu

Slides, Paper
  • M. Clerc:
    Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem
    2000.
    Paper and source files

  • M. Hoffmann, M. Mühlenthaler, S. Helwig, R. Wanka:
    Discrete Particle Swarm Optimization for TSP: Theoretical Results and Experimental Evaluations.
    in: Proc. International Conference on Adaptive and Intelligent Systems (ICAIS), pp. 416-427, 2011.
    doi:10.1007/978-3-642-23857-4_40
    pdf
7. Evolutionary Algorithms for Sorting and Shortest Path Computation (EA) Dominik Schmid

Slides, Paper
  • J. Scharnow, K. Tinnefeld, I. Wegener:
    The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths Problems.
    Journal of Mathematical Modelling and Algorithms 3 (2004) 349-366.
    doi:10.1023/B:JMMA.0000049379.14872.f5
    pdf
8. Evolutionary Algorithms for Minimum Spanning Trees (EA) Martin Bullinger

Slides, Paper
  • F. Neumann, I. Wegener:
    Randomized local search, evolutionary algorithms, and the minimum spanning tree problem.
    Theoretical Computer Science 378 (2007) 32-40.
    doi:10.1016/j.tcs.2006.11.002
    pdf
9. A Slime Mold Computes Shortest Paths Lukas Eisert

Slides, Paper
  • L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, K. Mehlhorn.
    Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds.
    in: Proc. 40th Int'l Colloquium on Automata, Languages, and Programming (ICALP), Part II, pp. 472-483, 2013.
    doi:10.1007/978-3-642-39212-2_42
    pdf
10. The Satisfiability Problem: Random Walk and Derandomization Timo Eckstein

Slides, Paper
  • U. Schöning.
    A probabilistic algorithm for k-SAT based on limited local search and restart.
    Algorithmica 32 (2002) 615-623.
    Paper beim Autor
    pdf

  • R. A. Moser, D. Scheder.
    A Full Derandomization of Schöning's k-SAT Algorithm.
    in: Proc. 43rd ACM Symp. on Theory of Computing (STOC), pp. 245-251, 2011.
    doi:10.1145/1993636.1993670
    pdf
11. Constructive Proof of the Lovasz Local Lemma Katharina Angermeier

Slides, Paper
  • H. Gebauer, R. A. Moser, D. Scheder, E. Welzl.
    The Lovasz Local Lemma and Satisfiability.
    Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pp. 30-54, 2009.
    doi:10.1007/978-3-642-03456-5_3
    pdf
12. Counting the Number of Satisfying Assignments Stefan Ploner

Slides, Paper
  • M. Thurley.
    An approximation algorithm for #k-SAT
    in: Proc. 29th Int. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 78-87.
    doi:10.4230/LIPIcs.STACS.2012.78
    pdf

  • M. Schmitt, R. Wanka.
    Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT
    Information Processing Letters (2013), pp. 337-344.
    doi:10.1016/j.ipl.2013.02.013
    pdf
13. Randomized Optimization Algorithms Manuel Schmitt

Slides
  • D.S. Hochbaum:
    Approximation Algorithms for NP-hard Problems, pp. 447-459
    PWS Publishing Company: Boston, 1997
    pdf

  • G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
    Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Problems, pp. 153-174
    Springer-Verlag: Berlin-Heidelberg-New York, 1999
    pdf
14. Approaches based on the Primal-Dual Paradigm Arya Moorthy

  • D.S. Hochbaum:
    Approximation Algorithms for NP-hard Problems, pp. 144-165
    PWS Publishing Company: Boston, 1997
    pdf

Project Work

In addition to the various talks, the students have worked on a programming project where the aim was to study the discussed organic methods, i.e., particle swarm optimization and evolutionary algorithms, on a number of common benchmark functions. The description of the project can be found here. The participants worked in three groups, using different programming languages. The results and the source code of their programmes can be downloaded below:

Time Line

Day Events
Sunday, 21-9-14
  • Arrival at Feldrand for dinner
  • Introduction of the course
    Monday, 22-9-14
    • General remarks about hiking in the mountains
    • Talk: Ernst W. Mayr - Fundamentals of Optimization Problems
    • Talk: Florian Pawlik - The Knapsack Problem
    • Talk: Julius Kobold - Dynamic Programming for Counting the Number of Knapsack Solutions (1)
      Tuesday, 23-9-14
      • Talk: Julius Kobold - Dynamic Programming for Counting the Number of Knapsack Solutions (2)
      • Talk: Sophia Koch - Blind Search
      • Afternoon: First hike to the Penser Joch
        Wednesday, 24-9-14
        • Talk: Christoph Strößner - Particle Swarm Optimization (PSO) and Parameter Selection
        • Talk: Yushan Liu - Particle Swarm Optimization for Discrete Problems (PSO)
        • Talk: Dominik Schmid - Evolutionary Algorithms for Sorting and Shortest Path Computation (EA)
        • Talk: Martin Bullinger - Evolutionary Algorithms for Minimum Spanning Trees (EA)
        • Evening: Ceremony with the mayor
          Thursday, 25-9-14
          • Intense work on the programming project
          • Hike from Asten to the Penser Joch
            Friday, 26-9-14
            • Talk: Lukas Eisert - A Slime Mold Computes Shortest Paths
            • Talk: Timo Eckstein - The Satisfiability Problem: Random Walk and Derandomization
            • Talk: Katharina Angermeier - Constructive Proof of the Lovasz Local Lemma
              Saturday, 27-9-14
              • Tour to Bozen
              • Evening: Guest Talk of Prof. Hans Pongratz, CIO of Technische Universität München
                Sunday, 28-9-14
                • Day hike from Reinswald to Durnholz via Kassian-Spitze and Latzfonser Kreuz
                  Monday, 29-09-14
                  • Talk: Stefan Ploner - Counting the Number of Satisfying Assignments
                  • Intense work on the programming project
                  • Afternoon: Run around Lake Durnholz
                  • First Ferienakademie Schafkopf Tournament - Glorious victory for Dominik Schmid from Course 1
                    Tuesday, 30-09-14
                    • Day hike from Reinswald via Villandersberg to Kircherhof
                    • Evening: Guest Talk of Prof. Siegfried Russwurm, member of the managing board of Siemens AG
                      Wednesday, 01-10-14
                      • Talk: Manuel Schmitt - Randomized Optimization Algorithms
                      • Talk: Arya Moorthy - Approaches based on the Primal-Dual Paradigm
                      • Afternoon: Presentation of the results of the project work
                      • Evening: Semifinals in table tennis: Unfortunately, Feldrand clearly lost
                      • Evening: Semifinals in chess: Feldrand again lost the tournament, but won a knight
                        Thursday, 02-10-14
                        Friday, 03-10-14
                        • Departure from Feldrand after breakfast

                          Full archive containing all pictures, all course materials and all files related to the project can be found here (caution: size ≈ 15 GB).