Search NASA⌕ Search

SEARCH · Search NASA

Results for “Integer programming”

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 883 records · Page 49

Proposed data compression schemes for the Galileo S-band contingency mission

The Galileo spacecraft is currently on its way to Jupiter and its moons. In April 1991, the high gain antenna (HGA) failed to deploy as commanded. In case the current efforts to deploy the HGA fails, communications during the Jupiter encounters will be through one of two low gain antenna (LGA) on an S-band (2.3 GHz) carrier. A lot of effort has been and will be conducted to attempt to open the HGA. Also various options for improving Galileo's telemetry downlink performance are being evaluated in the event that the HGA will not open at Jupiter arrival. Among all viable options the most promising and powerful one is to perform image and non-image data compression in software onboard the spacecraft. This involves in-flight re-programming of the existing flight software of Galileo's Command and Data Subsystem processors and Attitude and Articulation Control System (AACS) processor, which have very limited computational and memory resources. In this article we describe the proposed data compression algorithms and give their respective compression performance. The planned image compression algorithm is a 4 x 4 or an 8 x 8 multiplication-free integer cosine transform (ICT) scheme, which can be viewed as an integer approximation of the popular discrete cosine transform (DCT) scheme. The implementation complexity of the ICT schemes is much lower than the DCT-based schemes, yet the performances of the two algorithms are indistinguishable. The proposed non-image compression algorith is a Lempel-Ziv-Welch (LZW) variant, which is a lossless universal compression algorithm based on a dynamic dictionary lookup table. We developed a simple and efficient hashing function to perform the string search.

Cheung, Kar-Ming↗

Ground control system for the midcourse space experiment UTC clock

One goal of the Midcourse Space Experiment (MSX) spacecraft Operations Planning Center is to maintain the onboard satellite UTC clock (UTC(MSX)) to within 1 millisecond of UTC(APL) (the program requirement is 10 msec). The UTC(MSX) clock employs as its time base an APL built 5 MHz quartz oscillator, which is expected to have frequency instabilities (aging rate + drift rate + frequency offset) that will cause the clock to drift approximately two to ten milliseconds per day. The UTC(MSX) clock can be advanced or retarded by the APL MSX satellite ground control center by integer multiples of 1 millisecond. The MSX Operations Planning Center is developing software which records the drift of UTC(MSX) relative to UTC(APL) and which schedules the time of day and magnitude of UTC(MSX) clock updates up to 48 hours in advance. Because of the manner in which MSX spacecraft activities are scheduled, MSX clock updates are planned 24 to 48 hours in advance, and stored in the satellite's computer controller for later execution. Data will be collected on the drift of UTC(MSX) relative to UTC(APL) over a three to five day period. Approximately six times per day, the time offset between UTC(MSX) and UTC(APL) will be measured by APL with a resolution of less than 100 microseconds. From this data a second order analytical model of the clock's drift will be derived. This model will be used to extrapolate the offset of the MSX clock in time from the present to 48 hours in the future. MSX clock updates will be placed on the spacecraft's daily schedule whenever the predicted clock offset exceeds 0.5 milliseconds. The paper includes a discussion of how the empirical model of the MSX clock is derived from satellite telemetry data, as well as the algorithm used to schedule MSX clock updates based on the model.

Dragonette, Richard↗

New bounding and decomposition approaches for MILP investment problems: Multi-area transmission and generation planning under policy constraints

A novel two-phase bounding and decomposition approach to compute optimal and near-optimal solutions to large-scale mixed-integer investment planning problems is proposed and it considers a large number of operating subproblems, each of which is a convex optimization. Our motivating application is the planning of power transmission and generation in which policy constraints are designed to incentivize high amounts of intermittent generation in electric power systems. The bounding phase exploits Jensen’s inequality to define a lower bound, which we extend to stochastic programs that use expected-value constraints to enforce policy objectives. The decomposition phase, in which the bounds are tightened, improves upon the standard Benders’ algorithm by accelerating the convergence of the bounds. The lower bound is tightened by using a Jensen’s inequality-based approach to introduce an auxiliary lower bound into the Benders master problem. Upper bounds for both phases are computed using a sub-sampling approach executed on a parallel computer system. Numerical results show that only the bounding phase is necessary if loose optimality gaps are acceptable. But, the decomposition phase is required to attain optimality gaps. Moreover, use of both phases performs better, in terms of convergence speed, than attempting to solve the problem using just the bounding phase or regular Benders decomposition separately.

