Dominik Michael Krupke

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

Minimum Scan Cover with Angular Transition Costs

Sándor P. Fekete , Linda Kleist , and Dominik Krupke

SIAM J. Discret. Math., 2021

Abs

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph \G that is embedded in Euclidean space. The edges of \G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in \Θ(\log χ(G)) while for 3D the minimum scan time is not upper bounded by \χ(G)\. We use this relationship to prove that the existence of a constant-factor approximation implies P \= NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of \\frac32 even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an Ø(c)\-approximation for \k\-colored graphs with \k≤χ(G)^c\. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph.
Robust disease module mining via enumeration of diverse prize-collecting Steiner trees

Judith Bernett , Dominik Krupke , Sepideh Sadegh , Jan Baumbach , Sándor P. Fekete , Tim Kacprowski , Markus List , and David B. Blumenthal

Bioinformatics, Jan 2022

Abs

Disease module mining methods (DMMMs) extract subgraphs that constitute candidate disease mechanisms from molecular interaction networks such as protein–protein interaction (PPI) networks. Irrespective of the employed models, DMMMs typically include non-robust steps in their workflows, i.e. the computed subnetworks vary when running the DMMMs multiple times on equivalent input. This lack of robustness has a negative effect on the trustworthiness of the obtained subnetworks and is hence detrimental for the widespread adoption of DMMMs in the biomedical sciences. To overcome this problem, we present a new DMMM called ROBUST (robust disease module mining via enumeration of diverse prize-collecting Steiner trees). In a large-scale empirical evaluation, we show that ROBUST outperforms competing methods in terms of robustness, scalability and, in most settings, functional relevance of the produced modules, measured via KEGG (Kyoto Encyclopedia of Genes and Genomes) gene set enrichment scores and overlap with DisGeNET disease genes.
Near-Optimal Coverage Path Planning with Turn Costs

Dominik Krupke

In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , Jan 2024

Abs

Coverage path planning is a fundamental challenge in robotics, with diverse applications in aerial surveillance, manufacturing, cleaning, inspection, agriculture, and more. The main objective is to devise a trajectory for an agent that efficiently covers a given area, while minimizing time or energy consumption. Existing practical approaches often lack a solid theoretical foundation, relying on purely heuristic methods, or overly abstracting the problem to a simple Traveling Salesman Problem in Grid Graphs. Moreover, the considered cost functions only rarely consider turn cost, prize-collecting variants for uneven cover demand, or arbitrary geometric regions. In this paper, we describe an array of systematic methods for handling arbitrary meshes derived from intricate, polygonal environments. This adaptation paves the way to compute efficient coverage paths with a robust theoretical foundation for real-world robotic applications. Through comprehensive evaluations, we demonstrate that the algorithm also exhibits low optimality gaps, while efficiently handling complex environments. Furthermore, we showcase its versatility in handling partial coverage and accommodating heterogeneous passage costs, offering the flexibility to trade off coverage quality and time efficiency.