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 919 records · Page 51

Fast Active-Set Thresholding Method for Nonnegative Least Squares

Nonnegative Least Squares (NNLS) is a fundamental constrained optimization problem encountered in many applications such as image deblurring, signal processing, nonnegative matrix factorization, magnetic microscopy, and hyperspectral imaging. Active-set based methods are a common class of algorithms for solving NNLS which identify the optimal variable set of the NNLS solution. They do so by iteratively solving a series of unconstrained least squares problems, identifying which variables violate the nonnegativity constraints, and then swapping variables in/out of consideration until the optimal set of variables is found. Several variations improving upon this method exist in the literature. In this work, we propose an active-set swap heuristic which further improves upon existing active-set based methods for NNLS. Our optimizations are based upon adding multiple variables to the passive set within a threshold of the smallest gradient value and removing variables within a similar threshold of the closest boundary constraint. We leverage these optimizations to yield a Fast Active-Set Thresholding NNLS (FAST-NNLS) algorithm which significantly outperforms the existing state-of-the-art NNLS algorithms for a wide range of problems. Rigorous convergence guarantees are proven for the proposed method. We demonstrate the effectiveness of our proposed method on multiple synthetic datasets and two realworld text analysis applications. In doing so, we present the most comprehensive NNLS solver comparison in the literature to date.

Cobb, Benjamin [Georgia Institute of Technology]↗

A Privacy Preserving Model-Free Optimization and Control Framework for Demand Response from Residential Thermal Loads

We consider the problem of optimizing the cost of procuring electricity for a large collection of homes managed by a load serving entity, by pre-cooling or pre-heating the thermal inertial loads in the homes to avoid procuring power during periods of peak electricity pricing. We would like to accomplish this objective in a completely privacy-preserving and model-free manner, that is, without direct access to the state variables (temperatures or power consumption) or the dynamical models (thermal characteristics) of individual homes, while guaranteeing personal comfort constraints of the consumers. We propose a two-stage optimization and control framework to address this problem. In the first stage, we use a long short-term memory (LSTM) network to predict hourly electricity prices, based on historical pricing data and weather forecasts. Given the hourly price forecast and thermal models of the homes, the problem of designing an optimal power consumption trajectory that minimizes the total electricity procurement cost for the collection of thermal loads can be formulated as a large-scale integer program (with millions of variables) due to the on-off cyclical dynamics of such loads. We provide a simple heuristic relaxation to make this large-scale optimization problem model-free and computationally tractable. In the second stage, we translate the results of this optimization problem into distributed open-loop control laws that can be implemented at individual homes without measuring or estimating their state variables, while simultaneously ensuring consumer comfort constraints. We demonstrate the performance of this approach on a large-scale test case comprising of 500 homes in the Houston area and benchmark its performance against a direct model-based optimization and control solution.

Sivaranjani, S.↗

Fast and Accurate Support Vector Machines on Large Scale Systems

Support Vector Machines (SVM) is a supervised Machine Learning and Data Mining (MLDM) algorithm, which has become ubiquitous largely due to its high accuracy and obliviousness to dimensionality. The objective of SVM is to find an optimal boundary --- also known as hyperplane --- which separates the samples (examples in a dataset) of different classes by a maximum margin. Usually, very few samples contribute to the definition of the boundary. However, existing parallel algorithms use the entire dataset for finding the boundary, which is sub-optimal for performance reasons. In this paper, we propose a novel distributed memory algorithm to eliminate the samples which do not contribute to the boundary definition in SVM. We propose several heuristics, which range from early (aggressive) to late (conservative) elimination of the samples, such that the overall time for generating the boundary is reduced considerably. In a few cases, a sample may be eliminated (shrunk) pre-emptively --- potentially resulting in an incorrect boundary. We propose a scalable approach to synchronize the necessary data structures such that the proposed algorithm maintains its accuracy. We consider the necessary trade-offs of single/multiple synchronization using in-depth time-space complexity analysis. We implement the proposed algorithm using MPI and compare it with libsvm--- de facto sequential SVM software --- which we enhance with OpenMP for multi-core/many-core parallelism. Our proposed approach shows excellent efficiency using up to 4096 processes on several large datasets such as UCI HIGGS Boson dataset and Offending URL dataset.

Vishnu, Abhinav↗

A Scalable Distributed Louvain Algorithm for Large-Scale Graph Community Detection

