Skip to content
Snippets Groups Projects
Select Git revision
  • master default
  • final_version_project_thesis_colin_wulf
2 results
Compare
Forked from cm-projects / dw1000_driver_freertos
Source project has a limited visibility.
Name Last commit Last update
sheets
.gitignore
README.md
README.md

Algorithms Lab - Summer 2023

Optimization problems occur in many practical applications of computer science, such as planning routes or scheduling jobs. Some of them, e.g. shortest paths, are easy to solve to optimality, at least with the proper theoretical background. Many of them are not and can be proved to be NP-hard, i.e., there is probably no algorithm that can solve every instance of the problem efficiently to provable optimality. The most common tactic for these cases is to just implement a heuristic, e.g., a genetic algorithm. But is this really there really no hope for an optimal algorithm? During this lab, we will investigate three techniques that can actually compute optimal solutions in reasonable time for instances of reasonable size for many problems. These techniques are:

  • Constraint Programming with CP-SAT. A very generic technique that allows you to specify the constraints of the problem and it will try to solve it by a portfolio of techniques, especially the next mentioned two.
  • SAT Solver that can often solve very large logical formulas, and by a clever application can also be tricked into solving optimization problems.
  • Mixed Integer Programming that can be used to solve optimization problems expressible by integer and fractional variables and linear constraints.

A trained algorithm engineer or operations researcher is actually able to model most combinatorial optimization problems with one of these techniques, even if they contain complex constraints or objective functions. At the end of the semester, you will be able to solve many problems with these tools, too. Of course it is not just about how well a problem can be modelled but also, how effective the underlying engine can solve it; these are NP-hard problems after all.

Content

The lab consists of four sheets and a final project.

  • In the first sheet, you will set up the programming environment and take a peek into some actual code.
  • The second sheet will have you use CP-SAT, the most generic technique.
  • The third sheet makes you use a SAT-solver, which are more rudimentary but can actually deal with much more variables than CP-SAT.
  • The fourth sheet then makes you use a Mixed Integer Programming solver, which are especially powerful, e.g., for network problems.

In a final project, your team has to get creative and develop a solver for an NP-hard optimization problem of your choice. We will help you select one.

We are always looking for excellent students that can help us as student assistants (HiWi) with research projects (and potentially even start a research career here). Students showing their skills with excellent projects may get offered to continue their project (if it is academically interesting) or to work with us on other projects.

Requirements

  • Good programming skills in Python, as the whole course will be in Python and there won't be time for us to teach you Python.
  • Basic knowledge on algorithms. Algorithms and Data Structures 1 is mandatory. Algorithms and Data Structures 2 and Network Algorithms are recommendable. If you already attended Algorithm Engineering (Keldenich/Krupke) you may be overqualified for the first part and can directly start with a project.
  • A unix system (can be a virtual machine) and basic knowledge on how to use it. It is possible to run most things also on Windows, but we cannot provide support.
  • Basic skills with Git. This is actually something you can quickly learn, but you have to do it on your own.

Timeline

    1. April: Kickoff
    • Who are we?
    • Who are you?
    • What is this lab about?
    • How will this lab be organized?
    • What will be the first task?
    • Team assignments. Special treatment for master or already experienced students.

The following dates are not final, yet. We will dynamically adapt based on your needs:

    1. May: Handout second sheet, for the fast teams.
    1. May: Deadline/Presentation first sheet.
    1. May: Handout third sheet.
    1. May: Deadline/Presentation second sheet.
    1. May: Handout fourth sheet.
    1. June: Deadline/Presentation third sheet.
    1. June: Deadline/Presentation fourth sheet. Start of project.
    1. September: Deadline for project.

Project Ideas

Your project can be of different flavors (which you can also mix):

  • Educational: Create something that teaches student how to use one of the techniques or how they work. For example you could create an applet that lets you learn about Branch and Bound.
  • Applied Optimization: Find a difficult optimization problem and implement a tool to optimize it. For example you could try to design a better tool for the SEP-assignment. This should either come with a nice user interface or an extensive empirical evaluation (i.e., something you can present).
  • Game/Puzzle: Many puzzles can be solved via one of the techniques you learned here. You could think about a game for which you can compute the optimal solution using one of the techniques and either evaluate the performance of the player based on it, or just use it to find good puzzles or just their solutions.

The primary requirement for you project is to have one of the techniques (CP-SAT, SAT, MIP) learned during the beginning of the lab as a fundamental component. However, it does not have to be the biggest component (e.g., if you create a game). Please think about a project you want to do and talk with us about your ideas.

Here is a list of potential problems:

  • Puzzle: Given a polyomino, place a minimal number of knights such that every field in the polyomino is covered. You can also state a random set of figures and quantities and ask for a full covering placement.
  • Vehicle Routing: There is an abundant amount of touring problems you could write a solver for. E.g., picking up food from various restaurants with a set of drones and delivering it to customers as quickly as possible.
  • Scheduling and Assignment: There are also many scheduling variants you could optimize. E.g., schedule the time table for some competition such that the breaks for the participants between matches are maximized.
  • Write an applet that lets you learn how Branch and Bound works (e.g., for the Knapsack-problem you learned about in AuD2).
  • Write an applet that lets you learn how the DPLL-algoritm works.

Lectures to go next

This lab is just a quick peek into solving NP-hard problems in practice, there is more!

  • Algorithm Engineering (Master, infrequently) will teach you a superset of this lab, with more details.
  • Mathematische Methode der Algorithmik (Master) will teach you the theoretical background of Linear Programming and Mixed Integer Programming.
  • Approximation Algorithms (Master) will teach you theoretical aspects of how to approximate NP-hard problems with guarantees. While this takes a theoretical point of view, the theoretical understanding can improve your practical skills on understanding and solving such problems.