Dr. Dominik Michael Krupke

contact information

profile

PostDoc Researcher in the Algorithms Division (IBR) at University of Technology in Braunschweig, Germany. I am interested in most aspects of algorithms and data structures, but my expertise lies in optimizing difficult, i.e., NP-hard, combinatorial problems with various techniques. My dissertation showcases large parts of my toolkit, including Mixed Integer Programming (Gurobi and CPLEX), Constraint Programming (CP-SAT of Google’s ortools), SAT-solvers, Dynamic Programming, Graph Algorithms, Approximation Algorithms, Reinforcement Learning, Meta-Heuristics, etc. There is a large overlap with the fields of Operations Research and Mathematical Optimization, but I prefer the term Algorithm Engineering as I am really focused on the algorithms and have primarily been educated by theoretical computer scientists. Thus, I am not just interested in just applying and combining these tools but also to understand how and why they work so well (or don’t). Currently, I am especially fascinated by CP-SAT because it smartly combines a lot of techniques, some of which seem unwise on first sight but work surprisingly well.

My preferred programming languages are Python and C++ (if Python is too slow or if I want to play with low level stuff).

Outside the university, I like to test and expand my physical limits in weight lifting (currently at nearly 2.5x own body weight in DL) and Krav Maga. My preferred means of transport have two wheels (cyclocross bicycle and motorcycles).


Research Agenda

The following is a draft of my research agenda, which I am currently working on. If you have any feedback, please let me know: I am still a relatively young PostDoc, trying to become an independent researcher (aka professor).

Exploring and Improving Techniques to solve NP-hard Problems

Nearly a decade ago, I was introduced to a versatile tool - Mixed Integer Programming (MIP) - which I likened to a hammer. Many NP-hard problems resembled nails, requiring only a few hits from the right angle to solve them. Supported by approximation algorithms and meta-heuristics, I achieved optimal or near-optimal solutions for many problems. However, with further study, I recognized some limitations of MIP's Branch and Cut-algorithm for certain problems. This realization prompted me top explore alternatives like Constraint Programming (CP) and SAT-solvers, which proved fruitful where MIP faltered. Since then, I've been driven by curiosity to experiment with new techniques, comprehend their inner workings, acknowledge their limitations, and combine them into more powerful tools.

A highly effective framework I've employed in the recent years involves a specialized variant of Large Neighborhood Search (LNS). This technique entails iteratively deconstructing small portions of a solution, leveraging tools like MIP or CP for repair. The key lies in an intricate understanding of the problem's nuances to identify precise segments for deconstruction and establish effective repair strategies. This can necessitate the integration of multiple orthogonal strategies, enabling the seamless fusion of diverse techniques to tackle a problem. A notable, recent accomplishment in this framework is SampLNS (WIP), which uses a CP-SAT-based LNS for optimization, supported by an MIP-based LNS on an auxiliary problem for computing lower bounds and breaking symmetries, with dynamic parameter adaptation after each iteration. We can also use techniques like MIP to easily improve the performance of meta-heuristics, such as computing optimal cross-overs in population-based approaches.

Central to my research agenda is to further explore the possibilities of combining diverse techniques, especially within the (A)LNS framework. I believe that there are further problems that so far only allowed heuristic solutions, but can be solved to near-optimality with the right and adaptive combination of techniques. Additionally, there are only few researchers with a broad expertise in different techniques, which is necessary to identify the right combination of techniques. Note that there is a clear distinction to already well-established portfolio-solvers, such as CP-SAT, as the adaptive fusion happens deeper in the approach.

An LNS visualization by my students Gabriel Gehkre and Laurenz Illner

Large Neighborhood Search for TSP as simple illustration (it is more beneficial for complex, but hard to visualize, problems). Animation by my students Gabriel Gehrke and Laurenz Illner (2023).

References: (WIP=Work in Progress)

Coverage Path Planning

