Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Integer Optimization”

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 487 records · Page 27
All sourcesNASA NTRSDOE OSTI
NASA NTRS2003

Runway Operations Planning: A Two-Stage Solution Methodology

The airport runway is a scarce resource that must be shared by different runway operations (arrivals, departures and runway crossings). Given the possible sequences of runway events, careful Runway Operations Planning (ROP) is required if runway utilization is to be maximized. Thus, Runway Operations Planning (ROP) is a critical component of airport operations planning in general and surface operations planning in particular. From the perspective of departures, ROP solutions are aircraft departure schedules developed by optimally allocating runway time for departures given the time required for arrivals and crossings. In addition to the obvious objective of maximizing throughput, other objectives, such as guaranteeing fairness and minimizing environmental impact, may be incorporated into the ROP solution subject to constraints introduced by Air Traffic Control (ATC) procedures. Generating optimal runway operations plans was approached in with a 'one-stage' optimization routine that considered all the desired objectives and constraints, and the characteristics of each aircraft (weight class, destination, Air Traffic Control (ATC) constraints) at the same time. Since, however, at any given point in time, there is less uncertainty in the predicted demand for departure resources in terms of weight class than in terms of specific aircraft, the ROP problem can be parsed into two stages. In the context of the Departure Planner (OP) research project, this paper introduces Runway Operations Planning (ROP) as part of the wider Surface Operations Optimization (SOO) and describes a proposed 'two stage' heuristic algorithm for solving the Runway Operations Planning (ROP) problem. Focus is specifically given on including runway crossings in the planning process of runway operations. In the first stage, sequences of departure class slots and runwy crossings slots are generated and ranked based on departure runway throughput under stochastic conditions. In the second stage, the departure class slots are populated with specific flights from the pool of available aircraft, by solving an integer program. Preliminary results from the algorithm implementation on real-world traffic data are included.

Anagnostakis, Ioannis↗
NASA NTRSDate not supplied

A Multilevel Approach For SolvingLarge-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization

Quantum approximate optimization is one ofthe promising candidates for useful quantum computation,particularly in the context of finding approximate solutionsto Quadratic Unconstrained Binary Optimization (QUBO)problems. However, the existing quantum processing units(QPUs) are of relatively small size, and canonical mappingsof QUBO via the Ising model require one qubit per vari-able, rendering direct large-scale optimization infeasible.In classical optimization, a general strategy for addressingmany large-scale problems is via multilevel/multigrid meth-ods, where the large target problem is iteratively coarsenedand the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentallytest how existing QPUs perform when used as a sub-solverwithin such a multilevel strategy. To this aim, we com-bine and extend (via additional classical processing steps)the recently proposed Noise-Directed Adaptive Remapping(NDAR) and Quantum Relax&Round (QRR) algorithms.We first demonstrate the effectiveness of our heuristicextensions on Rigetti’s superconducting transmon deviceAnkaa-2. We find approximate solutions to10instances offully connected82-qubit Sherrington-Kirkpatrick graphswith random integer-valued coefficients obtaining normal-ized approximation ratios (ARs) in the range∼0.98−1.0,and the same class with real-valued coefficients (ARs∼0.94−1.0). Then, we implement the extended NDAR andQRR algorithms as subsolvers in the multilevel algorithmfor6large-scale graphs with at most∼27,000variables.In practice, the QPU (with classical post-processing steps)is used to find approximate solutions to dozens of at most82-qubit problems, which are iteratively used to constructthe global solution. We observe that quantum optimizationresults are competitive in terms of the quality of solutionswhen compared to classical heuristics used as subsolverswithin the multilevel approach.Reproducibility: source code and data are available at[TBA upon acceptance]

quantum computing↗
DOE OSTI2022

Natural gas maximal load delivery for multi-contingency analysis

