Dominik Michael Krupke
PostDoc Researcher/Instructor/Consultant at TU Braunschweig, Algorithms Division.
![profile-dispu.jpg](/assets/img/profile-dispu.jpg?d1ae5fb1020ea31884c713bf6290ec35)
Theoretical Mind, Practical Solutions: Mastering NP-Hard Optimization Problems.
I specialize in solving NP-hard optimization problems in practice, combining techniques such as Mixed Integer Programming, Constraint Programming, SAT solvers, and Meta-Heuristics. My current preferred framework is Adaptive Large Neighborhood Search, which allows me to effectively mix various ideas to obtain high-quality solutions even for complex problems. I describe myself as an algorithm engineer because my strength lies in engineering algorithms with any means necessary. It is difficult to fit me into a single discipline or role, so let me explain the different aspects of my work.
As a software engineer, I write high-quality code and have experience setting up, maintaining, deploying, and managing software projects. Algorithms can become complex and often require frequent iterations, so it is essential to properly modularize them to keep them testable and maintainable. I am comfortable with tools like Git, Docker, and CI pipelines, which help me integrate and deliver solutions efficiently. I am also familiar with low-level details like caching, branch prediction, linking, and mixing languages. While I quickly learn new frameworks, I sometimes need a refresher on topics like design patterns since I am not a full-time developer.
In theoretical computer science, I have a strong foundation, with my Master’s thesis and much of my PhD work focused on this field. I understand concepts like complexity, reductions, and approximation, and can quickly identify problem types like Set Cover or opportunities for dynamic programming. My Master’s thesis addressed a notable open problem (#53 of the Open Problems Project), and I have enjoyed working on topics like Minimum Scan Cover, which involved elegant theoretical proofs. However, I have become less interested in lengthy NP-hardness proofs or abstract concepts that do not have practical applications.
In mathematical optimization, I enjoy translating problems into quantifiable mathematical formulations and am familiar with concepts like cutting planes, integrality gaps, duality, symmetry breaking, and decomposition methods. While I might not be fluent in every technical term and might resort to some hand-waving when explaining more complex methods like the ellipsoid method, I am comfortable bending the rules of mathematical precision to achieve practical results.
As an operations researcher, I build efficient models and apply algorithmic techniques, especially when standard approaches fall short. I value the power of meta-heuristics for tasks like warm-starting or providing quick feedback. Although I am not deeply involved in the business aspects and prefer working directly with solvers rather than using modeling languages, I find that I am particularly valuable when a problem requires more than just running a straightforward solve
command.
As a data scientist, I regularly work with data using SQL, NoSQL, Pandas, and other frameworks. Data analysis and visualization are essential for the empirical evaluation of algorithms. I often apply techniques from machine learning, such as PCA and clustering for benchmark building, and have successfully used reinforcement learning for an optimization problem where classical methods failed. I take satisfaction in creating clean and well-documented data pipelines, often using tools like Pydantic. However, these are just tools for me, and while I am interested in AI and eager to explore new techniques, my experience with complex machine learning projects is limited.
In my role as an instructor, I have co-designed and taught courses on algorithm engineering, supervised numerous theses, and developed engaging lab exercises, which are my preferred teaching method. I received a lot of positive feedback for the CP-SAT Primer, which started as a cheat sheet but is now close to becoming a complete book. While I find teaching fulfilling, I recognize that it would not be enough to sustain me if it involved repeatedly covering the same material.
As a researcher, I have co-authored numerous papers and enjoy diving deep into new topics. I have presented at various conferences and collaborated with many peers from different fields. However, I often find the academic system frustratingly slow and inefficient. In contrast, I appreciate the faster pace and smoother processes in consulting work, where progress is more tangible and less encumbered by bureaucracy. Nonetheless, I enjoy the freedom academia provides and the collaborative, non-competitive community it fosters.
Outside of my professional roles, I am passionate about powerlifting and take a strategic approach to my training, aiming to maximize gains with minimal time investment. Given that I rarely have more than three 45-minute sessions per week, I face an intriguing optimization challenge: how to make the most progress while minimizing the risk of injury. This involves carefully balancing training variables, despite the noisy feedback from factors like sleep quality, which can significantly impact performance. The challenge of fine-tuning my regimen to account for these variables mirrors the problem-solving mindset I apply in my work.
Technical Skills
- Combinatorial Optimization: Proficient in solving NP-hard problems to optimality using techniques like Mixed Integer Programming, Constraint Programming, custom branch-and-bound algorithms, SAT-solvers, and Second Order Cone Programming.
- Approximation & Meta-heuristics: Skilled in finding near-optimal solutions via approximation algorithms, meta-heuristics, and LNS-variants.
- Algorithmic Foundations: Strong background in theoretical computer science, with a comprehensive understanding of algorithmic concepts and their practical applications, such as complexity, approximation, and graph theory.
- Programming & Performance: Adept in writing maintainable Python and C++ code for complex algorithms, with expertise in performance tuning and modularization. Check out my repositories for examples.
- Data Analysis & Visualization: Capable of managing, evaluating, and quality-checking complex data, as well as visualizing data sets for insights and decision-making. Refer to my dissertation for exemplary empirical evaluations.
- Machine Learning: Familiar with machine learning techniques and have applied them successfully in research projects. Eager to explore their potential to augment classical algorithms, although this is neither a primary focus nor an area of expertise.
Research Skills
- Theory-Practice Bridge: Skillful in bridging the gap between theoretical computer science and practical implementation, highlighted by interdisciplinary collaborations and consultancy.
- Interdisciplinary Collaboration: Extensive involvement in projects across diverse fields such as robotics, bioinformatics, automotive, and satellite management.
- Creativity & Curiosity: Demonstrated curiosity and creativity in learning and combining new techniques, as evidenced by the diverse techniques used in my dissertation and the variety of projects undertaken.
Soft Skills
- Teaching & Presentation: Proficient in teaching and presenting complex topics, as proven by the positive evaluation of my lecture on algorithm engineering and the popularity of my online material.
- Project Management: Experienced in managing multiple projects and student teams concurrently, as evidenced by the number of successfully completed projects.
Selected Publications
-
- Robust disease module mining via enumeration of diverse prize-collecting Steiner treesBioinformatics, Jan 2022
- Near-Optimal Coverage Path Planning with Turn CostsIn 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , Jan 2024