A problem class I have been intensively working on for a long time and from different angles is coverage path planning. In coverage path planning, an efficient trajectory has to be found that covers a given area. This problem is relevant in many applications, e.g., lawn mowing, cleaning, painting, or surveillance, but also notoriously difficult. I have been looking at the theoretical complexity of problem variants, devised approximation algorithms, engineered those, implemented MIP-models, Large Neighborhood Search (LNS) heuristics, and how to deal with polygonal instead of grid environments. One of the latest results uses Close-Enough TSP as a subroutine to compute near-optimal tours and lower bounds for covering a polygon with a circular tool, without the restriction to a grid environment. We are currently working on an improved Close-Enough TSP-solver based on a custom Branch and Bound algorithm, to expand the applicability of the approach to larger instances. Extensions to TSP with Neighborhoods and routing around obstacles are also planned and partially already under development. Additionally, I am planning to develop an exact Close-Enough TSP with Turn Costs-solver, and use it to also compute bounds for the problem of covering a polygon with a circular tool with turn costs.

Partial Coverage Path Planning

Partial Coverage Path Planning with Turn Costs.

Close-Enough TSP

Close-Enough TSP

References:

Optimizing Problems with Turn Costs

Above, I already mentioned my deep interest in computing coverage tours with turn costs, but I am also interested in turn costs in general. Many problem definitions ignore the dynamics and only consider distance costs. However, in many real-world applications, turn costs are also relevant. Unfortunately, they often significantly increase the complexity of the problem, but at the same time, they also make the problem more interesting and realistic. I intend to explore further problems with turn costs in the future, especially the above-mentioned Close-Enough TSP with Turn Costs.

References:

Multi-Agent and Swarm Problems

Parallelization is not only useful in algorithms, but also in the real world. Systems with multiple agents can often solve problems faster and more efficiently than a single agent. However, this requires coordination between the agents, which is often difficult to achieve. I am planning to extend my work on coverage path planning to multi-agent systems and also to look into Multi-Agent Path Finding (MAPF) in general. The aspects of distributing the load and to coordinate the agents, i.e., preventing collisions, are interesting and challenging.

Multi-Agent Path Planning from toybox implementation.

Multi-Agent Path Planning from toybox implementation.

Steiner Swarm

Using a swarm of simple robots to maintain connectivity.

References:

Other Geometric Optimization Problems

I have also been working on various other problems in computational geometry, such as computing minimal polygons with holes from a given set of points. Computing simple polygons would just be the euclidean Traveling Salesman Problem, but allowing holes can make some subtours legal. This requires specially created cuts that only disallow subtours that are not feasible holes, which of course can depend on the outer boundary. Assembly problems are also interesting and challenging, as the individual parts can have intricate dependencies. With being a co-organizer and technical lead of the CG:SHOP competitions, I am of course also in constant contact with various other problems in computational geometry, even if I am not actively working on them.

I am planning to go deeper into using SAT-solvers for assembly problems. There is already work in progress on k-Handed Assembly, and maximizing the constructable part in Tilt Assembly resp. minimizing the necessary auxiliary parts.

Packing rectangles using LNS

Packing rectangles using population-based LNS.

Computing disassembly with a minimal number of hands.

Computing disassembly with a minimal number of hands.

References:

Methodology for Algorithm Engineering

Algorithm Engineering requires many skills on top of just algorithm design and writing efficient code. While there are cases in which it is sufficient to just do a quick implementation, run a benchmark, and print the results in a table, things quickly get more complicated to a level that can no longer be handled without a proper methodology.

First, the algorithm implementation and the evaluation framework needs to be reusable, so that it can be used by others, for verification but also to build upon it. As soon as the implementation has complex dependencies or is not trivial to use, it is not enough to just share the code, but it needs to be packaged and documented. There are modern tools to help with this, but they require some effort to learn and use. Too often, this leads to the situation that the code is not shared at all, or only in a way that is not usable by others. This is problematic as it limits the scalability of research, if everyone has to reinvent the wheel. We like to share our code as easy to use Python-packages, but as we often use C++ for performance-critical parts, we also have to deal with the problem of sharing C++-code and including complicated dependencies, such as CGAL. This requires a lot of work and understanding of the tools, and unfortunately, there is no textbook I know of that you could just press into the hands of a student to learn it.

