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.

SourceResearch connectionFrom yearThrough year

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

At least 109 records · Page 6

All sources NASA NTRS DOE OSTI

NASA NTRS2003

A Fast Implementation of the ISOCLUS Algorithm

Unsupervised clustering is a fundamental tool in numerous image processing and remote sensing applications. For example, unsupervised clustering is often used to obtain vegetation maps of an area of interest. This approach is useful when reliable training data are either scarce or expensive, and when relatively little a priori information about the data is available. Unsupervised clustering methods play a significant role in the pursuit of unsupervised classification. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points (or samples) in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute a set of cluster centers in d-space. Although there is no specific optimization criterion, the algorithm is similar in spirit to the well known k-means clustering method in which the objective is to minimize the average squared distance of each point to its nearest center, called the average distortion. One significant feature of ISOCLUS over k-means is that clusters may be merged or split, and so the final number of clusters may be different from the number k supplied as part of the input. This algorithm will be described in later in this paper. The ISOCLUS algorithm can run very slowly, particularly on large data sets. Given its wide use in remote sensing, its efficient computation is an important goal. We have developed a fast implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm, the filtering algorithm, by Kanungo et al.. They showed that, by storing the data in a kd-tree, it was possible to significantly reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm. For technical reasons, which are explained later, it is necessary to make a minor modification to the ISOCLUS specification. We provide empirical evidence, on both synthetic and Landsat image data sets, that our algorithm's performance is essentially the same as that of ISOCLUS, but with significantly lower running times. We show that our algorithm runs from 3 to 30 times faster than a straightforward implementation of ISOCLUS. Our adaptation of the filtering algorithm involves the efficient computation of a number of cluster statistics that are needed for ISOCLUS, but not for k-means.

Memarsadeghi, Nargess↗

NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Monte Carlo Tree Search Approach

Numerous unmanned aircraft systems operating at low altitudes to deliver goods and services may one day become ubiquitous in our cities. In the Unmanned Aircraft Systems (UAS) Traffic Management (UTM) framework, such a concept is envisioned, where aerial vehicles operate beyond visual line of sight (BVLOS) within specifically reserved and time stamped “corridors” in the airspace. For example, these corridors or operational intent volumes can connect an aerial vehicle’s origin site to its destination site for package delivery operations. There may also be more than one corridor available for an aerial vehicle to choose from and often different corridors may intersect with one another. Thus, it is imperative to ensure flight trajectories belonging to different aerial vehicles are not in conflict. Per the UTM CONOPs, we assume that a vehicle almost always stays inside its corridor or operational volume. This work provides a framework for strategic deconfliction of UTM or package delivery drones, where we schedule the departure time of all vehicles subject to various temporal constraints (including the corridor deconfliction at the intersections). We present the “multi-route weighted package delivery problem” which serves as an exemplifying model for strategic deconfliction in UTM. In the multi-route weighted package delivery problem, a graph network is given which consists of a set of depots (source) and drop-off (destination) nodes, with multiple routes (defined as a sequence of waypoints) connecting the depots to drop-off nodes. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is for a known set of aerial vehicles to depart from the depots, choose a route and take off time, while avoiding conflicts with other aerial vehicles, and minimizing both risk and distance traveled. We provide a mixed integer linear programming (MILP) formulation of the problem, as well as a heuristic solution based on Monte Carlo Tree Search (MCTS) – a method used in game theory and artificial intelligence – to overcome limitations inherent to optimal solvers. Computational results show the advantages of using MCTS over the MILP formulation; the former can provide a sub-optimal solution quickly, and may sometimes even reach an optimal solution, whereas the latter may not even produce a solution in reasonable time. Furthermore, results from both the MILP formulation and MCTS methods were validated using a preliminary agent-based simulator implementing the UTM concept of operations. Thus, the MCTS method can be seen as a scalable solution to the complex multi-route weighted package delivery problem and may possibly be extended to similar complex optimization problems.

Kenny Chour↗

NASA NTRS1990

