Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 397 records · Page 22

Properly Learning Decision Trees in almost Polynomial Time

We give an n O (log log n ) -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over { ± 1} n . Even in the realizable setting, the previous fastest runtime was n O (log n ) , a consequence of a classic algorithm of Ehrenfeucht and Haussler. Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O’Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

Computer Science↗

A Self-Sustained CPS Design for Reliable Wildfire Monitoring

Continuous monitoring of areas nearby the electric grid is critical for preventing and early detection of devastating wildfires. Existing wildfire monitoring systems are intermittent and oblivious to local ambient risk factors, resulting in poor wildfire awareness. Ambient sensor suites deployed near the gridlines can increase the monitoring granularity and detection accuracy. However, these sensors must address two challenging and competing objectives at the same time. First, they must remain powered for years without manual maintenance due to their remote locations. Second, they must provide and transmit reliable information if and when a wildfire starts. The first objective requires aggressive energy savings and ambient energy harvesting, while the second requires continuous operation of a range of sensors. To the best of our knowledge, this paper presents the first self-sustained cyber-physical system that dynamically co-optimizes the wildfire detection accuracy and active time of sensors. The proposed approach employs reinforcement learning to train a policy that controls the sensor operations as a function of the environment (i.e., current sensor readings), harvested energy, and battery level. Here, the proposed cyber-physical system is evaluated extensively using real-life temperature, wind, and solar energy harvesting datasets and an open-source wildfire simulator. In long-term (5 years) evaluations, the proposed framework achieves 89% uptime, which is 46% higher than a carefully tuned heuristic approach. At the same time, it averages a 2-minute initial response time, which is at least 2.5× faster than the same heuristic approach. Furthermore, the policy network consumes 0.6 mJ per day on the TI CC2652R microcontroller using TensorFlow Lite for Micro, which is negligible compared to the daily sensor suite energy consumption.

54 ENVIRONMENTAL SCIENCES↗

Quasi-Optimal Elimination Trees for 2D Grids with Singularities

We construct quasi-optimal elimination trees for 2D finite element meshes with singularities. These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in parallel shared-memory executions. Since the meshes considered are a subspace of all possible mesh partitions, we call these minimizers quasi-optimal. We minimize the cost functionals using dynamic programming. Finding these minimizers is more computationally expensive than solving the original algebraic system. Nevertheless, from the insights provided by the analysis of the dynamic programming minima, we propose a heuristic construction of the elimination trees that has cost O N e log ⁡ N e , where N e is the number of elements in the mesh. We show that this heuristic ordering has similar computational cost to the quasi-optimal elimination trees found with dynamic programming and outperforms state-of-the-art alternatives in our numerical experiments.

Paszyńska, A.↗

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗

Mota Mapper: A Multi-Objective Topology-Aware Mapper Library

Mota is a library that provides several heuristics for mapping tasks to compute ranks (processes) on a networked computer cluster or supercomputer. It was originally designed for task placement of adaptive mesh refinement codes (AMR). It is multi-objective in the sense that it simultaneously balances (potentially multiple types of) computational load on each rank as well as the communication traffic between the boxes. The heuristics used for mapping include algorithms such as greedy list assignment and space-filling curves, as well as algorithms from graph analysis such as adjacency matrix bandwidth reduction, recursive bisection, and greedy graph placement.

Chan, Cy↗

Code for the manuscript "Lagrangian Large Eddy Simulations vis Physics-informed Machine Learning"

