@misc{BorndoerferElijazyferSchwartz2019, author = {Bornd{\"o}rfer, Ralf and Elijazyfer, Ziena and Schwartz, Stephan}, title = {Approximating Balanced Graph Partitions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73675}, year = {2019}, abstract = {We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a \$\Delta\$-approximation where \$\Delta\$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.}, language = {en} } @misc{Elijazyfer2018, type = {Master Thesis}, author = {Elijazyfer, Ziena}, title = {L{\"a}ngenbeschr{\"a}nkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung}, year = {2018}, language = {de} } @misc{Schreck2018, type = {Master Thesis}, author = {Schreck, Vanessa}, title = {Algorithmic Analysis of the Graph Segmentation Problem}, year = {2018}, language = {en} } @article{Schwartz2022, author = {Schwartz, Stephan}, title = {An overview of graph covering and partitioning}, volume = {345}, journal = {Discrete Mathematics}, number = {8}, doi = {https://doi.org/10.1016/j.disc.2022.112884}, year = {2022}, abstract = {While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.}, language = {en} } @misc{SchwartzBalestrieriBorndoerfer2018, author = {Schwartz, Stephan and Balestrieri, Leonardo and Bornd{\"o}rfer, Ralf}, title = {On Finding Subpaths With High Demand}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69280}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{SchwartzBorndoerferBalestrieri2018, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Balestrieri, Leonardo}, title = {On Finding Subpaths With High Demand}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, pages = {355 -- 360}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @inproceedings{BorndoerferSchwartzBartz2018, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Bartz, Gerald}, title = {The Graph Segmentation Problem}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, pages = {35 -- 44}, year = {2018}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @article{GrimmHoogervorstBorndoerfer2025, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Two Models for Rolling Stock Scheduling}, volume = {59}, journal = {Transportation Science}, number = {5}, arxiv = {http://arxiv.org/abs/2312.09697}, doi = {10.1287/trsc.2024.0505}, year = {2025}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.}, language = {en} } @misc{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84427}, year = {2021}, language = {en} } @inproceedings{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Finding Minimum Balanced Separators - an Exact Approach}, booktitle = {Operations Research Proceedings 2021}, issn = {1438-0064}, doi = {https://doi.org/10.1007/978-3-031-08623-6_24}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83138}, pages = {154 -- 159}, year = {2021}, abstract = {Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.}, language = {en} } @misc{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82616}, year = {2021}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.}, language = {en} } @inproceedings{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in optimal experimental design and second order cone programming}, volume = {51}, booktitle = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, doi = {10.2478/v10127-012-0016-x}, pages = {161 -- 171}, year = {2012}, abstract = {In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results.}, language = {en} } @misc{Schwartz2013, type = {Master Thesis}, author = {Schwartz, Stephan}, title = {Bilevel Programming to Optimize the Use of Traffic Control Gantries for Toll Enforcement}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54180}, year = {2013}, language = {en} } @misc{BorndoerferBuwayaSagnoletal.2014, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks}, issn = {1438-0064}, doi = {10.1002/net.21596}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-47139}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{SchwartzSchlechteSwarat2017, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_30}, pages = {217 -- 223}, year = {2017}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{SchwartzSchlechteSwarat2016, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61123}, year = {2016}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @misc{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in Optimal Experimental Design and Second Order Cone Programming}, volume = {51}, number = {51}, issn = {1438-0064}, doi = {10.2478/v10127-012-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14942}, pages = {161 -- 171}, year = {2012}, abstract = {In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results.}, language = {en} } @misc{BorndoerferBuwayaSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, issn = {1438-0064}, doi = {/10.1016/j.endm.2013.05.100}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17401}, year = {2012}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} } @misc{BorndoerferSagnolSwarat2011, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_51}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14299}, number = {11-42}, year = {2011}, abstract = {This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.}, language = {en} } @misc{SagnolBorndoerferSchlechteetal.2014, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {The Price of Spite in Spot-checking games}, issn = {1438-0064}, doi = {10.1007/978-3-662-44803-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52775}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{BorndoerferSagnolSchwartz2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, volume = {52}, booktitle = {INOC 2015 - 7th International Network Optimization Conference}, doi = {10.1016/j.endm.2016.03.040}, pages = {301 -- 308}, year = {2016}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} }