Optimization of rotor blades for combined structural, dynamic, and aerodynamic properties

Optimal helicopter blade design with computer-based mathematical programming has received more and more attention in recent years. Most of the research has focused on optimum dynamic characteristics of rotor blades to reduce vehicle vibration. There is also work on optimization of aerodynamic performance and on composite structural design. This research has greatly increased our understanding of helicopter optimum design in each of these aspects. Helicopter design is an inherently multidisciplinary process involving strong interactions among various disciplines which can appropriately include aerodynamics; dynamics, both flight dynamics and structural dynamics; aeroelasticity: vibrations and stability; and even acoustics. Therefore, the helicopter design process must satisfy manifold requirements related to the aforementioned diverse disciplines. In our present work, we attempt to combine several of these important effects in a unified manner. First, we design a blade with optimum aerodynamic performance by proper layout of blade planform and spanwise twist. Second, the blade is designed to have natural frequencies that are placed away from integer multiples of the rotor speed for a good dynamic characteristics. Third, the structure is made as light as possible with sufficient rotational inertia to allow for autorotational landing, with safe stress margins and flight fatigue life at each cross-section, and with aeroelastical stability and low vibrations. Finally, a unified optimization refines the solution.

He, Cheng-Jian↗

NASA NTRS2010

Optimal Compression of Floating-Point Astronomical Images Without Significant Loss of Information

We describe a compression method for floating-point astronomical images that gives compression ratios of 6 - 10 while still preserving the scientifically important information in the image. The pixel values are first preprocessed by quantizing them into scaled integer intensity levels, which removes some of the uncompressible noise in the image. The integers are then losslessly compressed using the fast and efficient Rice algorithm and stored in a portable FITS format file. Quantizing an image more coarsely gives greater image compression, but it also increases the noise and degrades the precision of the photometric and astrometric measurements in the quantized image. Dithering the pixel values during the quantization process greatly improves the precision of measurements in the more coarsely quantized images. We perform a series of experiments on both synthetic and real astronomical CCD images to quantitatively demonstrate that the magnitudes and positions of stars in the quantized images can be measured with the predicted amount of precision. In order to encourage wider use of these image compression methods, we have made available a pair of general-purpose image compression programs, called fpack and funpack, which can be used to compress any FITS format image.

Pence, William D.↗

NASA NTRS1975

Planning air transport network in Appalachia

Main issues to be considered in designing an air transport system are discussed, and a model for the selection of an optimal air network for a region is presented. It was desired to have the ability to consider a dense network of nodes and air routes and variations in schedules on routes, which in combination would represent virtually all conceivable alternatives. Linear and integer programming were chosen as the most promising analysis methodologies. Integer programming was found to be intractable, while linear programming provided efficient solutions. The model was applied to studying the feasibility of a STOL network in West Virginia. Based on allowable paths, an examination of intercity demands, and established growth points, desired levels of service expressed as minimum flights were determined for certain city pairs.

Carter, E. C.↗

NASA NTRS2004

Reducing Errors by Use of Redundancy in Gravity Measurements

A methodology for improving gravity-gradient measurement data exploits the constraints imposed upon the components of the gravity-gradient tensor by the conditions of integrability needed for reconstruction of the gravitational potential. These constraints are derived from the basic equation for the gravitational potential and from mathematical identities that apply to the gravitational potential and its partial derivatives with respect to spatial coordinates. Consider the gravitational potential in a Cartesian coordinate system {x1,x2,x3}. If one measures all the components of the gravity-gradient tensor at all points of interest within a region of space in which one seeks to characterize the gravitational field, one obtains redundant information. One could utilize the constraints to select a minimum (that is, nonredundant) set of measurements from which the gravitational potential could be reconstructed. Alternatively, one could exploit the redundancy to reduce errors from noisy measurements. A convenient example is that of the selection of a minimum set of measurements to characterize the gravitational field at n3 points (where n is an integer) in a cube. Without the benefit of such a selection, it would be necessary to make 9n3 measurements because the gravitygradient tensor has 9 components at each point. The problem of utilizing the redundancy to reduce errors in noisy measurements is an optimization problem: Given a set of noisy values of the components of the gravity-gradient tensor at the measurement points, one seeks a set of corrected values - a set that is optimum in that it minimizes some measure of error (e.g., the sum of squares of the differences between the corrected and noisy measurement values) while taking account of the fact that the constraints must apply to the exact values. The problem as thus posed leads to a vector equation that can be solved to obtain the corrected values.

