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 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem 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. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 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 - 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 - Sagnol, Guillaume A1 - Schwartz, Stephan T1 - An Extended Network Interdiction Problem for Optimal Toll Control 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. T3 - ZIB-Report - 15-32 KW - network interdiction Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55405 SN - 1438-0064 ER - 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 - 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 - 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 - 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 - CHAP A1 - Borndörfer, Ralf A1 - Casel, Katrin A1 - Issac, Davis A1 - Niklanovits, Aikaterini A1 - Schwartz, Stephan A1 - Zeif, Ziena T1 - Connected k-partition of k-connected graphs and c-claw-free graphs T2 - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 N2 - A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c −1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w_1, ..., w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T_1, ..., T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least w_i/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least w_i/3 and at most max({r, 3})w_i, where r ≥1 is the ratio between the largest and smallest value in w_1, ..., w_k. In particular for the balanced version, i.e. w_1 = w_2 = ... = w_k, this gives a partition with 1/3 w_i ≤ w(T_i) ≤ 3w_i. Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-147200 VL - 207 SP - 27:1 EP - 27:14 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik 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 - CHAP A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints T2 - Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7–10, 2022 N2 - Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts. Y1 - 2022 U6 - https://doi.org/10.48786/inoc.2022.12 SP - 63 EP - 68 ER - TY - GEN A1 - Schwartz, Stephan T1 - An Overview of Graph Covering and Partitioning 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, our review extends to the corresponding partioning problems. T3 - ZIB-Report - 20-24 KW - Graph Covering KW - Graph Partitioning Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79431 SN - 1438-0064 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 - 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 - 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 - JOUR A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Vertex Covering with Capacitated Trees JF - Networks N2 - The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph’svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature Y1 - 2023 U6 - https://doi.org/10.1002/net.22130 VL - 81 IS - 2 SP - 253 EP - 277 ER -