We would like to disclose a code based on Python/Pytorch, in which we implement the data-driven physics-informed machine learning of Lagrangian large eddy simulation that is described in the manuscript "Lagrangian Large Eddy Simulations via Physics-Informed Machine Learning ". High-Reynolds number Homogeneous Isotropic Turbulence is fully described within the Navier-Stokes (NS) equations, which are notoriously difficult to solve numerically. Engineers, interested primarily in describing turbulence at a reduced range of resolved scales, have designed heuristics, known as Large Eddy Simulation (LES). LES is described in terms of the temporally evolving Eulerian velocity field defined over a spatial grid with the mean-spacing correspondent to the resolved scale. This classic Eulerian LES depends on assumptions about the effects of sub-grid scales on the resolved scales. Here, we take an alternative approach and design novel LES heuristics stated in terms of Lagrangian particles moving with the flow. Our \emph{Lagrangian LES}, thus L-LES, is described by equations generalizing the weakly compressible Smoothed Particle Hydrodynamics formulation with extended parametric and functional freedom, which is then resolved via Machine Learning training on Lagrangian data from Direct Numerical Simulations of the NS equations. The L-LES model includes physics-informed parameterization and functional form, by combining physics-based parameters and physics-inspired Neural Networks to describe the evolution of turbulence within the resolved range of scales. The sub-grid scale contributions are modeled separately with physical constraints to account for the effects from un-resolved scales. We build the resulting model under the Differentiable Programming framework to facilitate efficient training. We experiment with loss functions of different types, including physics-informed ones accounting for statistics of Lagrangian particles. We show that our Lagrangian LES model is capable of reproducing Eulerian and unique Lagrangian turbulence structures and statistics over a range of turbulent Mach numbers.

Tian, Yifeng↗

A novel physics-based and data-supported microstructure model for part-scale simulation of laser powder bed fusion of Ti-6Al-4V

The elasto-plastic material behavior, material strength and failure modes of metals fabricated by additive manufacturing technologies are significantly determined by the underlying process-specific microstructure evolution. In this work a novel physics-based and data-supported phenomenological microstructure model for Ti-6Al-4V is proposed that is suitable for the part-scale simulation of laser powder bed fusion processes. The model predicts spatially homogenized phase fractions of the most relevant microstructural species, namely the stable β-phase, the stable α s -phase as well as the metastable Martensite α m -phase, in a physically consistent manner. In particular, the modeled microstructure evolution, in form of diffusion-based and non-diffusional transformations, is a pure consequence of energy and mobility competitions among the different species, without the need for heuristic transformation criteria as often applied in existing models. The mathematically consistent formulation of the evolution equations in rate form renders the model suitable for the practically relevant scenario of temperature- or time-dependent diffusion coefficients, arbitrary temperature profiles, and multiple coexisting phases. Due to its physically motivated foundation, the proposed model requires only a minimal number of free parameters, which are determined in an inverse identification process considering a broad experimental data basis in form of time-temperature transformation diagrams. Subsequently, the predictive ability of the model is demonstrated by means of continuous cooling transformation diagrams, showing that experimentally observed characteristics such as critical cooling rates emerge naturally from the proposed microstructure model, instead of being enforced as heuristic transformation criteria. Eventually, the proposed model is exploited to predict the microstructure evolution for a realistic selective laser melting application scenario and for the cooling/quenching process of a Ti-6Al-4V cube of practically relevant size. Numerical results confirm experimental observations that Martensite is the dominating microstructure species in regimes of high cooling rates, e.g., due to highly localized heat sources or in near-surface domains, while a proper manipulation of the temperature field, e.g., by preheating the base-plate in selective laser melting, can suppress the formation of this metastable phase.

Inverse parameter identification↗

Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. Here, we also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size.

97 MATHEMATICS AND COMPUTING↗

Hyporheic hydraulic geometry: Conceptualizing relationships among hyporheic exchange, storage, and water age

Hyporheic exchange is now widely acknowledged as a key driver of ecosystem processes in many streams. Yet stream ecologists have been slow to adopt nuanced hydrologic frameworks developed and applied by engineers and hydrologists to describe the relationship between water storage, water age, and water balance in finite hydrosystems such as hyporheic zones. Here, in the context of hyporheic hydrology, we summarize a well-established mathematical framework useful for describing hyporheic hydrology, while also applying the framework heuristically to visualize the relationships between water age, rates of hyporheic exchange, and water volume within hyporheic zones. Building on this heuristic application, we discuss how improved accuracy in the conceptualization of hyporheic exchange can yield a deeper understanding of the role of the hyporheic zone in stream ecosystems. Although the equations presented here have been well-described for decades, our aim is to make the mathematical basis as accessible as possible and to encourage broader understanding among aquatic ecologists of the implications of tailed age distributions commonly observed in water discharged from and stored within hyporheic zones. Our quantitative description of “hyporheic hydraulic geometry,” associated visualizations, and discussion offer a nuanced and realistic understanding of hyporheic hydrology to aid in considering hyporheic exchange in the context of river and stream ecosystem science and management.

54 ENVIRONMENTAL SCIENCES↗