Second, evaluations can quickly become very complex, and it is easy to make mistakes. The complexity of the evaluation explodes exponentially with the number of parameters you want to evaluate. It takes experience to design experiments that are not only correct but also efficient and comprehensible. You often need to split your evaluations into multiple parts, which requires a structured workflow and documentation to keep track of everything. Some experiments can take weeks to finish and create tens of gigabytes of data, which needs to be managed and analyzed. As you usually also iterate on your implementation, as you get new ideas or find bugs, you need to make sure that the data remains consistent and comparable, without having to rerun everything. This is a lot of work with many pitfalls, and it is often left to the junior researchers to figure out on their own. This is especially problematic for junior researcher that can not leverage the experience of a senior researcher (with fresh hands-on experience), as it is rarely described in papers.

Other disciplines, such as machine learning, bioinformatics, etc., struggle with similar problems, and I am planning to survey how they deal with it. Their communities are often much larger, and they have more resources to develop tools and methodologies, such as Scientific Python. I also already started to develop tools to help with it, such as slurminade, a decorator-based helper for distributing Python with Slurm, and AlgBench, a framework for managing and analyzing experiments. For helping building Python packages with C++-extensions, I am working on skbuild-conan, which is an extension of scikit-build that allows you to use conan to manage your C++ dependencies. Additionally, I have prepared examples and try to document my workflows of current and future projects, to help others to get started. However, this is a serious amount of work and requires a lot of experience, such that I am planning to reach out to other researchers to work on this together. I spent already a lot of time on this, but I believe it is worth it as it will help to scale research and improve its quality.

References:

Teaching Algorithm Engineering

I served for multiple years as technical lead for the CG:SHOP challenges, which motivates the computational geometry community to tackle difficult optimization problems. Together with my colleague Phillip Keldenich, I developed a new course on Algorithm Engineering, teaching the methodology to solve NP-hard problems and to implement algorithms efficiently. To get students interested, I also offer a beginner-friendly algorithm lab that lets students use a few tools such as MIP-solvers, SAT-solvers, and CP-solvers as a black box to solve NP-hard problems. Originating from the algorithm engineering course, I started writing a (well-received) primer on Google's CP-SAT solver, which is a powerful new tool for solving NP-hard problems. I believe that one needs to understand the tools to use them effectively, and it does in my opinion not yet have the necessary educational material for beginners to understand it. My future roadmap involves creating a tutorial and simple framework for implementing efficient branch and bound algorithms. This will deepen insights into existing implementations and provide a cornerstone for non-classical implementations, not yet supported by existing frameworks (e.g., our work on CE-TSP).

References:

Connecting with other Fields

Many researchers in other fields have to deal with complex optimization problems, but they often do not have the necessary expertise to solve them efficiently, nor do they know that there are significantly better options than some meta-heuristics. I like to connect to different fields and look for problems that can be solved with my expertise. Additionally, I am a curious person and like to learn about what other people a curious about. Examples of fields I have already had contact with:

Computing disassembly with a minimal number of hands.

A schedule for communication windows of a massive satellite swarm to ground stations.

Machine Learning in Algorithm Engineering

The raise of LLMs (Large Language Models) like GPT-3 open exciting new opportunities for algorithm engineering, which I am eager to explore. They do not only show potential in helping to write, document, and debug code but also in tuning code. Further, they may help in analyzing the data of experiments and in detecting anomalies and patterns. For example, you could let an LLM read all the logs of your experiments and return suspicious logs that could be an undetected bug and should be investigated. While you should not rely on an LLM for that and definitely need to implement safety-measures yourself, it could help you find anomalies earlier. I have also been surprised by tools like Copilot, being able to help with writing MIP-models (though, it is also dangerous due to the ability to do nearly correct suggestions, with difficult to spot errors).

Of course there are also the obvious applications of using Machine Learning in the optimization itself, e.g., as a cost-function in an A* search, or for the algorithm selection problem. We have successfully use Deep Reinforcement Learning for the Gathering problem, beating our classical algorithms that were complete overhelmed by the complexity of the problem. However, the success stories of Machine Learning in optimization are still rare, and I am not sure that this will change soon. The classical algorithms already kind of learn automatically (e.g., CDCL), without the need for neural networks. I am still open to explore possibilities, though I believe that they will rather in parameter tuning and algorithm selection, than in the optimization itself. We also successfully used techniques from machine learning to select a subset of diverse instance from a huge set for the CG:SHOP competitions, but these were rather simple techniques such as k-means clustering.