Kulikov, Igor↗

NASA NTRS2009

Optimal Compression Methods for Floating-point Format Images

We report on the results of a comparison study of different techniques for compressing FITS images that have floating-point (real*4) pixel values. Standard file compression methods like GZIP are generally ineffective in this case (with compression ratios only in the range 1.2 - 1.6), so instead we use a technique of converting the floating-point values into quantized scaled integers which are compressed using the Rice algorithm. The compressed data stream is stored in FITS format using the tiled-image compression convention. This is technically a lossy compression method, since the pixel values are not exactly reproduced, however all the significant photometric and astrometric information content of the image can be preserved while still achieving file compression ratios in the range of 4 to 8. We also show that introducing dithering, or randomization, when assigning the quantized pixel-values can significantly improve the photometric and astrometric precision in the stellar images in the compressed file without adding additional noise. We quantify our results by comparing the stellar magnitudes and positions as measured in the original uncompressed image to those derived from the same image after applying successively greater amounts of compression.

Pence, W. D.↗

NASA NTRS2011

A Simulation Based Approach to Optimize Berth Throughput Under Uncertainty at Marine Container Terminals

Berth scheduling is a critical function at marine container terminals and determining the best berth schedule depends on several factors including the type and function of the port, size of the port, location, nearby competition, and type of contractual agreement between the terminal and the carriers. In this paper we formulate the berth scheduling problem as a bi-objective mixed-integer problem with the objective to maximize customer satisfaction and reliability of the berth schedule under the assumption that vessel handling times are stochastic parameters following a discrete and known probability distribution. A combination of an exact algorithm, a Genetic Algorithms based heuristic and a simulation post-Pareto analysis is proposed as the solution approach to the resulting problem. Based on a number of experiments it is concluded that the proposed berth scheduling policy outperforms the berth scheduling policy where reliability is not considered.

Golias, Mihalis M.↗

NASA NTRS2013

Influence of Computational Drop Representation in LES of a Droplet-Laden Mixing Layer

Multiphase turbulent flows are encountered in many practical applications including turbine engines or natural phenomena involving particle dispersion. Numerical computations of multiphase turbulent flows are important because they provide a cheaper alternative to performing experiments during an engine design process or because they can provide predictions of pollutant dispersion, etc. Two-phase flows contain millions and sometimes billions of particles. For flows with volumetrically dilute particle loading, the most accurate method of numerically simulating the flow is based on direct numerical simulation (DNS) of the governing equations in which all scales of the flow including the small scales that are responsible for the overwhelming amount of dissipation are resolved. DNS, however, requires high computational cost and cannot be used in engineering design applications where iterations among several design conditions are necessary. Because of high computational cost, numerical simulations of such flows cannot track all these drops. The objective of this work is to quantify the influence of the number of computational drops and grid spacing on the accuracy of predicted flow statistics, and to possibly identify the minimum number, or, if not possible, the optimal number of computational drops that provide minimal error in flow prediction. For this purpose, several Large Eddy Simulation (LES) of a mixing layer with evaporating drops have been performed by using coarse, medium, and fine grid spacings and computational drops, rather than physical drops. To define computational drops, an integer NR is introduced that represents the ratio of the number of existing physical drops to the desired number of computational drops; for example, if NR=8, this means that a computational drop represents 8 physical drops in the flow field. The desired number of computational drops is determined by the available computational resources; the larger NR is, the less computationally intensive is the simulation. A set of first order and second order flow statistics, and of drop statistics are extracted from LES predictions and are compared to results obtained by filtering a DNS database. First order statistics such as Favre averaged stream-wise velocity, Favre averaged vapor mass fraction, and the drop stream-wise velocity, are predicted accurately independent of the number of computational drops and grid spacing. Second order flow statistics depend both on the number of computational drops and on grid spacing. The scalar variance and turbulent vapor flux are predicted accurately by the fine mesh LES only when NR is less than 32, and by the coarse mesh LES reasonably accurately for all NR values. This is attributed to the fact that when the grid spacing is coarsened, the number of drops in a computational cell must not be significantly lower than that in the DNS.