97 MATHEMATICS AND COMPUTING↗

Conservative Patch Algorithm and Mesh Sequencing for PAB3D

A mesh-sequencing algorithm and a conservative patched-grid-interface algorithm (hereafter Patch Algorithm ) have been incorporated into the PAB3D code, which is a computer program that solves the Navier-Stokes equations for the simulation of subsonic, transonic, or supersonic flows surrounding an aircraft or other complex aerodynamic shapes. These algorithms are efficient, flexible, and have added tremendously to the capabilities of PAB3D. The mesh-sequencing algorithm makes it possible to perform preliminary computations using only a fraction of the grid cells (provided the original cell count is divisible by an integer) along any grid coordinate axis, independently of the other axes. The patch algorithm addresses another critical need in multi-block grid situation where the cell faces of adjacent grid blocks may not coincide, leading to errors in calculating fluxes of conserved physical quantities across interfaces between the blocks. The patch algorithm, based on the Stokes integral formulation of the applicable conservation laws, effectively matches each of the interfacial cells on one side of the block interface to the corresponding fractional cell area pieces on the other side. This approach is comprehensive and unified such that all interface topology is automatically processed without user intervention. This algorithm is implemented in a preprocessing code that creates a cell-by-cell database that will maintain flux conservation at any level of full or reduced grid density as the user may choose by way of the mesh-sequencing algorithm. These two algorithms have enhanced the numerical accuracy of the code, reduced the time and effort for grid preprocessing, and provided users with the flexibility of performing computations at any desired full or reduced grid resolution to suit their specific computational requirements.

Pao, S. P.↗

Investigation of correlation classification techniques

A two-step classification algorithm for processing multispectral scanner data was developed and tested. The first step is a single pass clustering algorithm that assigns each pixel, based on its spectral signature, to a particular cluster. The output of that step is a cluster tape in which a single integer is associated with each pixel. The cluster tape is used as the input to the second step, where ground truth information is used to classify each cluster using an iterative method of potentials. Once the clusters have been assigned to classes the cluster tape is read pixel-by-pixel and an output tape is produced in which each pixel is assigned to its proper class. In addition to the digital classification programs, a method of using correlation clustering to process multispectral scanner data in real time by means of an interactive color video display is also described.

Haskell, R. E.↗

A digital algorithm for spectral deconvolution with noise filtering and peak picking: NOFIPP-DECON

Noise-filtering, peak-picking deconvolution software incorporates multiple convoluted convolute integers and multiparameter optimization pattern search. The two theories are described and three aspects of the software package are discussed in detail. Noise-filtering deconvolution was applied to a number of experimental cases ranging from noisy, nondispersive X-ray analyzer data to very noisy photoelectric polarimeter data. Comparisons were made with published infrared data, and a man-machine interactive language has evolved for assisting in very difficult cases. A modified version of the program is being used for routine preprocessing of mass spectral and gas chromatographic data.

Edwards, T. R.↗

Seismic Retrofit for Electric Power Systems

Our paper develops a two-stage stochastic program and solution procedure to optimize the selection of seismic retrofit strategies to increase the resilience of electric power systems against earthquake hazards. The model explicitly considers the range of earthquake events that are possible and, for each, an approximation of the distribution of damage experienced. Furthermore, this is important because electric power systems are spatially distributed and so their performance is driven by the distribution of component damage. We also test this solution procedure against the nonlinear integer solver in LINGO 13 and apply the formulation and solution strategy to the Eastern Interconnection, where seismic hazard stems from the New Madrid seismic zone.

58 GEOSCIENCES↗