An increasing dependence on natural gas has amplified existing vulnerabilities to the power grid, including disruptions to gas transmission networks from natural and man-made disasters. To address the operational challenges arising from these disruptions, we, in this study, consider the problem of estimating the steady-state operating capacity of a damaged gas pipeline network while ensuring the maximal delivery of load. Specifically, we formulate the mixed-integer nonconvex maximal load delivery (MLD) problem, which proves difficult to solve on large-scale networks. To address this challenge, we present a relaxation of the MLD problem and use it to determine bounds on the transport capacity of a gas pipeline system. A rigorous computational evaluation over network models ranging in size from 11 to 4,197 junctions shows that the relaxation-based method is suitable for analyzing the impacts of multi-contingency network disruptions, often converging to the optimal solution of the relaxation in less than ten seconds.

03 NATURAL GAS↗
NASA NTRS2008

Quantum-Inspired Maximizer

A report discusses an algorithm for a new kind of dynamics based on a quantum- classical hybrid-quantum-inspired maximizer. The model is represented by a modified Madelung equation in which the quantum potential is replaced by different, specially chosen 'computational' potential. As a result, the dynamics attains both quantum and classical properties: it preserves superposition and entanglement of random solutions, while allowing one to measure its state variables, using classical methods. Such optimal combination of characteristics is a perfect match for quantum-inspired computing. As an application, an algorithm for global maximum of an arbitrary integrable function is proposed. The idea of the proposed algorithm is very simple: based upon the Quantum-inspired Maximizer (QIM), introduce a positive function to be maximized as the probability density to which the solution is attracted. Then the larger value of this function will have the higher probability to appear. Special attention is paid to simulation of integer programming and NP-complete problems. It is demonstrated that the problem of global maximum of an integrable function can be found in polynomial time by using the proposed quantum- classical hybrid. The result is extended to a constrained maximum with applications to integer programming and TSP (Traveling Salesman Problem).

Zak, Michail↗
NASA NTRS1991

On optimal filtering of GPS dual frequency observations without using orbit information

The concept of optimal filtering of observations collected with a dual frequency GPS P-code receiver is investigated in comparison to an approach for C/A-code units. The filter presented here uses only data gathered between one receiver and one satellite. The estimated state vector consists of a one-way pseudorange, ionospheric influence, and ambiguity biases. Neither orbit information nor station information is required. The independently estimated biases are used to form double differences where, in case of a P-code receiver, the wide lane integer ambiguities are usually recovered successfully except when elevation angles are very small. An elevation dependent uncertainty for pseudorange measurements was discovered for different receiver types. An exponential model for the pseudorange uncertainty was used with success in the filter gain computations.

Eueler, Hans-Juergen↗
DOE OSTI2021

CAN-D: A Modular Four-Step Pipeline for Comprehensively Decoding Controller Area Network Data

Controller area networks (CANs) are a broadcast protocol for real-time communication of critical vehicle subsystems. Original equipment manufacturers of passenger vehicles hold secret their mappings of CAN data to vehicle signals, and these definitions vary according to make, model, and year. Without these mappings, the wealth of real-time vehicle information hidden in the CAN packets is uninterpretable, severely impeding vehicle-related research, including CAN cybersecurity and privacy studies, aftermarket tuning, efficiency and performance monitoring, and fault diagnosis to name a few. Guided by the four-part CAN signal definition, we present CAN-D (CAN-Decoder), a modular, four-step pipeline for identifying each signal's boundaries (start bit and length), endianness (byte ordering), signedness (bit-to-integer encoding), and by leveraging diagnostic standards, augmenting a subset of the extracted signals with meaningful, physical interpretation. En route to CAN-D, we provide a comprehensive review of the CAN signal reverse engineering research. All previous methods ignore endianness and signedness, rendering them incapable of decoding many standard CAN signal definitions. Incorporating endianness grows the search space from 128 to 4.72E21 signal tokenizations and introduces a web of changing dependencies. In response, we formulate, formally analyze, and provide an efficient solution to an optimization problem, allowing identification of the optimal set of signal boundaries and byte orderings. In addition, we provide two novel, state-of-the-art signal boundary classifiers—both of which are superior to previous approaches in precision and recall in three different test scenarios—and the first signedness classification algorithm, which exhibits a $>$ 97% F-score. Altogether, CAN-D is the only solution with the potential to extract any CAN signal that is also the state of the art. In evaluation on 10 vehicles of different makes, CAN-D's average $\ell ^1$ error is five times better (81% less) than all previous methods and exhibits lower average error, even when considering only signals that meet prior methods’ assumptions. Finally, CAN-D is implemented in lightweight hardware, allowing for an on-board diagnostic (OBD-II) plugin for real-time in-vehicle CAN decoding.

