An official website of the United States government
Spatial optimization is an integral part of GIS and spatial analysis. It involves making various decisions in space, ranging from the location of public facilities to vehicle routing and political districting. While useful, such problems (especially large problem instances) are often difficult to solve using general mathematical programming (due to their generality). Traditionally, an alternative solution method is Lagrangian relaxation, which, if well-designed, can be fast and optimal. One has to derive the Lagrangian dual problem and its (sub)gradients, and move towards the optimal solution via a search process such as gradient descent. Despite its merits, Lagrangian relaxation as a solution algorithm requires one to derive the (sub)gradients manually, which is error-prone and makes the solution algorithm difficult to develop and highly dependent on the model at hand. This paper aims to ease the development of Lagrangian relaxation algorithms for GIS practitioners by employing the automatic (sub)gradient (autograd) computation capabilities originally developed in modern Deep Learning. Using the classic p-median problem as an example, we demonstrate how Lagrangian relaxation can be developed with paper and pencil, and how the (sub)gradient computation derivation can be automated using autograd. As such, the human expert only needs to implement the Lagrangian problem in a scientific computing language (such as Python), and the system can find the (sub)gradients of this code, even if it contains complex loops and conditional statements. We verify that the autograd version of the algorithm is equivalent to the original version with manually derived gradients. By automating the (sub)gradient computation, we significantly lower the cost of developing a Lagrangian algorithm for the p-median. And such automation can be applied to numerous other optimization problems.
more »
« less
A Decomposition and Coordination Approach for Large Sub-hourly Unit Commitment
Sub-hourly Unit Commitment (UC) problems have been suggested as a way to improve power system efficiency. Such problems, however, are much more difficult than hourly UC problems. This is not just because of the increased number of period to consider, but also because of much reduced unit ramping capabilities leading to more complicated convex hulls. As a result, state-of-the-art and practice methods such as branch-and-cut suffer from poor performance. In this paper, our recent Surrogate Absolute-Value Lagrangian Relaxation (SAVLR) method, which overcame major difficulties of standard Lagrangian Relaxation, is enhanced by synergistically incorporating the concept of Ordinal Optimization (OO). By using OO, solving subproblems becomes much faster. Testing of Midcontinent ISO (MISO)’s problem with 15 minutes as the time interval over 36 hours involving about 1,100 units and 15000 virtuals demonstrates that the new method obtains near-optimal solutions efficiently and significantly outperforms branch-and-cut.
more »
« less
- Award ID(s):
- 1810108
- PAR ID:
- 10257311
- Date Published:
- Journal Name:
- IEEE Power and Energy Society 2020 General Meeting
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This article focuses on a recently developed formulation based on the noncommutative branch‐cut cosmology, the Wheeler‐DeWitt (WdW) equation, the Hořava–Lifshitz quantum gravity, chaotic and the coupling of the corresponding Lagrangian approach with the inflaton scalar field. Assuming a mini‐superspace of variables obeying the noncommutative Poisson algebra, we examine the impact of the inflaton scalar field on the evolutionary dynamics of the branch‐cut Universe scale factor, characterized by the dimensionless helix‐like function . This scale factor characterizes a Riemannian foliated spacetime that topologically overcomes the primordial singularities. We take the Hořava–Lifshitz action modeled by branch‐cut quantum gravity as our starting point, which depends on the scalar curvature of the branched Universe and its derivatives and which preserves the diffeomorphism property of General Relativity, maintaining compatibility with the Arnowitt–Deser–Misner formalism. We then investigate the sensitivity of the scale factor of the branch‐cut Universe's dynamics.more » « less
-
A significant amount of research has been performed on network accessibility evaluation, but studies on incorporating accessibility maximization into network design problems have been relatively scarce. This study aimed to bridge the gap by proposing an integer programming model that explicitly maximizes the number of accessible opportunities within a given travel time budget. We adopted the Lagrangian relaxation method for decomposing the main problem into three subproblems that can be solved more efficiently using dynamic programming. The proposed method was applied to several case studies, which identified critical links for maximizing network accessibility with limited construction budget, and also illustrated the accuracy and efficiency of the algorithm. This method is promisingly scalable as a solution algorithm for large-scale accessibility-oriented network design problems.more » « less
-
Advancing Column Generation by a Novel Variable Fixing Method In the paper titled “DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods,” Dr. Yu Yang introduces DeLuxing—an innovative variable-fixing technique that significantly advances column-generation-based exact methods for solving large-scale optimization problems, particularly vehicle routing problems (VRPs). DeLuxing leverages a novel linear programming formulation with a small subset of the enumerated variables, which is theoretically guaranteed to yield qualified dual solutions for computing Lagrangian underestimates. By eliminating over 75% of the unnecessary variables, DeLuxing drastically boosts computational efficiency, doubling the size of CMTVRPTW (capacitated multitrip vehicle routing problem with time windows) instances that can be solved optimally. Additionally, this breakthrough accelerates top VRP solvers like RouteOpt by up to 71%. The core concept underpinning DeLuxing extends to broader contexts such as variable type relaxation and cutting plane addition, achieving an additional 25% speedup for difficult instances.more » « less
-
The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form $$\beta \sqrt n$$ for the minimum length of a Traveling Salesperson Tour throuh $$n$$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such \emph{Euclidean functionals} on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through $$n$$ random points in $[0,1]^2$ was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential ($$e^{\tilde \Omega(n)}$$) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms (a lower bound as strong as $$e^{\tilde \Omega (n)}$$ was not even been known in worst-case analysis).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