We present a new distributed community detection algorithm for large graphs based on the Louvain method. We exploit a distributed delegate partitioning to ensure the workload and communication balancing among processors. In addition, we design a new heuristic strategy to carefully coordinate the community constitution in a distributed environment, and ensure the convergence of the distributed clustering algorithm. Our intensive experimental study has demonstrated the scalability and the correctness of our algorithm with various large-scale real-world and synthetic graph datasets using up to 32,768 processors.

Computer Science↗

Hierarchical Clock Synchronization in MPI

We present a new distributed community detection algorithm for large graphs based on the Louvain method. We exploit a distributed delegate partitioning to ensure the workload and communication balancing among processors. In addition, we design a new heuristic strategy to carefully coordinate the community constitution in a distributed environment, and ensure the convergence of the distributed clustering algorithm. Our intensive experimental study has demonstrated the scalability and the correctness of our algorithm with various large-scale real-world and synthetic graph datasets using up to 32,768 processors

Computer Science↗

An architecture for real time data acquisition and online signal processing for high throughput tandem mass spectrometry

Independent, greedy collection of data events using simple heuristics results in massive over-sampling of the prominent data features in large-scale studies over what should be achievable through “intelligent,” online acquisition of such data. As a result, data generated are more aptly described as a collection of a large number of small experiments rather than a true large-scale experiment. Nevertheless, achieving “intelligent,” online control requires tight interplay between state-of-the-art, data-intensive computing infrastructure developments and analytical algorithms. In this paper, we propose a Software Architecture for Mass spectrometry-based Proteomics coupled with Liquid chromatography Experiments (SAMPLE) to develop an “intelligent” online control and analysis system to significantly enhance the information content from each sensor (in this case, a mass spectrometer). Using online analysis of data events as they are collected and decision theory to optimize the collection of events during an experiment, we aim to maximize the information content generated during an experiment by the use of pre-existing knowledge to optimize the dynamic collection of events.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Data-Driven Voltage Regulation of Distribution Grid Using Nonlinear Autoregressive Model with Exogenous Inputs (NARX)

This article proposes data-driven control via a nonlinear autoregressive model with exogenous inputs (NARX) for real-time voltage regulation of a modified feeder using reactive power sources. Traditional voltage control strategies rely on rule-based heuristics or optimization techniques, which often require detailed system models and extensive computational resources. The NARX-based controller learns system dynamics from historical data and predicts optimal reactive power dispatch in real-time for voltage correction. The proposed approach is evaluated on a power system feeder model under varying load and network conditions. Simulation results demonstrate that the NARX-based controller achieves improved voltage regulation, offering higher adaptability to system fluctuations. This study highlights the potential of data-driven control for enhancing the reliability of power distribution networks.

Donge, Vrushabh [ORNL] (ORCID:0000000306062803)↗

Extracting Operating Modes from Building Electrical Load Data: Preprint

Empirical techniques for characterizing electrical energy use now play a key role in reducing electricity consumption, particularly miscellaneous electrical loads, in buildings. Identifying device operating modes (mode extraction) creates a better understanding of both device and system behaviors. Using clustering to extract operating modes from electrical load data can provide valuable insightsinto device behavior and identify opportunities for energy savings. We present a fast and effective heuristic clustering method to identify and extract operating modes in electrical load data.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Scalable Proximity-Based Methods for Large-Scale Analysis of Atom Probe Data

Powered by recent advances in data acquisition technologies, today's state-of-the-art atom probe microscopes yield data sets with sizes ranging from a few million atoms to billions of atoms. Analysis of these atomic data sets within rea-sonable turnaround times is a pressing data analysis challenge for material scientists currently equipped with software systems that do not scale to these massive data sets. Here, we present the shared memory component of a larger ongoing effort to develop a multi-feature data analysis framework capable of analyzing atom probe data of all sizes and scales from desktop multicore machines to large-scale high-performance computing platforms with hybrid (shared and distributed memory) architectures. Our focus here is on a broad class of popular atom probe data analysis methods that rely on core time-consuming k-NN queries. We present a scalable, heuristic algorithm for k-NN queries using three-dimensional range trees. To demonstrate its efficacy, the k-NN algorithm is integrated with two use cases of atom probe data analysis methods and the resulting analysis times are shown to speedup by over 20X on a 32-core Cray XC40 node using workloads up to 8 million atoms, which is already beyond the at-scale capabilities of existing atom probe software. Using this k-NN algorithm, we also introduce a novel parameter estimation method for a class of cluster finding methods, called friends-of-friends (FoF) methods, to completely bypass their expensive pre-processing steps. In each case, we validate the results on a variety of control data sets.