References:

Teaching

Phillip Keldenich and I offer the new course algorithm engineering, which teaches you how to implement algorithms efficiently (lots of CPU and memory architecture) and to understand and use techniques for solving NP-hard optimization problems (MIP, CP, SAT, Heuristics). The course is aimed for master students and was first taught during summer term in 2022.

I assisted lectures in mathematical optimization, algorithm engineering, and approximation algorithms. Additionally, I supervised multiple software development labs, projects, and theses for students.

Achievements and Awards

Curriculum Vitae

Publications

Sándor P Fekete, Dominik Krupke, Michael Perk, Christian Rieck, Christian Scheffer
A Closer Cut: Computing Near-Optimal Lawn Mowing Tours
2023, 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 1--14

Judith Bernett, Dominik Krupke, Sepideh Sadegh, Jan Baumbach, Sándor P. Fekete, Tim Kacprowski, Markus List, David B. Blumenthal
Robust disease module mining via enumeration of diverse prize-collecting Steiner trees [URL] [DOI]
2022, Bioinformatics, Volume: , pp.

Kevin Buchin, Alexander Hill, Sándor Fekete, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, Martijn Struijs
Minimum Scan Cover and Variants: Theory and Experiments
2022, ACM Journal of Experimental Algorithmics, Volume: 27, pp. 1--28

Sándor P Fekete, Phillip Keldenich, Dominik Krupke, Joseph SB Mitchell
Computing coordinated motion plans for robot swarms: The cg: shop challenge 2021
2022, ACM Journal of Experimental Algorithmics (JEA), Volume: 27, pp. 1--12

Erik D Demaine, Sándor P Fekete, Phillip Keldenich, Dominik Krupke, Joseph SB Mitchell
Area-optimal simple polygonalizations: The CG challenge 2019
2022, Journal of Experimental Algorithmics (JEA), Volume: 27, pp. 1--12

Sándor P. Fekete, Linda Kleist, Dominik Krupke
Minimum Scan Cover with Angular Transition Costs [URL] [DOI]
2021, SIAM J. Discret. Math., Volume: 35, pp. 1337--1355

Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, Martijn Struijs
Minimum Scan Cover and Variants - Theory and Experiments [URL] [DOI]
2021, 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France, Volume: 190, pp. 4:1--4:16

Mohamed Ben Larbi, Kattia Pozo, Tom Haylok, Mirue Choi, Benjamin Grzesik, Andreas Haas, Dominik Krupke, Harald Konstanski, Volker Schaus, Sándor Fekete, Christian Schurig, Enrico Stoll
Towards the Automated Operations of Large Distributed Satellite Systems. Part 1: Review and Paradigm Shifts [DOI]
2020, Advances in Space Research, Volume: 67, pp.

Mohamed Ben Larbi, Kattia Pozo, Mirue Choi, Tom Haylok, Benjamin Grzesik, Andreas Haas, Dominik Krupke, Harald Konstanski, Volker Schaus, Sándor Fekete, Christian Schurig, Enrico Stoll
Towards the Automated Operations of Large Distributed Satellite Systems. Part 2: Classifications and Tools [DOI]
2020, Advances in Space Research, Volume: 67, pp.

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt
Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces [URL] [DOI]
2020, Algorithmica, Volume: 82, pp. 165--187

Sándor P. Fekete, Linda Kleist, Dominik Krupke
Minimum Scan Cover with Angular Transition Costs [URL] [DOI]
2020, 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, Volume: 164, pp. 43:1--43:18

Aaron T. Becker, Sándor P. Fekete, Li Huang, Phillip Keldenich, Linda Kleist, Dominik Krupke, Christian Rieck, Arne Schmidt
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces [URL] [DOI]
2020, 2020 IEEE International Conference on Robotics and Automation, ICRA 2020, Paris, France, May 31 - August 31, 2020, pp. 2508--2514

Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips
Probing a Set of Trajectories to Maximize Captured Information [URL] [DOI]
2020, 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy, Volume: 160, pp. 5:1--5:14