Minimizing Energy Use of Mixed-Fleet Public Transit for Fixed-Route Service

Affordable public transit services are crucial for communities since they enable residents to access employment, education, and other services. Unfortunately, transit services that provide wide coverage tend to suffer from relatively low utilization, which results in high fuel usage per passenger per mile, leading to high operating costs and environmental impact. Electric vehicles (EVs) can reduce energy costs and environmental impact, but most public transit agencies have to employ them in combination with conventional, internal-combustion engine vehicles due to the high upfront costs of EVs. To make the best use of such a mixed fleet of vehicles, transit agencies need to optimize route assignments and charging schedules, which presents a challenging problem for large transit networks. We introduce a novel problem formulation to minimize fuel and electricity use by assigning vehicles to transit trips and scheduling them for charging, while serving an existing fixed-route transit schedule. We present an integer program for optimal assignment and scheduling, and we propose polynomial-time heuristic and meta-heuristic algorithms for larger networks. We evaluate our algorithms on the public transit service of Chattanooga, TN using operational data collected from transit vehicles. Our results show that the proposed algorithms are scalable and can reduce energy use and, hence, environmental impact and operational costs. For Chattanooga, the proposed algorithms can save $145,635 in energy costs and 576.7 metric tons of CO 2 emission annually.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DeepHyper: A Python Package for Massively Parallel Hyperparameter Optimization in Machine Learning

Machine learning models are increasingly applied across scientific disciplines, yet their effectiveness often hinges on heuristic decisions—such as data transformations, training strategies, and model architectures—that are not learned by the models themselves. Automating the selection of these heuristics and analyzing their sensitivity is crucial for building robust and efficient learning workflows. DeepHyper addresses this challenge by democratizing hyperparameter optimization, providing accessible tools to streamline and enhance machine learning workflows from a laptop to the largest supercomputer in the world. Building on top of hyperparameter optimization, it unlocks new capabilities around ensembles of models for improved accuracy and uncertainty quantification. All of these organized around efficient parallel computing.

ensemble↗

An Analysis of Source Tilting and Sub-cell Opacity Sampling for IMC [Slides]

Implicit Monte Carlo (IMC) is a stochastic method for solving the radiative transfer equations for multiphysics application with the material in local thermodynamic equilibrium. The IMC method employs a fictitious scattering term that is computed from an implicit discretization of the material temperature equation. Unfortunately, the original histogram representation of the temperature and opacity with respect to the spatial domain leads to nonphysically fast propagation of radiation waves through optically thick material. In the past, heuristic source tilting schemes have been used to mitigate the numerical teleportation error of the radiation particles in IMC that cause this overly rapid radiation wave propagation. While improving the material temperature profile throughout the time duration, these tilting schemes alone do not generally alleviate the teleportation error to suitable levels. Another means of potentially reducing teleportation error in IMC is implementing continuous sub-cell opacities based on sub-cell temperature profiles. We present here an analysis of source tilting and continuous sub-cell opacity sampling applied to various discretizations of the temperature equation. Through this analysis, we demonstrate that applying both heuristics does not necessarily yield more accurate results if the discretization of the material equation is inconsistent with the Monte Carlo sub-cell transport.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Efficient Algorithm for Locating and Sizing Series Compensation Devices in Large Transmission Grids: Solutions and Applications (PART II)

In a companion manuscript, we developed a novel optimization method for placement, sizing, and operation of Flexible Alternating Current Transmission System (FACTS) devices to relieve transmission network congestion. Specifically, we addressed FACTS that provide Series Compensation (SC) via modification of line inductance. In this manuscript, this heuristic algorithm and its solutions are explored on a number of test cases: a 30-bus test network and a realistically-sized model of the Polish grid (~2700 nodes and ~3300 lines). The results on the 30-bus network are used to study the general properties of the solutions including non-locality and sparsity. The Polish grid is used as a demonstration of the computational efficiency of the heuristics that leverages sequential linearization of power flow constraints and cutting plane methods that take advantage of the sparse nature of the SC placement solutions. Using these approaches, the algorithm is able to solve an instance of Polish grid in tens of seconds. We explore the utility of the algorithm by analyzing transmission networks congested by (a) uniform load growth, (b) multiple overloaded configurations, and (c) sequential generator retirements

25 ENERGY STORAGE↗