Subroutines For Image Processing

Image Processing Library computer program, IPLIB, is collection of subroutines facilitating use of COMTAL image-processing system driven by HP 1000 computer. Functions include addition or subtraction of two images with or without scaling, display of color or monochrome images, digitization of image from television camera, display of test pattern, manipulation of bits, and clearing of screen. Provides capability to read or write points, lines, and pixels from image; read or write at location of cursor; and read or write array of integers into COMTAL memory. Written in FORTRAN 77.

Faulcon, Nettie D.↗

ZONAL TOROIDAL HARMONIC EXPANSIONS OF EXTERNAL GRAVITATIONAL FIELDS FOR RING-LIKE OBJECTS

We present an expression of the external gravitational field of a general ring-like object with axial and plane symmetries such as oval toroids or annular disks with an arbitrary density distribution. The main term is the gravitational field of a uniform, infinitely thin ring representing the limit of zero radial width and zero vertical height of the object. The additional term is derived from a zonal toroidal harmonic expansion of a general solution of Laplace’s equation outside the Brillouin toroid of the object. The special functions required are the point value and the first-order derivative of the zonal toroidal harmonics of the first kind, namely, the Legendre function of the first kind of half integer degree and an argument that is not less than unity. We developed a recursive method to compute them from two pairs of seed values explicitly expressed by some complete elliptic integrals. Numerical experiments show that appropriately truncated expansions converge rapidly outside the Brillouin toroid. The truncated expansion can be evaluated so efficiently that, for an oval toroid with an exponentially damping density profile, it is 3000–10,000 times faster than the two-dimensional numerical quadrature. A group of the Fortran 90 programs required in the new method and their sample outputs are available electronically.

79 ASTRONOMY AND ASTROPHYSICS↗

Mesh2d

Mesh2d is a Fortran90 program designed to generate two-dimensional structured grids of the form [x(i),y(i,j)] where [x,y] are grid coordinates identified by indices (i,j). The x(i) coordinates alone can be used to specify a one-dimensional grid. Because the x-coordinates vary only with the i index, a two-dimensional grid is composed in part of straight vertical lines. However, the nominally horizontal y(i,j0) coordinates along index i are permitted to undulate or otherwise vary. Mesh2d also assigns an integer material type to each grid cell, mtyp(i,j), in a user-specified manner. The complete grid is specified through three separate input files defining the x(i), y(i,j), and mtyp(i,j) variations.

Smith, Frank↗

Mesh2d Grid Generator Design and Use

Mesh2d is a Fortran90 program designed to generate two-dimensional structured grids of the form [x(i),y(i,j)] where [x,y] are grid coordinates identified by indices (i,j). The x(i) coordinates alone can be used to specify a one-dimensional grid. Because the x-coordinates vary only with the i index, a two-dimensional grid is composed in part of straight vertical lines. However, the nominally horizontal y(i,j 0 ) coordinates along index i are permitted to undulate or otherwise vary. Mesh2d also assigns an integer material type to each grid cell, mtyp(i,j), in a user-specified manner. The complete grid is specified through three separate input files defining the x(i), y(i,j), and mtyp(i,j) variations. The overall mesh is constructed from grid zones that are typically then subdivided into a collection of smaller grid cells. The grid zones usually correspond to distinct materials or larger-scale geometric shapes. The structured grid zones are identified through uppercase indices (I,J). Subdivision of zonal regions into grid cells can be done uniformly, or nonuniformly using either a polynomial or geometric skewing algorithm. Grid cells may be concentrated backward, forward, or toward both ends. Figure 1 illustrates the above concepts in the context of a simple four zone grid.

97 MATHEMATICS AND COMPUTING↗

WORM (Write One, Read Many)

