Mixed integer programming algorithms for site selection and other fixed charge problems having capacity constraints
Mixed integer programming algorithms for site selection and other fixed charge problems having capacity constraints
SEARCH · Engineering Papers
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.
Mixed integer programming algorithms for site selection and other fixed charge problems having capacity constraints
A parallelization of the k-means++ seed selection algorithm on three distinct hardware platforms: GPU, multicore CPU, and multithreaded architecture. K-means++ was developed by David Arthur and Sergei Vassilvitskii in 2007 as an extension of the k-means data clustering technique. These algorithms allow people to cluster multidimensional data, by attempting to minimize the mean distance of data points within a cluster. K-means++ improved upon traditional k-means by using a more intelligent approach to selecting the initial seeds for the clustering process. While k-means++ has become a popular alternative to traditional k-means clustering, little work has been done to parallelize this technique. We have developed original C++ code for parallelizing the algorithm on three unique hardware architectures: GPU using NVidia's CUDA/Thrust framework, multicore CPU using OpenMP, and the Cray XMT multithreaded architecture. By parallelizing the process for these platforms, we are able to perform k-means++ clustering much more quickly than it could be done before.
A genetic algorithm is used to select the inputs to a neural network function approximator. In the application considered, modeling critical parameters of the space shuttle main engine (SSME), the functional relationship between measured parameters is unknown and complex. Furthermore, the number of possible input parameters is quite large. Many approaches have been used for input selection, but they are either subjective or do not consider the complex multivariate relationships between parameters. Due to the optimization and space searching capabilities of genetic algorithms they were employed to systematize the input selection process. The results suggest that the genetic algorithm can generate parameter lists of high quality without the explicit use of problem domain knowledge. Suggestions for improving the performance of the input selection process are also provided.
ABSTRACT We present a systematic study of the impact of a dust bias on samples of damped Ly α absorbers (DLAs). This bias arises as an effect of the magnitude and colour criteria utilized in the Sloan Digital Sky Survey (SDSS) quasar target selection up until data release 7 (DR7). The bias has previously been quantified assuming only a contribution from the dust obscuration. In this work, we apply the full set of magnitude and colour criteria used up until SDSS-DR7 in order to quantify the full impact of dust biasing against dusty and metal-rich DLAs. We apply the quasar target selection algorithm on a modelled population of intrinsic colours, and by exploring the parameter space consisting of redshift, ($z_{\rm{\small QSO}}$and zabs), optical extinction, and H i column density, we demonstrate how the selection probability depends on these variables. We quantify the dust bias on the following properties derived for DLAs at z ≈ 3: the incidence rate, the mass density of neutral hydrogen and metals, and the average metallicity. We find that all quantities are significantly affected. When considering all uncertainties, the mass density of neutral hydrogen is underestimated by 10–50 per cent, and the mass density in metals is underestimated by 30–200 per cent. Lastly, we find that the bias depends on redshift. At redshift z = 2.2, the mass density of neutral hydrogen and metals might be underestimated by up to a factor of 2 and 5, respectively. Characterizing such a bias is crucial in order to accurately interpret and model the properties and metallicity evolution of absorption-selected galaxies.
Experimental processes, analytical methods, and numerical algorithms are described that may be used to predict the forces and moments of an internal strain-gage balance during a wind tunnel test. First, the control volume model of a strain-gage balance and the concepts of load state, load space, and output space are introduced. These important abstractions provide a better understanding of fundamental characteristics of different balance load prediction approaches. Then, the description of strain-gage balance data and the definition of the primary gage sensitivity is discussed. Afterwards, basic elements of the calibration of a typical six-component balance are reviewed. Two fundamentally different balance load prediction methods, the processing of check loads, and related topics are also discussed. Three real-world balance data examples are reviewed in great detail to illustrate typical analysis results for a variety of strain-gage balance designs. Finally, important observations are summarized and recommendations are provided. Additional information and detailed mathematical derivations can be found in the appendices of the document. They include the following topics: balance terminology, definitions of important statistical metrics, balance axis system conventions, balance load transformations, the combined load diagram, electrical output format options, bi-directional gage output characteristics, determination of the natural zeros, derivation of two balance load prediction methods, description of two tare load iteration algorithms, modeling of balance temperature effects, basics of three-component moment balances, definition of the percent contribution, detection of linear and near-linear dependencies in balance calibration data, a regression model term selection algorithm, and other related topics.
This paper focuses on the work being performed at the NASA Marshall Space Flight Center (MSFC) in support of Mars Ascent Vehicles (MAVs). Specifically, the analysis presented is in support of Martian sample return architectures. In or-der to assess vehicle sensitivities, a detailed simulation tool, (MAV Analysis Tool in Simscape) MANTIS, was implemented using the MATLAB/Simulink Sim-scape architecture. High fidelity navigation sensor models and guidance algorithms were included in order to facilitate sensor requirement development and flight algorithm selection. This work focuses on the performance of the integrated system and the coupling of navigation and guidance capabilities. The architecture trades are heavily dependent on the ascent flight profile chosen. This work assesses both open- and closed-loop guidance algorithms to capture their relative performance and the resulting requirements on sensor capability to support preliminary vehicle design. The analysis builds on previous work that focused on navigation performance for initialization and ascent flight of crewed vehicle. The results provide insight into the coupling between sensor requirements and ascent guidance approach. The analysis provides data to support requirements for hard-ware selection and testing. Additional discussion is also included focusing on other system constraints that affect hardware selection and operational constraints.
Purpose: To assess dosimetric differences in IMRT lung stereotactic body radiotherapy (SBRT) plans calculated with Varian AAA and Acuros (AXB) and with vendor-supplied (V) versus in-house (IH) measured Hounsfield units (HU) to mass and HU to electron density conversion tables. Methods: In-house conversion tables were measured using Gammex 472 density-plug phantom. IMRT plans (6 MV, Varian TrueBeam, 6–9 coplanar fields) meeting departmental coverage and normal tissue constraints were retrospectively generated for 10 lung SBRT cases using Eclipse Vn 10.0.28 AAA with in-house tables (AAA/IH). Using these monitor units and MLC sequences, plans were recalculated with AAA and vendor tables (AAA/V) and with AXB with both tables (AXB/IH and AXB/V). Ratios to corresponding AAA/IH values were calculated for PTV D95, D01, D99, mean-dose, total and ipsilateral lung V20 and chestwall V30. Statistical significance of differences was judged by Wilcoxon Signed Rank Test (p<0.05). Results: For HU<−400 the vendor HU-mass density table was notably below the IH table. PTV D95 ratios to AAA/IH, averaged over all patients, are 0.963±0.073 (p=0.508), 0.914±0.126 (p=0.011), and 0.998±0.001 (p=0.005) for AXB/IH, AXB/V and AAA/V respectively. Total lung V20 ratios are 1.006±0.046 (p=0.386), 0.975±0.080 (p=0.514) and 0.998±0.002 (p=0.007); ipsilateral lung V20 ratios are 1.008±0.041(p=0.284), 0.977±0.076 (p=0.443), and 0.998±0.018 (p=0.005) for AXB/IH, AXB/V and AAA/V respectively. In 7 cases, ratios to AAA/IH were within ± 5% for all indices studied. For 3 cases characterized by very low lung density and small PTV (19.99±8.09 c.c.), PTV D95 ratio for AXB/V ranged from 67.4% to 85.9%, AXB/IH D95 ratio ranged from 81.6% to 93.4%; there were large differences in other studied indices. Conclusion: For AXB users, careful attention to HU conversion tables is important, as they can significantly impact AXB (but not AAA) lung SBRT plans. Algorithm selection is also important for small targets in low density lung.
The Dark Energy Spectroscopic Instrument (DESI) cosmology survey includes a Bright Galaxy Survey (BGS), which will yield spectra for over 10 million bright galaxies (r < 20.2 AB mag). The resulting sample will be valuable for both cosmological and astrophysical studies. However, the star/galaxy separation criterion implemented in the nominal BGS target selection algorithm excludes quasar host galaxies in addition to bona fide stars. While this excluded population is comparatively rare (∼3–4 per square degrees), it may hold interesting clues regarding galaxy and quasar physics. Therefore, we present a target selection strategy that was implemented to recover these missing active galactic nuclei (AGN) from the BGS sample. The design of the selection criteria was both motivated and confirmed using spectroscopy. The resulting BGS-AGN sample is uniformly distributed over the entire DESI footprint. According to DESI survey validation data, the sample comprises 93% quasi-stellar objects (QSOs), 3% narrow-line AGN or blazars with a galaxy contamination rate of 2%, and a stellar contamination rate of 2%. Peaking around redshift z = 0.5, the BGS-AGN sample is intermediary between quasars from the rest of the BGS and those from the DESI QSO sample in terms of redshifts and AGN luminosities. The stacked spectrum is nearly identical to that of the DESI QSO targets, confirming that the sample is dominated by quasars. We highlight interesting small populations reaching z > 2, which are either faint quasars with nearby projected companions or very bright quasars with strong absorption features including the Lyα forest, metal absorbers, and/or broad absorption lines.
NASA’s Safe and Precise Landing Integrated Capabilities Evolution (SPLICE) project is developing sensor, algorithm, and compute technologies for precision landing and hazard avoidance. These technologies are being tested as an integrated Precision Landing and Hazard Avoidance (PL&HA) system on Blue Origin’s New Shephard suborbital vehicle. A key goal for the computing element of this technology development is to characterize the performance of the SPLICE software workloads on the project’s Descent and Landing Computer (DLC). The DLC is a multi-core processor designed as a surrogate for NASA’s High-Performance Space Computer (HPSC). Measurements of the SPLICE workload performance on the DLC provides NASA insight on how PL&HA capabilities will perform on the HPSC, and guidance on how the SPLICE algorithms can be implemented to best utilize the DLC platform. This insight can also be used to derive requirements to guide trade studies on candidate computing architectures, for use on platforms like Blue Moon. NASA and Blue Origin are collaborating under an agreement to pursue this mutual benefit. Performance metrics collected are based on measurement of common compute resources such as percentage used of memory bandwidth, I/O utilization, interrupt latency, and kernel vs. user space code residency. Where possible existing performance counters and metrics that are part of the operating system kernel are used. As the design has a significant FPGA component, performance counters are identified and instantiated in the fabric to measure DMA performance and interface metrics. Collection of metrics is performed on the DLC with a representative workload that simulates a full landing cycle of the Blue Origin New Shepard vehicle. Consideration is given to the other compute implementations and whether they can run SPLICE algorithms at the same rate and with the same latency as the DLC. One option being considered is the use of a RISC-V soft core instantiated in a radiation resilient FPGA fabric such as the Xilinx KU60. Select algorithms from the SPLICE code will be run for comparison with the DLC. This paper describes how the DLC is instrumented to collect performance measurements of the SPLICE workloads, preliminary results from these measurements, and their implications on SPLICE algorithm implementation. The results of experimentation to derive candidate requirements for architecture trades on a PL&HA computing system are also presented.
The integration of renewable energy sources such as solar PVs into micro grids has increased in recent years. However, the intermittent and unpredictable nature of renewable energy generation makes supply uncertain, in turn requiring continuous net load balancing to ensure grid stability. One technique to achieve net load balancing is curtailment, however, selection of the optimal set of curtailment strategies to achieve a targeted curtailment is NP-hard. State-of-the-art curtailment selection techniques approach this problem by either developing computationally expensive optimal curtailment strategies or reduce accuracy to generate sub-optimal solutions quickly. In this work, we develop NO-LESS: a Near OptimaL CurtailmEnt Strategy Selection algorithm. NO-LESS is a novel Fully Polynomial Time Approximation Scheme (FPTAS) which determines bounded (near optimal) curtailment strategies in a small amount of time while simultaneously satisfying practical constraints on strategy switching overhead and curtailment fairness. We perform both theoretical analysis and practical evaluation to show that NO-LESS is a scalable solution for performing net load balancing through curtailment strategy selection in Micro Grids.
Reflecting the two tasks proposed for the current year, namely a feasibility study of simulating the NASA network, and a study of progressive transmission schemes, are presented. The view of the NASA network, gleaned from the various technical reports made available to use, is provided. Also included is a brief overview of how the current simulator could be modified to accomplish the goal of simulating the NASA network. As the material in this section would be the basis for the actual simulation, it is important to make sure that it is an accurate reflection of the requirements on the simulator. Brief descriptions of the set of progressive transmission algorithms selected for the study are contained. The results available in the literature were obtained under a variety of different assumptions, not all of which are stated. As such, the only way to compare the efficiency and the implementational complexity of the various algorithms is to simulate them.
We investigate machine learning (ML) techniques for predicting the number of galaxies (N{sub gal}) that occupy a halo, given the halo's properties. These types of mappings are crucial for constructing the mock galaxy catalogs necessary for analyses of large-scale structure. The ML techniques proposed here distinguish themselves from traditional halo occupation distribution (HOD) modeling as they do not assume a prescribed relationship between halo properties and N{sub gal}. In addition, our ML approaches are only dependent on parent halo properties (like HOD methods), which are advantageous over subhalo-based approaches as identifying subhalos correctly is difficult. We test two algorithms: support vector machines (SVM) and k-nearest-neighbor (kNN) regression. We take galaxies and halos from the Millennium simulation and predict N{sub gal} by training our algorithms on the following six halo properties: number of particles, M{sub 200}, {sigma}{sub v}, v{sub max}, half-mass radius, and spin. For Millennium, our predicted N{sub gal} values have a mean-squared error (MSE) of {approx}0.16 for both SVM and kNN. Our predictions match the overall distribution of halos reasonably well and the galaxy correlation function at large scales to {approx}5%-10%. In addition, we demonstrate a feature selection algorithm to isolate the halo parameters that are most predictive, a useful technique for understanding the mapping between halo properties and N{sub gal}. Lastly, we investigate these ML-based approaches in making mock catalogs for different galaxy subpopulations (e.g., blue, red, high M{sub star}, low M{sub star}). Given its non-parametric nature as well as its powerful predictive and feature selection capabilities, ML offers an interesting alternative for creating mock catalogs.
An enhanced Finite Control Set Model Predictive Control (FCS-MPC) strategy with a two-step prediction horizon for a Doubly-Fed Induction Generator (DFIG) is the focus of this paper. The DFIG and RL filter's discrete-time model is used in the proposed control scheme for a two-step prediction horizon of rotor and filter currents for the converter's eight possible switching states. Afterward, the control algorithm selects the ideal switching state, which minimizes currents' objective function. The proposed control scheme does not require a modulation stage for internal controllers. We use Lagrange extrapolations to predict the dynamic changes in currents. The switching frequency reduction is achieved by integrating an optimization constraint in the algorithm's cost function. Furthermore, the Total Harmonic Distortion level of currents is kept below 5%, according to IEEE Std 519-14. Obtained results reveal that the switching frequency of the DFIG converters is considerably reduced without losing control; it is reduced by 13.89KHz for the Grid Side Converter (GSC) and by 1.78KHz for the Rotor Side Converter (RSC).
The accuracy of the Ibrahim time Domain (ITD) identification algorithm in extracting structural model parameters from free response functions was studied using computer simulated data for 65 positions on an isotropic, uniform thickness plate with mode shapes obtained by NASTRAN analysis. Natural frequencies were used to study identification results over ranges of modal parameter values and user selectable algorithm constants. Effects of superimposing various levels of noise onto the functions were investigated. No detrimental effects were observed when the number of computational degrees of freedom allowed in the algorithm was made many times larger than the minimum necessary for adequate identification. The use of a high number of degrees of freedom when analyzing experimental data, for the simultaneous identification of many modes in one computer run are suggested.
We present the selection algorithm and anticipated results for the Time Domain Spectroscopic Survey (TDSS). TDSS is an Sloan Digital Sky Survey (SDSS)-IV Extended Baryon Oscillation Spectroscopic Survey (eBOSS) subproject that will provide initial identification spectra of approximately 220,000 luminosity-variable objects (variable stars and active galactic nuclei across 7500 deg{sup 2} selected from a combination of SDSS and multi-epoch Pan-STARRS1 photometry. TDSS will be the largest spectroscopic survey to explicitly target variable objects, avoiding pre-selection on the basis of colors or detailed modeling of specific variability characteristics. Kernel Density Estimate analysis of our target population performed on SDSS Stripe 82 data suggests our target sample will be 95% pure (meaning 95% of objects we select have genuine luminosity variability of a few magnitudes or more). Our final spectroscopic sample will contain roughly 135,000 quasars and 85,000 stellar variables, approximately 4000 of which will be RR Lyrae stars which may be used as outer Milky Way probes. The variability-selected quasar population has a smoother redshift distribution than a color-selected sample, and variability measurements similar to those we develop here may be used to make more uniform quasar samples in large surveys. The stellar variable targets are distributed fairly uniformly across color space, indicating that TDSS will obtain spectra for a wide variety of stellar variables including pulsating variables, stars with significant chromospheric activity, cataclysmic variables, and eclipsing binaries. TDSS will serve as a pathfinder mission to identify and characterize the multitude of variable objects that will be detected photometrically in even larger variability surveys such as Large Synoptic Survey Telescope.
Enzyme and metabolic engineering offer the potential to develop biocatalysts for converting natural resources to a wide range of chemicals. To broaden the scope of potential products beyond natural metabolites, methods of engineering enzymes to accept alternative substrates and/or perform novel chemistries must be developed. DNA synthesis can create large libraries of enzyme-coding sequences, but most biochemistries lack a simple assay to screen for promising enzyme variants. Our solution to this challenge is structure-guided mutagenesis, in which optimization algorithms select the best sequences from libraries based on specified criteria (i.e., binding selectivity). We demonstrate this approach by identifying medium-chain (C8–C12) acyl-ACP thioesterases through structure-guided mutagenesis. Medium-chain fatty acids, which are products of thioesterase-catalyzed hydrolysis, are limited in natural abundance, compared to long-chain fatty acids; the limited supply leads to high costs of C6–C10 oleochemicals such as fatty alcohols, amines, and esters. Here, we applied computational tools to tune substrate binding of the highly active ‘TesA thioesterase in Escherichia coli. We used the IPRO algorithm to design thioesterase variants with enhanced C12 or C8 specificity, while maintaining high activity. After four rounds of structure-guided mutagenesis, we identified 3 variants with enhanced production of dodecanoic acid (C12) and 27 variants with enhanced production of octanoic acid (C8). The top variants reached up to 49% C12 and 50% C8 while exceeding native levels of total free fatty acids. A comparably sized library created by random mutagenesis failed to identify promising mutants. The chain length-preference of ‘TesA and the best mutant were confirmed in vitro using acyl-CoA substrates. Molecular dynamics simulations, confirmed by resolved crystal structures, of ‘TesA variants suggest that hydrophobic forces govern ‘TesA substrate specificity. Finally, we expect the design rules that we uncovered and the thioesterase variants that we identified will be useful to metabolic engineering projects aimed at sustainable production of medium-chain-length oleochemicals.
The present status of numerical methods for partial differential equations on vector and parallel computers was reviewed. The relevant aspects of these computers are discussed and a brief review of their development is included, with particular attention paid to those characteristics that influence algorithm selection. Both direct and iterative methods are given for elliptic equations as well as explicit and implicit methods for initial boundary value problems. The intent is to point out attractive methods as well as areas where this class of computer architecture cannot be fully utilized because of either hardware restrictions or the lack of adequate algorithms. Application areas utilizing these computers are briefly discussed.
The present status of numerical methods for partial differential equations on vector and parallel computers was reviewed. The relevant aspects of these computers are discussed and a brief review of their development is included, with particular attention paid to those characteristics that influence algorithm selection. Both direct and iterative methods are given for elliptic equations as well as explicit and implicit methods for initial boundary value problems. The intent is to point out attractive methods as well as areas where this class of computer architecture cannot be fully utilized because of either hardware restrictions or the lack of adequate algorithms. Application areas utilizing these computers are briefly discussed.