42 ENGINEERING↗
DOE OSTI2024

Joint Expansion Planning of Power and Water Distribution Networks

This research considers the joint expansion planning of power and water distribution networks, which are interdependent at various levels. We consider the dependency arising through the power consumption of pumps and develop models for integrating new components into existing networks. Then, we formulate the joint expansion planning as a Mixed Integer Nonlinear Program (MINLP). Applying this MINLP to a small-scale test network, we illustrate the advantages offered by joint expansion planning, such as increased flexibility and reduced costs and redundancy, over independently expanding power and water distribution networks.

expansion planning↗
NASA NTRS1984

Shuffle-exchanges on augmented meshes

A mesh connected array of size N = two to the Kth power, K an integer, can be augmented by adding at most one edge per node such that it can perform a shuffle-exchange of size N/2 in constant time. A shuffle-exchange of size N is performed on this augmented array in constant time. This is done by combining the available perfect shuffle of size N/2 with the existing nearest neighbor connections of the mesh. By carefully scheduling the different permutations that are composed in order to achieve the shuffle, the time required is reduced to 5 steps, which is optimal for this network.

Bokhari, S. H.↗
NASA NTRS1992

Data parallel sorting for particle simulation

Sorting on a parallel architecture is a communications intensive event which can incur a high penalty in applications where it is required. In the case of particle simulation, only integer sorting is necessary, and sequential implementations easily attain the minimum performance bound of O (N) for N particles. Parallel implementations, however, have to cope with the parallel sorting problem which, in addition to incurring a heavy communications cost, can make the minimun performance bound difficult to attain. This paper demonstrates how the sorting problem in a particle simulation can be reduced to a merging problem, and describes an efficient data parallel algorithm to solve this merging problem in a particle simulation. The new algorithm is shown to be optimal under conditions usual for particle simulation, and its fieldwise implementation on the Connection Machine is analyzed in detail. The new algorithm is about four times faster than a fieldwise implementation of radix sort on the Connection Machine.

Dagum, Leonardo↗
DOE OSTI2020

Practice Summary: Improved Reliability via Optimization in Residential Microgrids

Southern Company is an electric utility that is embracing residential microgrids as a platform for distributed energy. The first residential microgrid in the southeastern United States was constructed in Hoover, Alabama, as a testbed for development. To operate the microgrid, we developed an optimization model for unit commitment and economic dispatch. We report the optimization model was implemented in a microgrid central controller and tested under various operational scenarios. Challenges also include developing a pricing algorithm to deliver price forecasts to the residential homes in the microgrid and open-source software restrictions.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2023

Minimal Energy Routing of a Leader and a Wingmate with Periodic Connectivity

