Instructors: Dr. Dominik Krupke and Gabriel Gehrke, TU Braunschweig, IBR, Algorithms Group
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:
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. This journey is not just about crafting elegant models but also about utilizing robust solution engines to navigate the complexities of NP-hard challenges effectively.
The class is organized into two main components: a series of exercises and an in-depth final project, both of which are designed to enhance your proficiency with key optimization techniques.
The exercise sheets will be conducted in pairs, while final projects will require collaboration among groups of three to four students. To ensure equitable team composition for the final projects, we may consider individual performance in the exercises as a criterion for team formation. Our objective is to create balanced teams by pairing students of comparable skill levels. This approach is informed by our observation that teams with a mix of varying abilities can sometimes lead to an imbalance, where more proficient students may inadvertently overshadow their peers.
To ensure you are thoroughly prepared for the project phase, this class will begin with a series of exercise sheets. These exercises are carefully crafted to either introduce you to new techniques or enhance your existing knowledge of them. Designed with a hands-on approach, these tasks aim to provide you with practical exposure to relevant tools and methodologies.
Each exercise sheet is allocated a two-week completion window. However, with new sheets released on a weekly basis, you effectively have one week to work on each exercise, with an additional week serving as a buffer. While the exercises are designed to be completed within a few hours, the learning curve associated with mastering new techniques may necessitate additional time. The time required to complete each sheet may vary; for example, you might spend more time on the initial sheet and less on subsequent ones, or vice versa, depending on your familiarity with the topics covered.
| Exercise Sheet 1 | Exercise Sheet 2 | Exercise Sheet 3 | Exercise Sheet 4 |
|---|---|---|---|
| Constraint Programming with CP-SAT | DIY: Branch and Bound | SAT Solver | Mixed Integer Programming |
| 2024-04-02 to 2023-04-16 | 2024-04-9 to 2024-04-23 | 2024-04-16 to 2023-04-30 | 2024-04-23 to 2024-05-07 |
| Here you will explore the use of CP-SAT, a declarative constraint programming solver. You will learn to define your problem mathematically, allowing CP-SAT to efficiently find solutions. | This exercise delves into the foundational algorithm behind generic solvers like CP-SAT. Participants will gain insights into what these solvers require for optimal performance by exploring the Branch and Bound algorithm. | After the high-level interface provided by CP-SAT, this exercise demands a closer interaction with the core mechanics of a SAT solver. You will learn to translate complex problems into basic logical formulas. | Learn about Mixed Integer Programming (MIP), a technique favored by many optimization experts. Although not as expressive as CP-SAT, MIP offers better scalability and the opportunity to apply various optimization tricks thanks to an extensive mathematical foundation. |
In the latter part of the course, we will embark on a comprehensive final project, marking an opportunity for you to apply the methodologies and strategies discussed in the exercises to a concrete, real-world challenge. This project phase, extending over several weeks, invites you to engage deeply with a problem, under the mentorship of your tutor. The culmination of this endeavor will be a presentation, wherein you will have the chance to exhibit the outcomes of your efforts.
The essence of the project phase is to immerse you in the practical application of optimization techniques, tackling a problem that demands a blend of innovative thinking and strategic planning. You are encouraged to explore diverse approaches to the problem, aiming to devise a persuasive and effective solution.
This semester, the project centers on creating a tool for SEP-assignments, addressing the longstanding issue of their complexity and inaccessibility. The challenge involves managing a database of projects and student preferences, with the goal of optimally assigning students to projects. This requires consideration of student preferences, project capacity constraints, and additional factors such as the distribution of skills (e.g., balancing the number of frontend and backend developers) and accommodating the preferences of institutes, particularly for students with whom they have previously worked. Your task is to select the most appropriate techniques learned during the course, apply them effectively, and convincingly present your solution in a competitive setting. While this project simulates a real-world consulting scenario, there exists the potential for your solution to be implemented in practice, should it prove sufficiently robust and innovative.
Please note, as a five-credit course, you are expected to dedicate approximately 150 hours in total to coursework. This allocation includes both the exercises and the project, with no more than 50 hours slated for the exercises. Consequently, a minimum of 100 hours should be devoted to the project, ensuring a deep and productive engagement with the material and the challenge at hand.
| Project (<- click for more details) |
|---|
| 2024-05-07 to 2024-07-12 |
| Use your newly acquired skills to tackle a real-world optimization challenge! |
For a successful experience in this course and to effectively work on the projects, students are expected to meet the following prerequisites:
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.
This class is just a quick peek into solving NP-hard problems in practice, there is more!
Please let us know by opening an issue! You can also create a pull request on a separate branch, but as we have to do the changes in our internal repository (which also contains solutions), from which the public repository is automatically updated, it is easier for us if you open an issue and let us do the changes.
If you are an instructor and want to use this material in your course, feel free to do so! We are happy to share our material with you. If you have any questions, feel free to reach out to us. To get the solutions, please contact us directly from your official university email address, so we can verify that you are an instructor and not a student.