Many combinatorial optimization problems can be solved efficiently on specially structured graphs by using algorithms based on decompositions of these graphs. Some decomposition approaches (e.g. branchwidth) can be generalized to hypergraphs, matroids, and symmetric submodular functions. We want to transfer these results to problems arising in rolling stock rostering where additional side constraints have to be taken into account.
