Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Übersicht
  - Team
  - Lehre
  - Arbeiten & Jobs
  - Forschung
  - Publikationen
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- Forschungsverbünde
  - IST.hub

Algorithmik-Praktikum: Solving NP-hard Problems in Practice

Semester	Wintersemester 2024/2025 Sommersemester 2024 Wintersemester 2023/2024 Sommersemester 2023 Wintersemester 2021/2022 Sommersemester 2021 Wintersemester 2020/2021 Sommersemester 2019
Modulnummer	INF-ALG-10
Studiengänge	Informatik Bachelor, Wirtschaftsinformatik Bachelor
IBR Gruppe	ALG (Prof. Fekete)
Art	Praktikum
Dozent	Dr. Dominik Krupke Wissenschaftlicher Mitarbeiter krupke[[at]]ibr.cs.tu-bs.de +49 531 3913112 Raum 317
LP	5
SWS	0+3
Ort & Zeit	We will have regular slots in which you can present your progress and get help. You do not have to attend the whole slot and also not every week, though, many students like to use these slots to work in a group and have the ability to directly ask questions.
Beginn	Kickoff: Tuesday, 2024-10-15, 16:45, IZ305. (please let me know if you cannot make it to the kickoff, and we may be able to find a solution.)
Voraussetzungen	For a successful experience in this course and to effectively work on the projects, students are expected to meet the following prerequisites: Proficiency in Python: The course's programming components will be exclusively conducted in Python. It is essential that you have a solid grasp of Python, as there will not be sufficient time to learn the language during the course. Algorithmic Foundations: Completion of Algorithms and Data Structures 1 is compulsory for foundational knowledge. It is advisable to have also completed (or complete in parallel) Algorithms and Data Structures 2 and Network Algorithms to be better prepared for the more complex topics. Additionally, it is beneficial to have attended Logic for Computer Scientist and Theoretical Computer Science I+II to be familiar with NP-hardness and propositional logic. Unix-Based Operating System: Access to a Unix system, which could be in the form of a virtual machine, is required for the course. Students should possess a fundamental understanding of Unix command-line operations. While most of the tools and software used in this course are compatible with Windows, support for Windows-specific issues cannot be guaranteed. Version Control with Git: A basic familiarity with Git is needed for version control purposes. While Git skills can be acquired swiftly, students are expected to learn them independently prior to or during the initial phase of the course. Please ensure you meet these requirements to engage fully in the course activities. If you have any questions or need clarification on the prerequisites, feel free to reach out to us.
Sprache	Deutsch/Englisch
Scheinerwerb	Wahlpflichtbereich (unbenotetes Praktikum). Wichtig: Du kannst an diesem Praktikum nur einmal teilnehmen, unabhängig davon, ob du es dir als Wahlpflicht oder Teamprojekt hast anerkennen lassen.
Anmeldung	To register for this module, please sign up for the mailing list. At the beginning of the semester, you will get a mail with the details for kickoff meeting. You can also just show up at the kickoff meeting, but a registration on the mailing list is still recommendable.
Inhalt	Optimization challenges are pervasive across numerous real-world applications within computer science, ranging from route planning to job scheduling. Certain problems, like the shortest path, can be solved efficiently and optimally with a solid theoretical foundation. However, a significant number of these challenges are classified as NP-hard, indicating that, for these problems, there is no known algorithm capable of consistently solving every instance efficiently to proven optimality. In such instances, heuristic approaches, such as genetic algorithms, are frequently employed as practical solutions. Yet, the question arises: Is it possible to devise algorithms that yield optimal solutions within a feasible timeframe for reasonably sized instances? This laboratory course is dedicated to exploring three sophisticated techniques that hold the potential for computing optimal solutions for a vast array of problems within practical limits. These techniques include: Constraint Programming with CP-SAT: This versatile methodology enables the definition of a problem’s constraints, upon which it employs a comprehensive suite of strategies, including the two techniques discussed below, to find optimal solutions. SAT Solvers: Renowned for their ability to resolve extensive logical formulas, these tools can be ingeniously adapted to address optimization challenges by transforming them into logical propositions. Mixed Integer Programming (MIP): This approach is adept at solving optimization problems characterized by integer and continuous variables under linear constraints. For algorithm engineers and operations researchers, mastering these techniques opens the door to modeling and solving a wide spectrum of combinatorial optimization problems. By the end of this course, you will have acquired the skills to leverage these powerful methodologies, enabling you to approach NP-hard problems not only with theoretical insight but with practical, actionable solutions.
Literatur/Links	Discrete Optimization Course: For those who are want to dive really deep into the topic, I recommend doing this free course on Coursera in parallel. It is very intense but also very rewarding. Probably one of the best courses I have ever seen. In Pursuit of the Traveling Salesman: This amazing book is not only a surprisingly good read, but also a great introduction to the field of optimization. It gives you a lot of the ideas that allow us to solve NP-hard problems in practice, while also gently introducing you to the way of thinking of an optimization expert. The CP-SAT Primer: Supplementary material on constraint programming by us that became kind of a book.