Bellan, Josette↗

NASA NTRS1982

The performance of M-ary FH-DPSK in the presence of partial-band multitone jamming

Using a geometric approach, the performance of M-ary FH-DPSK in the presence of partial-band multitone jamming is evaluated. The optimal jamming strategy is determined as a function of the number of signaling levels M and the ensuing results are used to determine worst case bit error probability performance as a function of this same parameter. It is demonstrated that, for M = 2 to the m power (where m is an integer), the best performance is obtained for M = 4.

Simon, M. K.↗

NASA NTRS2011

Fast Image Texture Classification Using Decision Trees

Texture analysis would permit improved autonomous, onboard science data interpretation for adaptive navigation, sampling, and downlink decisions. These analyses would assist with terrain analysis and instrument placement in both macroscopic and microscopic image data products. Unfortunately, most state-of-the-art texture analysis demands computationally expensive convolutions of filters involving many floating-point operations. This makes them infeasible for radiation- hardened computers and spaceflight hardware. A new method approximates traditional texture classification of each image pixel with a fast decision-tree classifier. The classifier uses image features derived from simple filtering operations involving integer arithmetic. The texture analysis method is therefore amenable to implementation on FPGA (field-programmable gate array) hardware. Image features based on the "integral image" transform produce descriptive and efficient texture descriptors. Training the decision tree on a set of training data yields a classification scheme that produces reasonable approximations of optimal "texton" analysis at a fraction of the computational cost. A decision-tree learning algorithm employing the traditional k-means criterion of inter-cluster variance is used to learn tree structure from training data. The result is an efficient and accurate summary of surface morphology in images. This work is an evolutionary advance that unites several previous algorithms (k-means clustering, integral images, decision trees) and applies them to a new problem domain (morphology analysis for autonomous science during remote exploration). Advantages include order-of-magnitude improvements in runtime, feasibility for FPGA hardware, and significant improvements in texture classification accuracy.

Thompson, David R.↗

NASA NTRS1993

Stochastic search in structural optimization - Genetic algorithms and simulated annealing

An account is given of illustrative applications of genetic algorithms and simulated annealing methods in structural optimization. The advantages of such stochastic search methods over traditional mathematical programming strategies are emphasized; it is noted that these methods offer a significantly higher probability of locating the global optimum in a multimodal design space. Both genetic-search and simulated annealing can be effectively used in problems with a mix of continuous, discrete, and integer design variables.

Hajela, Prabhat↗

NASA NTRS1987

Optimization of orbital assignment and specification of service areas in satellite communications

The mathematical nature of the orbital and frequency assignment problem for communications satellites is explored, and it is shown that choosing the correct permutations of the orbit locations and frequency assignments is an important step in arriving at values which satisfy the signal-quality requirements. Two methods are proposed to achieve better spectrum/orbit utilization. The first, called the delta S concept, leads to orbital assignment solutions via either mixed-integer or restricted basis entry linear programming techniques; the method guarantees good single-entry carrier-to-interference ratio results. In the second, a basis for specifying service areas is proposed for the Fixed Satellite Service. It is suggested that service areas should be specified according to the communications-demand density in conjunction with the delta S concept in order to enable the system planner to specify more satellites and provide more communications supply.

Wang, Cou-Way↗

NASA NTRS2013

NASA Tech Briefs, May 2013