WORM (Write One, Run Many) is an easy to use, cross platform, embedded and extensible, functional programming language designed to facilitate the creation of input-decks for computer codes that use standard ASCII text files for input. WORM makes it easy to create generic (yet, complex and powerful) reusable models. Additionally its nature allows for complex calculations and routines to be coded once and easily reused, further simplifying the creation of input decks. WORM (Write One, Run Many) is a powerful and versatile tool designed to improve the efficiency of today’s criticality safety analyst by allowing: + input decks for parametric studies to be created quickly and easily, + calculations and variables to be imbedded into any input deck, thus allowing for meaningful parameter specifications, + problems to be specified using any combination of units, and + complex mathematically defined models to be created. A very simple syntax is employed, and therefore the WORM is easy to learn. A WORM model is essentially a standard input deck with some of its numerical values replaced by WORM code. WORM code may include and evaluate the following mathematical operators and functions: addition, subtraction, multiplication, division, exponentiation, modulus, sine, cosine, tangent, arcsine, arccosine, arctangent, the natural logarithm, logarithm base 10, integer truncation, absolute value, and random number. Several common constants, e.g., pi, e, and Avogadros’s Number (both as 6.022e23 and 0.6022), are predefined in WORM. Additionally, many unit conversion factors are also predefined: millimeters, meters, inches, feet, yards, and mils to centimeters; kilograms, pounds, and ounces to grams; liters, milliliters, gallons, and fluid ounces to cubic centimeters; and angular degrees to radians. For parametric studies, WORM supports various shorthand list specifications: the explicit step size, linear interpolation, and logarithmic interpolation. The list notation sequentially assigns multiple values to a name. WORM creates an input deck for each value of the name. If multiple lists are used, WORM steps through each list individually, i.e., WORM creates input decks corresponding to each and every permutation of the list values. Additionally, a library of standard material definitions and Perl subroutines are included. Any one of these files can be incorporated into the subject model with a simple WORM read command. WORM is completely written in Perl, the Practical Extraction and Reporting Language. Perl is one of the most portable programming languages available today. As such, the WORM works on practically any computer platform.

Sartor, Raymond↗

Toplogical optimization of structures using Fourier representations

The minimization of compliance subject to a mass constraint is the topology optimization design problem of interest. The goal is to determine the optimal configuration of material within an allowed volume. Our approach builds upon the well-known density method in which the decision variable is the material density in every cell in a mesh. In it’s most basic form the density method consists of three steps: 1) the problem is convexified by replacing the integer material indicator function with a volume fraction, 2) the problem is regularized by filtering the volume fraction field to impose a minimum length scale; 3) the filtered volume fraction is penalized to steer the material distribution toward binary designs. The filtering step is used to yield a mesh-independent solution and to eliminate checkerboard instabilities. In image processing terms this is a low-pass filter, and a consequence is that the decision variables are not independent and a change of basis could significantly reduce the dimension of the nonlinear programming problem. Based on this observation, we represent the volume fraction field with a truncated Fourier representation. Furthermore, this imposes a minimal length scale on the problem, eliminates checkerboard instabilities, and also reduces the number of decision variables by over 100 × (two dimensions) or 1000 × (three dimensions).

97 MATHEMATICS AND COMPUTING↗

Implementation of a New DTSTEP Algorithm for use in RELAP5-3D and PVMEXEC Completion Report

The PVM Coupling methodology for decomposing a complex model into domains onto which individual programs may be applied has proven effective for solving many multi-physics problems. There have been, from the outset, some detailed and/or long-running models that cause the process to fail. This project addressed the PVM coupling issues surrounding the DTSTEP subroutines on RELAP5-3D and PVMEXEC. Some 25 errors are listed in Tables 1 and 18 and in Section 11. These arise from deficiencies in the floating point calculation and testing of time steps, cumulative time, and time targets. The algorithmic replacement of floating point control of these items with integer based timestepping was developed and implemented. The result of the first phase, undertaken by the INL was that all but three of these issues were resolved. Moreover, two conceptual errors in DTSTEP that were not PVM coupling related were discovered and solved. The final, and most difficult three PVM Bettis User Problems, were solved during the Bettis phase of development and debugging. In 8 months since the conclusion of the project, no further DTSTEP related PVM Coupling errors have been reported.

97 MATHEMATICS AND COMPUTING↗