A Generalized Framework for Modeling Next Generation 911 Implementations

This document summarizes the current state of Sandia 911 modeling capabilities and then addresses key aspects of Next Generation 911 (NG911) architectures for expansion of existing models. Analysis of three NG911 implementations was used to inform heuristics ,associated key data requirements, and assumptions needed to capture NG911 architectures in the existing models. Modeling of NG911 necessitates careful consideration of its complexity and the diversity of implementations. Draft heuristics for constructing NG911 models are pres ented based on the analysis along with a summary of current challenges and ways to improve future NG911 modeling efforts. We found that NG911 relies on E nhanced 911 (E911) assets such as 911 selective routers to route calls originating from traditional tel ephony service which are a majority of 911 calls. We also found that the diversity and transitional nature of NG911 implementations necessitates significant and frequent data collection to ensure that adequate model s are available for crisis action support.

97 MATHEMATICS AND COMPUTING↗

Teaching Game Theory to Kids and Limits of Prediction

I have once been asked to read a lecture to a group of 6th graders on Game Theory. After agreeing to it, I realized that explaining the game theory basics to 6th graders my be difficult, given that terms such as Nash equilibrium, minimax, maximin, optimization may not resonate in a 6th grade classroom. Instead I've introduced game theory using the rock-paper-scissors (RPS) game. Turns out kids are excellent gametheoreticians. In RPS, they understood both the benefits of randomizing their own strategy and of predicting their opponent's moves. They offered a number of heuristics both for the prediction and opening move. These heuristics included optimizing against past opponent moves, such as not playing rock if the opponent just played scissors, and playing a specific opening hand, such as "paper". Visualizing the effects of such strategic choices on-the-fly would be interesting and educational. This brief essay attempts demonstrating and visualizing the value of a few different strategic options in RPS. Specifically, we would like to illustrate the following: 1) what is the value of being unpredictable?; and 2) what is the value of being able to predict your opponent? In regard to prediction of human players, the question 2) has been reflected in Jon McLoone's entry in Wolfram Blog from January 20, 2014[1]. McLoone created a predictive algorithm for playing against human opponents, that learns to beat human opponents reliably after approximately 30 - 40 games. I use McLoone's implementation to represent a predictive and random strategies. The rest of this documents 1) investigates performance of this predictive strategy against a random strategy (which is optimal in RPS) and in 2) attempts to turn this predictive power against the predictive strategy by allowing the opponent the full knowledge of the predictor's strategy (but not the choices made using the strategy). This exposes a weakness in predictions made without taking risks into account by illustrating that predictive strategy may make the predictor predictable as well.

97 MATHEMATICS AND COMPUTING↗

Dynamic Multi-Sensor Multi-Mission Optimal Planning Tool

Remote sensing systems have firmly established a role in providing immense value to commercial industry, scientific exploration, and national security. Continued maturation of sensing technology has reduced the cost of deploying highly-capable sensors while at the same time increased reliance on the information these sensors can provide. The demand for time on these sensors is unlikely to diminish. Coordination of next-generation sensor systems, larger constellations of satellites, unmanned aerial vehicles, ground telescopes, etc. is prohibitively complex for existing heuristics-based scheduling techniques. The project was a two-year collaboration spanning multiple Sandia centers and included a partnership with Texas A&M University. We have developed algorithms and software for collection scheduling, remote sensor field-of-view pointing models, and bandwidth-constrained prioritization of sensor data. Our approach followed best practices from the operations research and computational geometry communities. These models provide several advantages over state of the art techniques. In particular, our approach is more flexible compared to heuristics that tightly couple models and solution techniques. First, our mixed-integer linear models afford a rigorous analysis so that sensor planners can quantitatively describe a schedule relative to the best possible. Optimal or near-optimal schedules can be produced with commercial solvers in operational run-times. These models can be modified and extended to incorporate different scheduling and resource constraints and objective function definitions. Further, we have extended these models to proactively schedule sensors under weather and ad hoc collection uncertainty. This approach stands in contrast to existing deterministic schedulers which assume a single future weather or ad hoc collection scenario. The field-of-view pointing algorithm produces a mosaic with the fewest number of images required to fully cover a region of interest. The bandwidth-constrained algorithms find the highest priority information that can be transmitted. All of these are based on mixed-integer linear programs so that, in the future, collection scheduling, field-of-view, and bandwidth prioritization can be combined into a single problem. Experiments conducted using the developed models, commercial solvers, and benchmark datasets have demonstrated that proactively scheduling against uncertainty regularly and significantly outperforms deterministic schedulers.