Topics include: Test Waveform Applications for JPL STRS Operating Environment; Pneumatic Proboscis Heat-Flow Probe; Method to Measure Total Noise Temperature of a Wireless Receiver During Operation; Cursor Control Device Test Battery; Functional Near-Infrared Spectroscopy Signals Measure Neuronal Activity in the Cortex; ESD Test Apparatus for Soldering Irons; FPGA-Based X-Ray Detection and Measurement for an X-Ray Polarimeter; Sequential Probability Ratio Test for Spacecraft Collision Avoidance Maneuver Decisions; Silicon/Carbon Nanotube Photocathode for Splitting Water; Advanced Materials and Fabrication Techniques for the Orion Attitude Control Motor; Flight Hardware Packaging Design for Stringent EMC Radiated Emission Requirements; RF Reference Switch for Spaceflight Radiometer Calibration; An Offload NIC for NASA, NLR, and Grid Computing; Multi-Scale CNT-Based Reinforcing Polymer Matrix Composites for Lightweight Structures; Ceramic Adhesive and Methods for On-Orbit Repair of Re-Entry Vehicles; Self-Healing Nanocomposites for Reusable Composite Cryotanks; Pt-Ni and Pt-Co Catalyst Synthesis Route for Fuel Cell Applications; Aerogel-Based Multilayer Insulation with Micrometeoroid Protection; Manufacturing of Nanocomposite Carbon Fibers and Composite Cylinders; Optimized Radiator Geometries for Hot Lunar Thermal Environments; A Mission Concept: Re-Entry Hopper-Aero-Space-Craft System on-Mars (REARM-Mars); New Class of Flow Batteries for Terrestrial and Aerospace Energy Storage Applications; Reliability of CCGA 1152 and CCGA 1272 Interconnect Packages for Extreme Thermal Environments; Using a Blender to Assess the Microbial Density of Encapsulated Organisms; Mixed Integer Programming and Heuristic Scheduling for Space Communication; Video Altimeter and Obstruction Detector for an Aircraft; Control Software for Piezo Stepping Actuators; Galactic Cosmic Ray Event-Based Risk Model (GERM) Code; Sasquatch Footprint Tool; and Multi-User Space Link Extension (SLE) System.

Source record↗

NASA NTRS1986

The role of service areas in the optimization of FSS orbital and frequency assignments

An implicit relationship is derived which relates the topocentric separation of two satellites required for a given level of single-entry protection to the separation and orientation of their service areas. The results are presented explicitly for circular beams and topocentric angles. A computational approach is given for elliptical beams and for use with longitude and latitude variables. It is found that the geocentric separation depends primarily on the service area separation, secondarily on a parameter which characterizes the electrical design, and only slightly on the mean orbital position of the satellites. Both linear programming and mixed integer programming algorithms are implemented. Possible objective function choices are discussed, and explicit formulations are presented for the choice of the sum of the absolute deviations of the orbital locations from some prescribed 'ideal' location set. A test problem involving six service areas is examined with results that are encouraging with respect to applying the linear programming procedure to larger scenarios.

Levis, C. A.↗

NASA NTRS2017

Efficient Trajectory Options Allocation for the Collaborative Trajectory Options Program

The Collaborative Trajectory Options Program (CTOP) is a Traffic Management Initiative (TMI) intended to control the air traffic flow rates at multiple specified Flow Constrained Areas (FCAs), where demand exceeds capacity. CTOP allows flight operators to submit the desired Trajectory Options Set (TOS) for each affected flight with associated Relative Trajectory Cost (RTC) for each option. CTOP then creates a feasible schedule that complies with capacity constraints by assigning affected flights with routes and departure delays in such a way as to minimize the total cost while maintaining equity across flight operators. The current version of CTOP implements a Ration-by-Schedule (RBS) scheme, which assigns the best available options to flights based on a First-Scheduled-First-Served heuristic. In the present study, an alternative flight scheduling approach is developed based on linear optimization. Results suggest that such an approach can significantly reduce flight delays, in the deterministic case, while maintaining equity as defined using a Max-Min fairness scheme.

Traffic Management Initiative (TMI)↗

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↗