Lu, Hao↗

An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

AutoReP: Automatic ReLU Replacement for Fast Private Network Inference

The proliferation of the Machine-Learning-As-A-Service (MLaaS) market has brought to light a number of clients’ data privacy and security concerns. One promising solution is private inference (PI) techniques using cryptographic primitives. These techniques often come with high computation and communication overhead associated with the non-linear operator such as ReLU. Several approaches have been developed in reducing the number of ReLU operations, however, they either require a heuristic threshold selection or introduce significant accuracy drop. This work presents AutoReP, a gradient-based framework for non-linear operators reduction that aims to mitigate these concerns from a systematic perspective. AutoReP automates the process of discrete selection of ReLU and polynomial functions on neurons to accelerate PI applications. We also introduce distribution-aware polynomial approximation (DaPa) to accurately approximate ReLUs under given distribution, preserving model expressivity. Our experimental results demonstrate significant accuracy improvements of 6.12% (94.31%, 12.9K ReLU budget, CIFAR-10), 8.39% (74.92%, 12.9K ReLU budget, CIFAR-100), and 9.45% (63.69%, 55K ReLU budget, Tiny-ImageNet) over current state-of-the-art methods, e.g., SNL. Morever, AutoReP is applied to EfficientNet-B2 on ImageNet dataset, and achieved 75.55% accuracy with 176.1 × ReLU budget reduction.

Peng, Hongwu↗

A One-Class Support Vector Machine Calibration Method for Time Series Change Point Detection

Identifying the change point of a system’s health status is critical. Indeed, a change point usually signifies an incipient fault under development. The One-Class Support Vector Machine (OC-SVM) is a popular machine learning model for anomaly detection that could be used for identifying change points; yet, it is sometimes difficult to obtain a good OC-SVM model that can be used on sensor measurement time series to identify the change points in system health status. In this paper, we propose a novel approach for calibrating OC-SVM models. Our method uses a heuristic search method to find a good set of input data and hyperparameters that yield a well-performing model. Our results on the C-MAPSS dataset demonstrate that OC-SVM can achieve satisfactory accuracy in detecting change point in time series with fewer training data, compared to state-of-the-art deep learning approaches. In our case study, the OC-SVM calibrated by the proposed model is shown to be useful especially in scenarios with limited amount of training data.

42 ENGINEERING↗

Iterative ramp sharpening for structure signature-preserving simplification of images

In this paper, we present a simple and heuristic ramp sharpening algorithm that achieves local contrast enhancement of vector-valued images. The proposed algorithm performs a local comparison of intensity values as well as gradient strength and directional information derived from the gradient structure tensor so that the sharpening is applied only for pixels found on the ramps around true edges. This way, the contrast between objects and regions separated by a ramp is enhanced correspondingly, avoiding ringing artefacts. It is found that applying this technique in an iterative manner on blurred imagery produces sharpening preserving both structure and signature of the image. The final approach reaches a good compromise between complexity and effectiveness for image simplification, enhancing in an efficient manner the image details and maintaining the overall image appearance.

97 MATHEMATICS AND COMPUTING↗

Linking Threat Agents to Targeted Organizations: A Pipeline for Enhanced Cybersecurity Risk Metrics

In this study, we present a methodology leveraging Large Language Models (LLMs) to transform Cybersecurity Threat Intelligence (CTI) narratives into actionable insights for individual organizations. Our approach automates the extraction of machine-readable adversary SKRAM (Skills, Knowledge, Resources, Authorities, and Motivation) attributes from open-source reports, extending LLM utility beyond typical interactions. This innovation enables precise, automated assessments of cybersecurity risks posed by various adversaries. Using a chain-of-thought and multi-shot prompting strategy, our methodology advances the automation of cybersecurity feature extraction for new machine-learning models that predict the risk of adversary targeting. This approach is refined using a substantial dataset of over 150 analyst-validated threat reports and synthetic organizational data from 900 companies. Here, by bootstrapping the training data with a rule-based heuristic over synthetic data, we have developed a high-accuracy machine-learning model that allows entities to dynamically prioritize threats and defensive actions.

Cyber Threat Intelligence↗

Approximate Mixed-Integer Programming Solution with Machine Learning Technique and Linear Programming Relaxation

