Search NASA⌕ Search

SEARCH · Search NASA

Results for “combinatorial optimization problem”

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 181 records · Page 10

Short communication : a linear assignment approach for the least-squares protein morphing problem.

This work addresses the computation of free-energy differences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morphing procedure, we employ permutations of atoms: we seek to find the permutation s that minimizes the mean-square distance traveled by the atoms. Instead of performing this combinatorial search in the space of permutations, we show that the best permutation can be found by solving a linear assignment problem. We demonstrate that the use of such optimal permutations significantly improves the efficiency of the free-energy computation.

59 BASIC BIOLOGICAL SCIENCES↗

Optimization strategies for the vulnerability analysis of the electric power grid.

Identifying small groups of lines, whose removal would cause a severe blackout, is critical for the secure operation of the electric power grid. We show how power grid vulnerability analysis can be studied as a mixed integer nonlinear programming (minlp) problem. Our analysis reveals a special structure in the formulation that can be exploited to avoid nonlinearity and approximate the original problem as a pure combinatorial problem. The key new observation behind our analysis is the correspondence between the Jacobian matrix (a representation of the feasibility boundary of the equations that describe the flow of power in the network) and the Laplacian matrix in spectral graph theory (a representation of the graph of the power grid). The reduced combinatorial problem is known as the network inhibition problem, for which we present a mixed integer linear programming formulation. Our experiments on benchmark power grids show that the reduced combinatorial model provides an accurate approximation, to enable vulnerability analyses of real-sized problems with more than 10,000 power lines.

99 GENERAL AND MISCELLANEOUS↗

Bayesian optimization with active learning of design constraints using an entropy-based approach

Abstract The design of alloys for use in gas turbine engine blades is a complex task that involves balancing multiple objectives and constraints. Candidate alloys must be ductile at room temperature and retain their yield strength at high temperatures, as well as possess low density, high thermal conductivity, narrow solidification range, high solidus temperature, and a small linear thermal expansion coefficient. Traditional Integrated Computational Materials Engineering (ICME) methods are not sufficient for exploring combinatorially-vast alloy design spaces, optimizing for multiple objectives, nor ensuring that multiple constraints are met. In this work, we propose an approach for solving a constrained multi-objective materials design problem over a large composition space, specifically focusing on the Mo-Nb-Ti-V-W system as a representative Multi-Principal Element Alloy (MPEA) for potential use in next-generation gas turbine blades. Our approach is able to learn and adapt to unknown constraints in the design space, making decisions about the best course of action at each stage of the process. As a result, we identify 21 Pareto-optimal alloys that satisfy all constraints. Our proposed framework is significantly more efficient and faster than a brute force approach.

36 MATERIALS SCIENCE↗

Aspects of job scheduling

A mathematical model for job scheduling in a specified context is presented. The model uses both linear programming and combinatorial methods. While designed with a view toward optimization of scheduling of facility and plant operations at the Deep Space Communications Complex, the context is sufficiently general to be widely applicable. The general scheduling problem including options for scheduling objectives is discussed and fundamental parameters identified. Mathematical algorithms for partitioning problems germane to scheduling are presented.

Phillips, K.↗

Fast Solution in Sparse LDA for Binary Classification

An algorithm that performs sparse linear discriminant analysis (Sparse-LDA) finds near-optimal solutions in far less time than the prior art when specialized to binary classification (of 2 classes). Sparse-LDA is a type of feature- or variable- selection problem with numerous applications in statistics, machine learning, computer vision, computational finance, operations research, and bio-informatics. Because of its combinatorial nature, feature- or variable-selection problems are NP-hard or computationally intractable in cases involving more than 30 variables or features. Therefore, one typically seeks approximate solutions by means of greedy search algorithms. The prior Sparse-LDA algorithm was a greedy algorithm that considered the best variable or feature to add/ delete to/ from its subsets in order to maximally discriminate between multiple classes of data. The present algorithm is designed for the special but prevalent case of 2-class or binary classification (e.g. 1 vs. 0, functioning vs. malfunctioning, or change versus no change). The present algorithm provides near-optimal solutions on large real-world datasets having hundreds or even thousands of variables or features (e.g. selecting the fewest wavelength bands in a hyperspectral sensor to do terrain classification) and does so in typical computation times of minutes as compared to days or weeks as taken by the prior art. Sparse LDA requires solving generalized eigenvalue problems for a large number of variable subsets (represented by the submatrices of the input within-class and between-class covariance matrices). In the general (fullrank) case, the amount of computation scales at least cubically with the number of variables and thus the size of the problems that can be solved is limited accordingly. However, in binary classification, the principal eigenvalues can be found using a special analytic formula, without resorting to costly iterative techniques. The present algorithm exploits this analytic form along with the inherent sequential nature of greedy search itself. Together this enables the use of highly-efficient partitioned-matrix-inverse techniques that result in large speedups of computation in both the forward-selection and backward-elimination stages of greedy algorithms in general.