We consider a route planning problem in which two unmanned vehicles are required to complete a set of tasks present at distinct locations, referred to as targets, with minimum energy consumption. The mission environment is hazardous, and to ensure a safe operation, the UVs are required to communicate with each other at every target they visit. The problem objective is to determine the allocation of the tasks to the UVs and plan tours for the UVs to visit the targets such that the weighted sum of the distances traveled by the UVs and the distances traveled by the communicating signals between them is minimized. We formulate this problem as an Integer program and show that naively solving the problem using commercially available off-the-shelf solvers is insufficient in determining scalable solutions efficiently. To address this computational challenge, we develop an approximation and a heuristic algorithm, and employ them to compute high-quality solutions to a special case of the problem where equal weights are assigned to the distances traveled by the vehicles and the communicating signals. For this special case, we show that the approximation algorithm has a fixed approximation ratio of 3.75. We also develop lower bounds to the optimal cost of the problem to evaluate the performance of these algorithms on large-scale instances. We demonstrate the performance of these algorithms on 500 randomly generated instances with the number of targets ranging from 6 to 100, and show that the algorithms provide high-quality solutions to the problem swiftly; the average computation time of the algorithmic solutions is within a fraction of a second for instances with at most 100 targets. Finally, we show that the approximation ratio has a variable ratio for the weighted case of the problem. Specifically, if ρ denotes the ratio of the weights assigned to the distances representing the communication and travel costs, the algorithm has an a posteriori ratio of $3 + \frac{3ρ}{4}$ when ρ ≥ 1, and $\frac{3}{ρ}$ + $\frac{3}{4}$ when ρ ≤ 1.

42 ENGINEERING↗
NASA NTRS1975

International Symposium on Remote Sensing of Environment, 10th, University of Michigan, Ann Arbor, Mich., October 6-10, 1975, Proceedings. Volumes 1 & 2

Topics treated include the application of a Fourier transform spectrometer to infrared remote sensing, the performance optimization of a satellite-borne thematic mapper, a data handling system to be integrated with a digital airborne multispectral scanner, infrared thermography for micro- and mesometeorological measurements, satellite interrogated data collection platforms for river and flood forecasting and the automatic measurement of sea surface temperature from a GOES satellite. Solar and atmospheric effects on satellite imagery derived from aircraft reflectance measurements, methods for determining haze levels from multispectral scanner data, restoration of Landsat images by discrete two-dimensional deconvolution and the automatic classification of aircraft and satellite multispectral images using mixed integer programming are also discussed. Individual items are announced in this issue.

Source record↗
DOE OSTI2022

Noisy intermediate-scale quantum algorithms

A universal fault-tolerant quantum computer that can efficiently solve problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement toward realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e., qubits that are not error corrected, and therefore perform imperfect operations within a limited coherence time. In the search for achieving quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry, and combinatorial optimization. The overarching goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, a thorough summary of NISQ computational paradigms and algorithms is provided. The key structure of these algorithms and their limitations and advantages are discussed. Finally, a comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices is additionally provided.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

A scalable planning framework of energy storage systems under frequency dynamics constraints

As the penetration of renewables increases in power systems, the declining system inertia can cause frequency stability issues. Battery energy storage systems (BESSs) respond fast and therefore can relieve the low inertia difficulty but need to be appropriately sized considering the associated cost. This paper presents a novel stochastic optimization model for economically planning BESS capacity while considering the spatial–temporal correlation of wind generation and generator outages under frequency stability constraints, which include the rate-of-change of frequency (RoCoF), frequency nadir (FN), and quasi-steady-state (QSS) frequency. A set of new FN constraints that can be easily linearized is developed. To account for renewable uncertainties, a realistic uncertainty modeling approach, Random Field, is adopted to generate wind generation scenarios by considering both spatial and temporal evolutions of wind speed profiles. The ESS sizing is formulated as a mixed-integer linear programming problem and solved by using a scalable decomposition-and-coordination approach, Surrogate Absolute Value Lagrangian Relaxation (SAVLR). To further improve the scalability and reduce computational burdens, a rolling-horizon-based update is developed and incorporated into SAVLR for providing a practical solution to the long-term planning of very large-scale power systems. Finally, a modified IEEE 118-bus system and the Polish system are used to validate the effectiveness and scalability of the model and solution methodology.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2012

Efficient Computation of Separation-Compliant Speed Advisories for Air Traffic Arriving in Terminal Airspace