Security constrained unit commitment (SCUC) is solved in the day-ahead electricity market to determine electricity generation schedule for the following date. The associated mixed integer programming (MIP) problem is known computationally hard. Heuristics like rounding can be computationally efficient for solving large MIP problems however often produces lower quality solutions due to discrepancy between MIP solution and linear programming relaxation (LPR) solution, i.e., variables taking different discrete values between MIP and LPR solutions. In this work, we applied the machine learning-based algorithms—Classification and Regression Tree (CART) model and random forest (RF) model—to obtain an LPR-based approximation that close to an MIP solution without actually solving the MIP problem. By computing feature importance derived from the CART and RF models, we assessed the link between coefficients in the MIP model, the LPR solution, and the optimal solution of the MIP problem. We applied the CART and RF approaches to solve SCUC problems using day-ahead energy market cases from Midcontinent Independent System Operator. The results show that our method is computationally efficient and could achieve an approximation sufficiently close to the SCUC solution with <0.15% error and ~78% reduction in the discrepancies between LPR and MIP solutions.

Lin, Xinming↗

MARS: Malleable Actor-Critic Reinforcement Learning Scheduler

In this paper, we introduce MARS, a new scheduling system for HPC-cloud infrastructures based on a cost-aware, flexible reinforcement learning approach, which serves as an intermediate layer for next generation HPC-cloud resource manager. MARS ensembles the pre-trained models from heuristic workloads and decides on the most cost-effective strategy for optimization. A whole workflow application would be split into several optimizable dependent sub-tasks, then based on the pre- defined resource management plan, a reward will be generated after executing a scheduled task. Lastly, MARS updates the Deep Neural Network (DNN) model based on the reward. MARS is designed to optimize the existing models through reinforcement mechanisms. MARS adapts to the dynamics of workflow applications, selects the most cost-effective scheduling solution among pre-built scheduling strategies (backfilling, SJF, etc.) and self- learning deep neural network model at run-time. We evaluate MARS with different real-world workflow traces. MARS can achieve 5%-60% increased performance compare to state-of-the- art approaches.

Baheri, Betis↗

Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing System

This study considers a heterogeneous computing system and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The heterogeneous system and workload described here are representative of a prototypical computing environment being studied as part of this collaboration. Each task can exhibit a time-varying importance or utility to the overall enterprise. In this system, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the system to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a heterogeneous computing system. The contributions of this paper are: (a) a mathematical model of a heterogeneous computing system where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment.

99 GENERAL AND MISCELLANEOUS↗

MICCO: An Enhanced Multi-GPU Scheduling Framework for Many-Body Correlation Functions

Calculation of many-body correlation functions is one of the critical kernels utilized in many scientific computing areas, especially in Lattice Quantum Chromodynamics (Lattice QCD). It is formalized as a sum of a large number of contraction terms each of which can be represented by a graph consisting of vertices describing quarks inside a hadron node and edges designating quark propagations at specific time intervals. Due to its computation- and memory-intensive nature, real-world physics systems (e.g., multi-meson or multi-baryon systems) explored by Lattice QCD prefer to leverage multi-GPUs. Different from general graph processing, many-body correlation function calculations show two specific features: a large number of computation-/data-intensive kernels and frequently repeated appearances of original and intermediate data. The former results in expensive memory operations such as tensor movements and evictions. The latter offers data reuse opportunities to mitigate the data-intensive nature of many-body correlation function calculations. However, existing graph-based multi-GPU schedulers cannot capture these data-centric features, thus resulting in a sub-optimal performance for many-body correlation function calculations. To address this issue, this paper presents a multi-GPU scheduling framework, MICCO, to accelerate contractions for correlation functions particularly by taking the data dimension (e.g., data reuse and data eviction) into account. This work first performs a comprehensive study on the interplay of data reuse and load balance, and designs two new concepts: local reuse pattern and reuse bound to study the opportunity of achieving the optimal trade-off between them. Based on this study, MICCO proposes a heuristic scheduling algorithm and a machine-learning-based regression model to generate the optimal setting of reuse bounds. Specifically, MICCO is integrated into a real-world Lattice QCD system, Redstar, for the first time running on multiple GPUs. The evaluation demonstrates MICCO outperforms other state-of-art works, achieving up to 2.25× speedup in synthesized datasets, and 1.49× speedup in real-world correlation functions.

Wang, Qihan↗