An official website of the United States government
Abstract Line coverage is the task of servicing a given set of one‐dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of therequired graph, that is, the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3 s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs on the UNC Charlotte campus road network.
more »
« less
A New Derivative‐Free Linear Approximation for Solving the Network Water Flow Problem With Convergence Guarantees
Abstract Addressing challenges in urban water infrastructure systems, including aging infrastructure, supply uncertainty, extreme events, and security threats, depends highly on water distribution networks modeling emphasizing the importance of realistic assumptions, modeling complexities, and scalable solutions. In this study, we propose a derivative‐free, linear approximation for solving the network water flow problem. The proposed approach takes advantage of the special form of the nonlinear head loss equations, and, after the transformation of variables and constraints, the water flow problem reduces to a linear optimization problem that can be efficiently solved by modern linear solvers. Ultimately, the proposed approach amounts to solving a series of linear optimization problems. We demonstrate the proposed approach through several case studies and show that the approach can model arbitrary network topologies and various types of valves and pumps, thus providing modeling flexibility. Under mild conditions, we show that the proposed linear approximation converges. We provide sensitivity analysis and discuss in detail the current limitations of our approach and suggest solutions to overcome these. All the codes, tested networks, and results are freely available on Github for research reproducibility.
more »
« less
- PAR ID:
- 10455518
- Publisher / Repository:
- DOI PREFIX: 10.1029
- Date Published:
- Journal Name:
- Water Resources Research
- Volume:
- 56
- Issue:
- 3
- ISSN:
- 0043-1397
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)The multicommodity flow problem is a classic problem in network flow and combinatorial optimization, with applications in transportation, communication, logistics, and supply chain management, etc. Existing algorithms often focus on low-accuracy approximate solutions, while high-accuracy algorithms typically rely on general linear program solvers. In this paper, we present efficient high-accuracy algorithms for a broad family of multicommodity flow problems on undirected graphs, demonstrating improved running times compared to general linear program solvers. Our main result shows that we can solve the 𝓁_{q, p}-norm multicommodity flow problem to a (1 + ε) approximation in time O_{q, p}(m^{1+o(1)} k² log(1/ε)), where k is the number of commodities, and O_{q, p}(⋅) hides constants depending only on q or p. As q and p approach to 1 and ∞ respectively, 𝓁_{q, p}-norm flow tends to maximum concurrent flow. We introduce the first iterative refinement framework for 𝓁_{q, p}-norm minimization problems, which reduces the problem to solving a series of decomposable residual problems. In the case of k-commodity flow, each residual problem can be decomposed into k single commodity convex flow problems, each of which can be solved in almost-linear time. As many classical variants of multicommodity flows were shown to be complete for linear programs in the high-accuracy regime [Ding-Kyng-Zhang, ICALP'22], our result provides new directions for studying more efficient high-accuracy multicommodity flow algorithms.more » « less
-
Abstract We introduce the concept of decision‐focused surrogate modeling for solving computationally challenging nonlinear optimization problems in real‐time settings. The proposed data‐driven framework seeks to learn a simpler, for example, convex, surrogate optimization model that is trained to minimize thedecision prediction error, which is defined as the difference between the optimal solutions of the original and the surrogate optimization models. The learning problem, formulated as a bilevel program, can be viewed as a data‐driven inverse optimization problem to which we apply a decomposition‐based solution algorithm from previous work. We validate our framework through numerical experiments involving the optimization of common nonlinear chemical processes such as chemical reactors, heat exchanger networks, and material blending systems. We also present a detailed comparison of decision‐focused surrogate modeling with standard data‐driven surrogate modeling methods and demonstrate that our approach is significantly more data‐efficient while producing simple surrogate models with high decision prediction accuracy.more » « less
-
Water Distribution Networks are a particularly critical infrastructure for the high energy costs and frequent failures. Variable Speed Pumps have been introduced to improve the regulation of water pumps, a key for the overall infrastructure performance. This paper addresses the problem of analyzing the effect of the VSPs regulation on the pressure distribution of a WDN, which is highly correlated to leakages and energy costs. Due to the fact that water network behavior can only be simulated, we formulate the problem as a black box feasibility determination, which we solve with a novel stochastic partitioning algorithm, the Feasibility Set Approximation Probabilistic Branch and Bound, that extends the algorithm previously proposed by two of the authors. We use, as black box, EPANet, a widely adopted hydraulic simulator. The preliminary results, over theoretical functions as well as a water distribution network benchmark case, show the viability and advantages of the proposed approach.more » « less
-
Future wireless networks need to support the increasing demands for high data rates and improved coverage. One promising solution is sectorization, where an infrastructure node (e.g., a base station) is equipped with multiple sectors employing directional communication. Although the concept of sectorization is not new, it is critical to fully understand the potential of sectorized networks, such as the rate gain achieved when multiple sectors can be simultaneously activated. In this paper, we focus on sectorized wireless networks, where sectorized infrastructure nodes with beam-steering capabilities form a multi-hop mesh network for data forwarding and routing. We present a sectorized node model and characterize the capacity region of these sectorized networks. We define the flow extension ratio and the corresponding sectorization gain, which quantitatively measure the performance gain introduced by node sectorization as a function of the network flow. Our objective is to find the optimal sectorization of each node that achieves the maximum flow extension ratio, and thus the sectorization gain. Towards this goal, we formulate the corresponding optimization problem and develop an efficient distributed algorithm that obtains the node sectorization under a given network flow with an approximation ratio of 2/3. Through extensive simulations, we evaluate the sectorization gain and the performance of the proposed algorithm in various network scenarios with varying network flows. The simulation results show that the approximate sectorization gain increases sublinearly as a function of the number of sectors per node.more » « less