Moghaddam, Baback↗

Online eco-routing for electric vehicles using combinatorial multi-armed bandit with estimated covariance

Identifying energy-efficient routes in real-time has significant implications for the energy-optimal operations of electric vehicles (EVs). Here, this study proposes a novel model for EV online eco-routing problem, which obtains the minimal expected energy consumption paths (MECPs) for multiple origin-destination (OD) pairs simultaneously. Specifically, we formulate the routing problem as a bandit problem and solve it with online algorithms. We extend the algorithms by implementing a path elimination mechanism to reduce the candidate path set and introducing the variance and covariance of the energy consumption to reduce the uncertainties. The numerical results show that the proposed algorithms can efficiently obtain near-optimal MECPs, and the solution is significantly better than the widely used shortest trip time path algorithm (STTP) and shortest trip distance path algorithm (SDP). The variation considering link energy covariance and path elimination generates paths that save 4.1% of energy compared to the SDP and 5.4% to the STTP.

33 ADVANCED PROPULSION SYSTEMS↗

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry. Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space. These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing. We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.

Delay Tolerant Networking↗

SARDA Surface Schedulers

Provide an overview of algorithms used in SARDA (Spot and Runway Departure Advisor) HITL (Human-in-the-Loop) simulation for Dallas Fort-Worth International Airport and Charlotte Douglas International airport. Outline a multi-objective dynamic programming (DP) based algorithm that finds the exact solution to the single runway scheduling (SRS) problem, and discuss heuristics to restrict the search space for the DP based algorithm and provide improvements.

runways scheduling↗

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type Σ x i = k for binary variables x i . Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

97 MATHEMATICS AND COMPUTING↗

Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable non-variational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher order terms using the Julia based QAOA simulation tool \texttt{JuliQAOA} to perform classical angle finding for up to $49$ QAOA layers ($p$). Parameter transfer of the fixed angles is validated using a combination of full statevector, Projected Entangled Pair States (PEPS), Matrix Product State (MPS), and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of $p$ - there are many cases where the performance temporarily decreases as a function of $p$ - but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the $100+$ qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM Quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM NISQ processors up to $p=5$ on \texttt{ibm\_fez}, up to $p=9$ on \texttt{ibm\_torino}, and up to $p=10$ on \texttt{ibm\_pittsburgh}.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

CSRI Summer Proceedings 2021

The Computer Science Research Institute (CSRI) brings university faculty and students to Sandia National Laboratories for focused collaborative research on Department of Energy (DOE) computer and computational science problems. The institute provides an opportunity for university researches to learn about problems in computer and computational science at DOE laboratories, and help transfer results of their research to programs at the labs. Some specific CSRI research interest areas are: scalable solvers, optimization, algebraic preconditioners, graph-based, discrete, and combinatorial algorithms, uncertainty estimation, validation and verification methods, mesh generation, dynamic load-balancing, virus and other malicious-code defense, visualization, scalable cluster computers, beyond Moore’s Law computing, exascale computing tools and application design, reduced order and multiscale modeling, parallel input/output, and theoretical computer science. The CSRI Summer Program is organized by CSRI and includes a weekly seminar series and the publication of a summer proceedings.

97 MATHEMATICS AND COMPUTING↗

CSRI Summer Proceedings 2021

The Computer Science Research Institute (CSRI) brings university faculty and students to Sandia National Laboratories for focused collaborative research on Department of Energy (DOE) computer and computational science problems. The institute provides an opportunity for university researches to learn about problems in computer and computational science at DOE laboratories, and help transfer results of their research to programs at the labs. Some specific CSRI research interest areas are: scalable solvers, optimization, algebraic preconditioners, graph-based, discrete, and combinatorial algorithms, uncertainty estimation, validation and verification methods, mesh generation, dynamic load-balancing, virus and other malicious-code defense, visualization, scalable cluster computers, beyond Moore’s Law computing, exascale computing tools and application design, reduced order and multiscale modeling, parallel input/output, and theoretical computer science. The CSRI Summer Program is organized by CSRI and includes a weekly seminar series and the publication of a summer proceedings.

97 MATHEMATICS AND COMPUTING↗

COHORT: Coordination of Heterogeneous Thermostatically Controlled Loads for Demand Flexibility

