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.
Near-Optimal Coverage Path Planning with Turn Costs

Dominik Krupke

In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , 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.
How Low Can We Go? Minimizing Interaction Samples for Configurable Systems

Dominik Krupke , Ahmad Moradi , Michael Perk , Phillip Keldenich , Gabriel Gehrke , Sebastian Krieter , Thomas Thüm , and Sándor P. Fekete

ACM Trans. Softw. Eng. Methodol., Jan 2025

Just Accepted

Abs

Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved.We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality, for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in 85 % of the cases; moreover, we can achieve and prove optimality of solutions for 63 % of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.