TY - GEN A1 - Borndörfer, Ralf A1 - Elijazyfer, Ziena A1 - Schwartz, Stephan T1 - Approximating Balanced Graph Partitions N2 - 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. T3 - ZIB-Report - 19-25 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73675 SN - 1438-0064 ER - TY - THES A1 - Elijazyfer, Ziena T1 - Längenbeschränkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung Y1 - 2018 ER - TY - THES A1 - Schreck, Vanessa T1 - Algorithmic Analysis of the Graph Segmentation Problem Y1 - 2018 ER - TY - JOUR A1 - Schwartz, Stephan T1 - An overview of graph covering and partitioning JF - Discrete Mathematics N2 - 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. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1016/j.disc.2022.112884 VL - 345 IS - 8 ER - TY - GEN A1 - Schwartz, Stephan A1 - Balestrieri, Leonardo A1 - Borndörfer, Ralf T1 - On Finding Subpaths With High Demand N2 - 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. T3 - ZIB-Report - 18-27 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69280 SN - 1438-0064 ER - TY - CHAP A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Balestrieri, Leonardo T1 - On Finding Subpaths With High Demand T2 - Operations Research Proceedings 2017 N2 - 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. Y1 - 2018 SP - 355 EP - 360 PB - Springer International Publishing ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Bartz, Gerald T1 - The Graph Segmentation Problem T2 - INOC 2017 – 8th International Network Optimization Conference N2 - 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. Y1 - 2018 VL - 64 SP - 35 EP - 44 ER - TY - JOUR A1 - Grimm, Boris A1 - Hoogervorst, Rowan A1 - Borndörfer, Ralf T1 - A Comparison of Two Models for Rolling Stock Scheduling JF - Transportation Science N2 - 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. Y1 - 2025 U6 - https://doi.org/10.1287/trsc.2024.0505 VL - 59 IS - 5 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints T3 - ZIB-Report - 21-34 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84427 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Finding Minimum Balanced Separators - an Exact Approach T2 - Operations Research Proceedings 2021 N2 - 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. T3 - ZIB-Report - 21-25 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83138 SN - 1438-0064 SP - 154 EP - 159 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Vertex Covering with Capacitated Trees N2 - 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. T3 - ZIB-Report - 21-14 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82616 SN - 1438-0064 ER - TY - CHAP A1 - Sagnol, Guillaume T1 - Network-related problems in optimal experimental design and second order cone programming T2 - Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications N2 - 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. Y1 - 2012 U6 - https://doi.org/10.2478/v10127-012-0016-x VL - 51 SP - 161 EP - 171 ER - TY - THES A1 - Schwartz, Stephan T1 - Bilevel Programming to Optimize the Use of Traffic Control Gantries for Toll Enforcement Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54180 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks N2 - 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. T3 - ZIB-Report - 14-07 KW - Game Theory KW - Stackelberg Equilibrium KW - Security Games KW - Mixed Integer Programming KW - Price of Anarchy Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-47139 SN - 1438-0064 ER - TY - CHAP A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies T2 - Operations Research Proceedings 2016 N2 - 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. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_30 SP - 217 EP - 223 ER - TY - GEN A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies N2 - 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. T3 - ZIB-Report - 16-65 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61123 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Network-related problems in Optimal Experimental Design and Second Order Cone Programming N2 - 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. T3 - ZIB-Report - 11-52 KW - Optimal Experimental Design KW - Second Order Cone Programming KW - Network measurements Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14942 SN - 1438-0064 VL - 51 IS - 51 SP - 161 EP - 171 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach N2 - 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. T3 - ZIB-Report - 12-47 KW - Stackelberg Equilibrium KW - Game Theory KW - Mixed Integer Programming Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17401 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways N2 - 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. T3 - ZIB-Report - 11-42 KW - Toll Enforcement KW - Vehicle Routing Problem KW - Duty Roster Planning KW - Integer Programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14299 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - The Price of Spite in Spot-checking games N2 - 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. T3 - ZIB-Report - 14-38 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52775 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schwartz, Stephan T1 - An Extended Network Interdiction Problem for Optimal Toll Control T2 - INOC 2015 – 7th International Network Optimization Conference N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1016/j.endm.2016.03.040 VL - 52 SP - 301 EP - 308 ER -