Volker Schaus, Dominik Krupke, Mohamed Ben Larbi, Andreas Haas, Benjamin Grzesik, Jonas Radtke, Sándor Fekete, Enrico Stoll
Automated Constellation Management With Self-Regulating Data-Economic Actors
2019, 70th International Astronautical Congress (IAC)

Sándor P. Fekete, Dominik Krupke
Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost [URL] [DOI]
2019, Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, pp. 186--198

Dominik Krupke, Volker Schaus, Andreas Haas, Michael Perk, Jonas Dippel, Benjamin Grzesik, Mohamed Khalil Ben Larbi, Enrico Stoll, Tom Haylock, Harald Konstanski, Kattia Flores Pozo, Mirue Choi, Christian Schurig, Sándor P. Fekete
Automated Data Retrieval from Large-Scale Distributed Satellite Systems [URL] [DOI]
2019, 15th IEEE International Conference on Automation Science and Engineering, CASE 2019, Vancouver, BC, Canada, August 22-26, 2019, pp. 1789--1795

Sándor P. Fekete, Dominik Krupke
Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation [URL] [DOI]
2019, Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings, Volume: 11485, pp. 224--236

An Nguyen, Dominik Krupke, Mary Burbage, Shriya Bhatnagar, Sándor P. Fekete, Aaron T. Becker
Using a UAV for Destructive Surveys of Mosquito Population [URL] [DOI]
2018, 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pp. 7812--7819

Phillip Keldenich, Sheryl Manzoor, Li Huang, Dominik Krupke, Arne Schmidt, Sándor P. Fekete, Aaron T. Becker
On Designing 2D Discrete Workspaces to Sort or Classify Polynminoes [URL] [DOI]
2018, 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018, pp. 1--9

Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel
Computing nonsimple polygons of minimum perimeter [URL] [DOI]
2017, J. Comput. Geom., Volume: 8, pp. 340--365

Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, An Nguyen
Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution) [URL] [DOI]
2017, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, Volume: 77, pp. 62:1--62:5

Arun Mahadev, Dominik Krupke, Sándor P. Fekete, Aaron T. Becker
Mapping and coverage with a particle swarm controlled by uniform inputs [URL] [DOI]
2017, 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017, pp. 1097--1104

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt
Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces [URL] [DOI]
2017, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, Volume: 92, pp. 11:1--11:13

Dominik Krupke
Algorithmic methods for complex dynamic sweeping problems [URL]
2016, Master Thesis

Arun V. Mahadev, Dominik Krupke, Jan-Marc Reinhardt, Sándor P. Fekete, Aaron T. Becker
Collecting a swarm in a grid environment using shared, global inputs [URL] [DOI]
2016, IEEE International Conference on Automation Science and Engineering, CASE 2016, Fort Worth, TX, USA, August 21-25, 2016, pp. 1231--1236

Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel
Computing Nonsimple Polygons of Minimum Perimeter [URL] [DOI]
2016, Experimental Algorithms - 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings, Volume: 9685, pp. 134--149

Dominik Krupke, Maximilian Ernestus, Michael Hemmer, Sándor P. Fekete
Distributed cohesive control for robot swarms: Maintaining good connectivity in the presence of exterior forces [URL] [DOI]
2015, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015, pp. 413--420

Dominik Krupke, Michael Hemmer, James McLurkin, Yu Zhou, Sándor P. Fekete
A parallel distributed strategy for arraying a scattered robot swarm [URL] [DOI]
2015, 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015, pp. 2795--2802

Maximilian Ernestus, Dominik Krupke
Distributed, scalable algorithmic methods for swarms with multiple leader robots [URL]
2014, Bachelor Thesis

Björn Bankowski, Thiemo Clausen, Dirk Ehmen, Maximilian Ernestus, Henning Hasemann, Tobias Jura, Alexander Kröller, Dominik Krupke, Marco Nikander
Panic Room: Experiencing Overload and Having Fun in the Process [URL] [DOI]
2014, Distributed, Ambient, and Pervasive Interactions - Second International Conference, DAPI 2014, Held as Part of HCI Interational 2014, Heraklion, Crete, Greece, June 22-27, 2014. Proceedings, Volume: 8530, pp. 241--252