The impact of short-term stochastic variability in solar irradiance on optimal microgrid design

This paper proposes a new methodology to capture the impact of fast moving clouds on utility power demand charges observed in microgrids with photovoltaic (PV) arrays, generators, and electrochemical energy storage. It consists of a statistical approach to introduce sub-hourly events in the hourly economic accounting process. The methodology is implemented in the Distributed Energy Resources Customer Adoption Model (DER-CAM), a state of the art mixed integer linear model used to optimally size DER in decentralized energy systems. Results suggest that previous iterations of DER-CAM could undersize battery capacities. The improved model depicts more accurately the economic value of PV as well as the synergistic benefits of pairing PV with storage.

24 POWER TRANSMISSION AND DISTRIBUTION↗

A Hierarchical Approach to Fracture Mechanics

Recent research conducted under NASA LaRC's Creativity and Innovation Program has led to the development of an initial approach for a hierarchical fracture mechanics. This methodology unites failure mechanisms occurring at different length scales and provides a framework for a physics-based theory of fracture. At the nanoscale, parametric molecular dynamic simulations are used to compute the energy associated with atomic level failure mechanisms. This information is used in a mesoscale percolation model of defect coalescence to obtain statistics of fracture paths and energies through Monte Carlo simulations. The mathematical structure of predicted crack paths is described using concepts of fractal geometry. The non-integer fractal dimension relates geometric and energy measures between meso- and macroscales. For illustration, a fractal-based continuum strain energy release rate is derived for inter- and transgranular fracture in polycrystalline metals.

Saether, Erik↗

Preliminary results of the 2023 International Fermilab Booster Studies

Here, an overview is given of the methods and preliminary results from dedicated beam studies on three topics conducted over five days in July 2023. In the first study, the Fermilab Booster magnets were held constant at magnetic fields corresponding to the injection energy. The beam loss and emittance growth were observed under varying intensity, tunes, and sextupole resonances. The corresponding beam conditions were also simulated with the MADX-SC code [1]. In the second study, measurements of the vertical half-integer resonance and correction methods are conducted for high-intensity beams ramping in the Booster. Finally, syncho-betatron instabilities are observed during transition-crossing in the Booster under strong space-charge conditions.

43 PARTICLE ACCELERATORS↗

Virtual Machine Language 2.1

VML (Virtual Machine Language) is an advanced computing environment that allows spacecraft to operate using mechanisms ranging from simple, time-oriented sequencing to advanced, multicomponent reactive systems. VML has developed in four evolutionary stages. VML 0 is a core execution capability providing multi-threaded command execution, integer data types, and rudimentary branching. VML 1 added named parameterized procedures, extensive polymorphism, data typing, branching, looping issuance of commands using run-time parameters, and named global variables. VML 2 added for loops, data verification, telemetry reaction, and an open flight adaptation architecture. VML 2.1 contains major advances in control flow capabilities for executable state machines. On the resource requirements front, VML 2.1 features a reduced memory footprint in order to fit more capability into modestly sized flight processors, and endian-neutral data access for compatibility with Intel little-endian processors. Sequence packaging has been improved with object-oriented programming constructs and the use of implicit (rather than explicit) time tags on statements. Sequence event detection has been significantly enhanced with multi-variable waiting, which allows a sequence to detect and react to conditions defined by complex expressions with multiple global variables. This multi-variable waiting serves as the basis for implementing parallel rule checking, which in turn, makes possible executable state machines. The new state machine feature in VML 2.1 allows the creation of sophisticated autonomous reactive systems without the need to develop expensive flight software. Users specify named states and transitions, along with the truth conditions required, before taking transitions. Transitions with the same signal name allow separate state machines to coordinate actions: the conditions distributed across all state machines necessary to arm a particular signal are evaluated, and once found true, that signal is raised. The selected signal then causes all identically named transitions in all present state machines to be taken simultaneously. VML 2.1 has relevance to all potential space missions, both manned and unmanned. It was under consideration for use on Orion.

Riedel, Joseph E.↗