A class of problems in air traffic management asks for a scheduling algorithm that supplies the air traffic services authority not only with a schedule of arrivals and departures, but also with speed advisories. Since advisories must be finite, a scheduling algorithm must ultimately produce a finite data set, hence must either start with a purely discrete model or involve a discretization of a continuous one. The former choice, often preferred for intuitive clarity, naturally leads to mixed-integer programs, hindering proofs of correctness and computational cost bounds (crucial for real-time operations). In this paper, a hybrid control system is used to model air traffic scheduling, capturing both the discrete and continuous aspects. This framework is applied to a class of problems, called the Fully Routed Nominal Problem. We prove a number of geometric results on feasible schedules and use these results to formulate an algorithm that attempts to compute a collective speed advisory, effectively finite, and has computational cost polynomial in the number of aircraft. This work is a first step toward optimization and models refined with more realistic detail.

Sadovsky, Alexander V.↗
DOE OSTI2022

Machine Learning for Slow Spill Regulation in the Fermilab Delivery Ring for Mu2e

A third-integer resonant slow extraction system is being developed for the Fermilab’s Delivery Ring to deliver protons to the Mu2e experiment. During a slow extraction process, the beam on target is liable to experience small intensity variations due to many factors. Owing to the experiment’s strict requirements in the quality of the spill, a Spill Regulation System (SRS) is currently under design. The SRS primarily consists of three components - slow regulation, fast regulation, and harmonic content tracker. In this presentation, we shall present the investigations of using Machine Learning (ML) in the fast regulation system, including further optimizations of PID controller gains for the fast regulation, prospects of an ML agent completely replacing the PID controller using supervised learning schemes such as Long Short-Term Memory (LSTM) and Gated Recurrent Unit (GRU) ML models, the simulated impact and limitation of machine response characteristics on the effectiveness of both PID and ML regulation of the spill. We also present here nascent results of Reinforcement Learning efforts, including continuous-action soft actor-critic methods, to regulate the spill rate.

43 PARTICLE ACCELERATORS↗
NASA NTRS1981

An optimization model for energy generation and distribution in a dynamic facility

An analytical model is described using linear programming for the optimum generation and distribution of energy demands among competing energy resources and different economic criteria. The model, which will be used as a general engineering tool in the analysis of the Deep Space Network ground facility, considers several essential decisions for better design and operation. The decisions sought for the particular energy application include: the optimum time to build an assembly of elements, inclusion of a storage medium of some type, and the size or capacity of the elements that will minimize the total life-cycle cost over a given number of years. The model, which is structured in multiple time divisions, employ the decomposition principle for large-size matrices, the branch-and-bound method in mixed-integer programming, and the revised simplex technique for efficient and economic computer use.

Lansing, F. L.↗
DOE OSTI2021

Electronic, magnetic, and optical properties of bulk and (1 1 1)-surfaces of CoMnZnSi quaternary Heusler alloy

The structural stability, electronic structure, and magnetic and optical properties of CoMnZnSi quaternary Heusler alloy (QHA) in the bulk and (1 1 1)-slab forms have been investigated by performing density functional theory (DFT) calculations. Formation and cohesive energies, and elastic constants confirm that the bulk CoMnZnSi is chemically and mechanically stable at an equilibrium lattice parameter of 5.81 Å. The calculated elastic constants also indicate that this QHA has ductile and anisotropic features. We investigate and discuss the bonding behavior from charge density distribution and density of states. Furthermore, these calculations in the bulk phase show a perfect half-metallic behavior with an integer value of magnetic moment (4 µB) and a large spin-flip gap of 0.39 eV. On the other hand, the Co (1 1 1) and Si (1 1 1)-slabs exhibit semi-metallic nature at the Fermi level. These results indicate that CoMnZnSi qualifies for spintronic applications. In the bulk and Co (1 1 1), Zn (1 1 1), and Si (1 1 1)-surfaces, the magnetic moment of Co and Mn atoms are ferromagnetically aligned, while the ferrimagnetic alignment of Co with Mn has been found in Mn (1 1 1)-surface. We also investigate the optimal conductivity, dielectric functions, reflectivity, absorption coefficient, refractive index, and loss function to understand the underlying optical properties of this alloy.

36 MATERIALS SCIENCE↗