47 OTHER INSTRUMENTATION↗

Atmospheric River Tracking Method Intercomparison Project (ARTMIP): Report of the Second ARTMIP Workshop

Atmospheric rivers (ARs) have for the last decade been broadly recognized for their global and regional significance in mediating energy and water cycles. As a distinct large-scale circulation feature, ARs can be characterized by long, narrow bands of atmospheric moisture transport from the tropics to higher latitudes. They are both an important source of water supply to coastal regions as well as a hazard because of their predisposition to increase flood risk. However, predicting ARs poses a significant challenge to the scientific community, as they exhibit large variability from subseasonal-to-interannual time scales. On multi-decadal and longer time scales, it is unclear how the frequency and intensity of ARs will change with a warming climate. Hence ARs play a significant role in understanding predictability of water cycle variability and extremes as well as becoming a factor in assessing risks to future infrastructures. There is a large body of literature that has explored ARs from both global and regional perspectives and from timescales spanning hourly to centennial. Despite significant progress in understanding ARs, significant gaps remain, e.g., in characterizing the dynamical and thermodynamical processes associated with ARs, improving predictions of ARs at weather and subseasonal-to-seasonal timescales, and understanding and quantifying the impacts of ARs on the design and management of built infrastructures. Furthermore, the consensus definition of ARs remains essentially qualitative, and investigators have had to rely on heuristic definitions of ARs for quantitative studies. In the First Atmospheric River Tracking Method Intercomparison Project (ARTMIP) workshop held in May 2017, it was recognized that (1) there are many heuristic AR tracking algorithms employed in the literature, (2) our quantitative—and possibly qualitative— understanding of ARs and their impacts may depend on the details of the algorithm used, (3) no data set yet exists to systematically explore the impact of AR tracking algorithm choice on scientific results, and (4) the broader scientific community therefore lacks any formal guidance on the advantages and disadvantages of different AR tracking methods. The First ARTMIP workshop defined and launched a multi-tiered intercomparison experiment designed to fill this community need. The first tier of ARTMIP was aimed at understanding the impact of AR algorithms on quantitative baseline statistics and characteristics of ARs, and the second tier includes sensitivity studies designed around specific science questions, such as reanalysis uncertainty and influences associated with climate change. The Second ARTMIP workshop was convened on April 23-24, 2018, as a two-day event, and following the completion of Tier 1 of the ARTMIP effort: an experiment in which most existing AR tracking algorithms were run on a standardized data set of reanalyzed weather conditions.

54 ENVIRONMENTAL SCIENCES↗

A Scalable Solution Framework for Stochastic Transmission and Generation Planning Problems. Draft

Current commercial software tools for transmission and generation investment planning have limited stochastic modeling capabilities. Because of this limitation, electric power utilities generally rely on scenario planning heuristics to identify potentially robust and cost effective investment plans for a broad range of system, economic, and policy conditions. Several research studies have shown that stochastic models perform significantly better than deterministic or heuristic approaches, in terms of overall costs. However, there is a lack of practical solution approaches to solve such models. In this paper we propose a scalable decomposition algorithm to solve stochastic transmission and generation planning problems, respectively considering discrete and continuous decision variables for transmission and generation investments. Given stochasticity restricted to loads and wind, solar, and hydro power output, we develop a simple scenario reduction framework based on a clustering algorithm, to yield a more tractable model. The resulting stochastic optimization model is decomposed on a scenario basis and solved using a variant of the Progressive Hedging (PH) algorithm. We perform numerical experiments using a 240-bus network representation of the Western Electricity Coordinating Council in the US. Although convergence of PH to an optimal solution is not guaranteed for mixed-integer linear optimization models, we find that it is possible to obtain solutions with acceptable optimality gaps for practical applications. Our numerical simulations are performed both on a commodity workstation and on a high-performance cluster. The results indicate that large-scale problems can be solved to a high degree of accuracy in at most two hours of wall clock time.

24 POWER TRANSMISSION AND DISTRIBUTION↗