A core problem with NP hard optimization problems is that the size of the problem will inevitably kill you performancewise at some point. Modern integer programming solvers can get you a long way but often there will be a relatively sharp line separating problems which the solver eats for breakfast and problems which have become to big. If the problem you are trying to solve exposes enough useful struture, a way to reduce the size is via decomposition, i.e., cutting the problem into smaller problems which can later be joined together in an optimal way. My PhD thesis “Decomposition of Integer Programs with Matchability Structure” focuses on problems where a part of the overall problem consists of a bipartite matching. Bipartite matchings are graph problems where you have two groups of entities and you want to join them up into pairs with one entity of each group. Bipartite matchings are a very well understood class of problems and they tend to appear in many situations – think assigning drivers to trucks, classes to classrooms, delivery boys to routes, etcetera.
In the thesis I explain how such structures can be exploited to formulate a Benders' decomposition where the matching problem can be solved separately from the rest of the problem without sacrificing optimality. This decomposition has multiple nice properties, due to the bipartite matching being a very well behaved problem class. From there I can show how the technique can be extended to cases where the subproblem is not a perfect bipartite matching but a hypergraph matching. This opens up a lot more porblems to the generic Benders' decomposition proposed. In the thesis I illustrate the techniques using the high school timetabling problem, but everything described is more generic and could apply to other similarly structured problems as well.
Another topic explored are problems which are decomposed using Dantzig-Wolfe decomposition where the subproblems are similar but not identical. In these cases the similarity of the subproblems can be used to aggregate them together in order to avoid unnecessary symmetry. Here a bipartite matching problem is used to make sure the solutions found can be matched to the original subproblems.
When should I read the thesis?
- You are a huge fan of integer programming and graph theory and love reading theorems combining those.
- Benders' or Dantzig-Wolfe decompositions are you best friends and you want to learn about a problem class where they can be applied more or less generically.
- The combinatorial problem you are currently struggling with consists of a part where two groups of things shall be pairwise matched together and you want to know if there is a more way to solve it.
Header photo by Death to the Stock Photo
comments powered by Disqus