Demand flexibility is increasingly important for power grids. Careful coordination of thermostatically controlled loads (TCLs) can modulate energy demand, decrease operating costs, and increase grid resiliency. We propose a novel distributed control framework for the Coordination Of HeterOgeneous Residential Thermostatically controlled loads (COHORT). COHORT is a practical, scalable, and versatile solution that coordinates a population of TCLs to jointly optimize a grid-level objective, while satisfying each TCL’s end-use requirements and operational constraints. To achieve that, we decompose the grid-scale problem into subproblems and coordi- nate their solutions to find the global optimum using the alternating direction method of multipliers (ADMM). The TCLs’ local problems are distributed to and computed in parallel at each TCL, making COHORT highly scalable and privacy-preserving. While each TCL poses combinatorial and non-convex constraints, we characterize these constraints as a convex set through relaxation, thereby making COHORT computationally viable over long planning horizons. After coordination, each TCL is responsible for its own control and tracks the agreed-upon power trajectory with its preferred strategy. In this work, we translate continuous power back to discrete on/off actuation, using pulse width modulation. COHORT is generalizable to a wide range of grid objectives, which we demonstrate through three distinct use cases: generation following, minimizing ramping, and peak load curtailment. In a notable experiment, we validated our approach through a hardware-in-the-loop simulation, including a real-world air conditioner (AC) controlled via a smart thermostat, and simulated instances of ACs modeled after real-world data traces. During the 15-day experimental period, COHORT reduced daily peak loads by an average of 12.5% and maintained comfortable temperatures.

demand response↗

Optimal decision trees for categorical data via integer programming

Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mixed integer programming formulation to construct optimal decision trees of a prespecified size. We take the special structure of categorical features into account and allow combinatorial decisions (based on subsets of values of features) at each node. Our approach can also handle numerical features via thresholding. Here we show that very good accuracy can be achieved with small trees using moderately-sized training sets. The optimization problems we solve are tractable with modern solvers.

97 MATHEMATICS AND COMPUTING↗

Machine Learning Applied to Zeolite Synthesis: The Missing Link for Realizing High-Throughput Discovery

Zeolites are microporous crystalline materials with well-defined cavities and pores, which can be prepared under different pore topologies and chemical compositions. Their preparation is typically defined by multiple interconnected variables (e.g., reagent sources, molar ratios, aging treatments, reaction time and temperature, among others), but unfortunately their distinctive influence, particularly on the nucleation and crystallization processes, is still far from being understood. Thus, the discovery and/or optimization of specific zeolites is closely related to the exploration of the parametric space through trial-and-error methods, generally by studying the influence of each parameter individually. In the past decade, machine learning (ML) methods have rapidly evolved to address complex problems involving highly nonlinear or massively combinatorial processes that conventional approaches cannot solve. Considering the vast and interconnected multiparametric space in zeolite synthesis, coupled with our poor understanding of the mechanisms involved in their nucleation and crystallization, the use of ML is especially timely for improving zeolite synthesis. Indeed, the complex space of zeolite synthesis requires drawing inferences from incomplete and imperfect information, for which ML methods are very well-suited to replace the intuition-based approaches traditionally used to guide experimentation. In this Account, we contend that both existing and new ML approaches can provide the “missing link” needed to complete the traditional zeolite synthesis workflow used in our quest to rationalize zeolite synthesis. Within this context, we have made important efforts on developing ML tools in different critical areas, such as (1) data-mining tools to process the large amount of data generated using high-throughput platforms; (2) novel complex algorithms to predict the formation of energetically stable hypothetical zeolites and guide the synthesis of new zeolite structures; (3) new “ab initio” organic structure directing agent predictions to direct the synthesis of hypothetical or known zeolites; (4) an automated tool for nonsupervised data extraction and classification from published research articles. ML has already revolutionized many areas in materials science by enhancing our ability to map intricate behavior to process variables, especially in the absence of well-understood mechanisms. Undoubtedly, ML is a burgeoning field with many future opportunities for further breakthroughs to advance the design of molecular sieves. For this reason, this Account includes an outlook of future research directions based on current challenges and opportunities. We envision this Account will become a hallmark reference for both well-established and new researchers in the field of zeolite synthesis.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Communication: A new paradigm for structure prediction in multicomponent systems

We analyse the combinatorial aspect of global optimisation for multicomponent systems, which involves searching for the optimal chemical ordering by permuting particles corresponding to different species. The overall composition is presumed fixed, and the geometry is relaxed after each permutation in order to relieve local strain. From ideas used to solve graph partitioning problems we devise a deterministic search scheme that outperforms (by orders of magnitude) conventional and self-guided basin-hopping global optimisation. The search is guided by the energy gain from either swapping particles i and j (ΔE{sub ij}) or changing the identity of particles i (ΔE{sub i}). These quantities are derived from the underlying (arbitrary) energy function, hence not constituting external bias, and for site-separable force fields each ΔE{sub i} can be approximated simply and efficiently. In our self-guided variant of basin-hopping, particles are weighted by an approximate ΔE{sub i} when randomly selected for an exchange, yielding a significant improvement for segregated multicomponent systems with modest particle size mismatch.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