Search NASA⌕ Search

SEARCH · Search NASA

Results for “combinatorial optimization”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Increasing the hardness of posiform planting using random QUBOs for programmable quantum annealer benchmarking

Posiform planting is a method for constructing QUBO instances with a unique planted solution that can be tailored to arbitrary connectivity graphs. In this study we investigate making posiform planted QUBOs computationally harder by fusing many smaller random Ising models, whose global minimum is computed classically, with posiform planted QUBOs. The unique ground state of the resulting QUBO is the concatenation of (exactly one of) the ground states of each smaller problem. Our method generates QUBO instances that have a unique solution, are native to the hardware graph, and have tunable computational hardness. We use our QUBOs to benchmark three D-Wave quantum annealing processors (with 563–5627 qubits), and compare them against simulated annealing and Gurobi. Surprisingly, we find that the D-Wave ground state sampling success rate is not dependent on the glued random QUBO size, and that some QUBO classes are solved at high success rates at short annealing times on the Zephyr processors.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Online Energy-optimal Routing for Electric Vehicles with Combinatorial Multi-arm Semi-Bandit

We have seen a rapid growth in the adoption of electric vehicle in today’s commercial mobility service market, from carrying passengers to the delivery of goods. One cardinal issue concerning the operation of EVs is the optimal routing of EV fleets with limited battery capacity. In this study, we investigate the energy-optimal online routing problem for the fleet of EVs, which focuses on identifying real-time minimum electricity consumption paths (MECP) for multiple OD pairs with limited information. We develop a multi-OD combinatorial multi-arm semi-bandit model (MCMAB) that uses the fleet of EVs as sensors in the transportation network and promotes the utilization of common information shared by different OD pairs. We further enrich the model with the path elimination policy to obtain MECP of high confidence while significantly reducing the number of learning iterations and the number of explorations needed. We demonstrate the effectiveness of the MCMAB and the efficiency of the path elimination policy with comprehensive numerical experiments in Manhattan, NYC. The results show that the proposed online routing algorithms can achieve near-optimal MECPs efficiently, and the quality of the solutions is significantly better than using the shortest travel time paths as approximate MECPs.

Chen, Xiaowei↗
DOE OSTI2018

Multi-modal optimization of bismuth vanadate photoanodes via combinatorial alloying and hydrogen processing

Alloying transition metals, such as Mo, into BiVO 4 has emerged as the primary mechanism for improving carrier transport in this photoanode for solar fuels production. The present work establishes here the generality of improving photoelectrochemical performance through co-alloying with a transition metal electron donor and a structure-modulating rare earth. Further improvement for all such alloys is obtained by annealing the oxide materials in H 2 , ultimately producing photoanodes with above 3 mA cm -2 photocurrent density under AM 1.5G illumination, in the top tier of compact BiVO 4 films.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Deep reinforcement learning to discover multi-fuel injection strategies for compression ignition engines

Over the past several decades, regulation of compression ignition engine emissions has become increasingly stringent as concern about the environmental and health implications of these emissions has grown. These changing constraints have led to a series of new, alternative fuel injection strategies that aim to maintain power output while reducing in-cylinder generated emissions by operating in the low-temperature combustion (LTC) regime. These advanced injection strategies are created and retuned for individual combinations of engine geometry, fuel, and emissions constraints. Deep reinforcement learning has been shown to be an effective alternative to traditional optimization approaches for highly combinatorial control problems, such as discovering the optimal injection schedules for compression ignition engines. In this study, we deploy a previously presented deep reinforcement learning framework to iteratively optimize a series of engine geometries over a range of increasingly strict NO x emissions regulations. We then examine the resulting injection schedules. We discuss the potential for using this deep reinforcement learning framework for fuel selection screening and for discovering unique injection strategies for different engine geometries and future emissions standards.

33 ADVANCED PROPULSION SYSTEMS↗
DOE OSTI2020

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Quantum computational phase transition in combinatorial problems

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2026

Robust Optimal Experimental Design of Infinite-Dimensional Bayesian Nonlinear Inverse Problems

Abstract. We consider robust optimal experimental design (ROED) for nonlinear Bayesian inverse problems governed by partial differential equations (PDEs). An optimal design is one that maximizes some utility quantifying the quality of the solution of an inverse problem. However, the optimal design is dependent on elements of the inverse problem such as the simulation model, the prior, or the measurement error model. ROED aims to produce an optimal design that is aware of the additional uncertainties encoded in the inverse problem and remains optimal even after variations in them. We follow a worst-case scenario approach to develop a new framework for robust optimal design of nonlinear Bayesian inverse problems. The proposed framework (a) is scalable and designed for infinite-dimensional Bayesian nonlinear inverse problems constrained by PDEs; (b) develops efficient approximations of the utility, namely the expected information gain; (c) employs eigenvalue sensitivity techniques to develop analytical forms and efficient evaluation methods of the gradient of the utility with respect to the uncertainties against which we wish to be robust; and (d) employs a probabilistic optimization paradigm that properly defines and efficiently solves the resulting combinatorial max-min optimization problem. The effectiveness of the proposed approach is illustrated for optimal sensor placement problem in an inverse problem governed by an elliptic PDE.

Chowdhary, Abhijit↗
DOE OSTI2018

Unsupervised phase mapping of X-ray diffraction data by nonnegative matrix factorization integrated with custom clustering

Abstract Analyzing large X-ray diffraction (XRD) datasets is a key step in high-throughput mapping of the compositional phase diagrams of combinatorial materials libraries. Optimizing and automating this task can help accelerate the process of discovery of materials with novel and desirable properties. Here, we report a new method for pattern analysis and phase extraction of XRD datasets. The method expands the Nonnegative Matrix Factorization method, which has been used previously to analyze such datasets, by combining it with custom clustering and cross-correlation algorithms. This new method is capable of robust determination of the number of basis patterns present in the data which, in turn, enables straightforward identification of any possible peak-shifted patterns. Peak-shifting arises due to continuous change in the lattice constants as a function of composition and is ubiquitous in XRD datasets from composition spread libraries. Successful identification of the peak-shifted patterns allows proper quantification and classification of the basis XRD patterns, which is necessary in order to decipher the contribution of each unique single-phase structure to the multi-phase regions. The process can be utilized to determine accurately the compositional phase diagram of a system under study. The presented method is applied to one synthetic and one experimental dataset and demonstrates robust accuracy and identification abilities.

36 MATERIALS SCIENCE↗
DOE OSTI2025

High-Throughput Microfluidic Electroporation (HTME): A Scalable, 384-Well Platform for Multiplexed Cell Engineering

Electroporation-mediated gene delivery is a cornerstone of synthetic biology, offering several advantages over other methods: higher efficiencies, broader applicability, and simpler sample preparation. Yet, electroporation protocols are often challenging to integrate into highly multiplexed workflows, owing to limitations in their scalability and tunability. These challenges ultimately increase the time and cost per transformation. As a result, rapidly screening genetic libraries, exploring combinatorial designs, or optimizing electroporation parameters requires extensive iterations, consuming large quantities of expensive custom-made DNA and cell lines or primary cells. To address these limitations, we have developed a High-Throughput Microfluidic Electroporation (HTME) platform that includes a 384-well electroporation plate (E-Plate) and control electronics capable of rapidly electroporating all wells in under a minute with individual control of each well. Fabricated using scalable and cost-effective printed-circuit-board (PCB) technology, the E-Plate significantly reduces consumable costs and reagent consumption by operating on nano to microliter volumes. Furthermore, individually addressable wells facilitate rapid exploration of large sets of experimental conditions to optimize electroporation for different cell types and plasmid concentrations/types. Use of the standard 384-well footprint makes the platform easily integrable into automated workflows, thereby enabling end-to-end automation. We demonstrate transformation of E. coli with pUC19 to validate the HTME's core functionality, achieving at least a single colony forming unit in more than 99% of wells and confirming the platform's ability to rapidly perform hundreds of electroporations with customizable conditions. This work highlights the HTME's potential to significantly accelerate synthetic biology Design-Build-Test-Learn (DBTL) cycles by mitigating the transformation/transfection bottleneck.

Gaillard, William R↗
DOE OSTI2025

Quantum Adiabatic Optimization with Rydberg Arrays: Localization Phenomena and Encoding Strategies

Quantum adiabatic optimization seeks to solve combinatorial problems using quantum dynamics, requiring the Hamiltonian of the system to align with the problem of interest. However, these Hamiltonians are often incompatible with the native constraints of quantum hardware, necessitating encoding strategies to map the original problem into a hardware-conformant form. While the classical overhead associated with such mappings is easily quantifiable and typically polynomial in problem size, it is much harder to quantify their overhead on the quantum algorithm, e.g., the transformation of the adiabatic timescale. In this work, we address this challenge on the concrete example of the encoding scheme proposed in [Nguyen , PRX Quantum , 010316 (2023)], which is designed to map optimization problems on arbitrarily connected graphs into Rydberg atom arrays. We consider the fundamental building blocks underlying this encoding scheme and determine the scaling of the minimum gap with system size along adiabatic protocols. Even when the original problem is trivially solvable, we find that the encoded problem can exhibit an exponentially closing minimum gap. We show that this originates from a quantum coherent effect, which gives rise to an unfavorable localization of the ground-state wave function. On the QuEra Aquila neutral atom machine, we observe such localization and its effect on the success probability of finding the correct solution to the encoded optimization problem. Finally, we propose quantum-aware modifications of the encoding scheme that avoid this quantum bottleneck and lead to an exponential improvement in the adiabatic performance. This highlights the crucial importance of accounting for quantum effects when designing strategies to encode classical problems onto quantum platforms. Published by the American Physical Society 2025

Bombieri, Lisa (ORCID:0009000950422897)↗
DOE OSTI2018

Restoration using Distributed Energy Resources for Resilient Power Distribution Networks

In this paper, we propose a restorative method to minimize the unserved demand in a power distribution network where some islands are formed due to multiple line outages. The restoration is achieved by tie-line switching and by solving a mixed-integer non-linear problem. Due to combinatorial issues of the optimization problem, a method is proposed which restores the system by setting up microgrids boundaries within the islands and connecting them through tie-lines for exchange of active power in between them. The optimal tie-line to interconnect the microgrids is decided through information exchange between the microgrid operators. Case studies on IEEE 33-bus distribution network is presented to illustrate the results and validate the performance of the proposed method.

Sarkar, Ranadhir↗
DOE OSTI2023

Rapid design of top-performing metal-organic frameworks with qualitative representations of building blocks

Abstract Data-driven materials design often encounters challenges where systems possess qualitative (categorical) information. Specifically, representing Metal-organic frameworks (MOFs) through different building blocks poses a challenge for designers to incorporate qualitative information into design optimization, and leads to a combinatorial challenge, with large number of MOFs that could be explored. In this work, we integrated Latent Variable Gaussian Process (LVGP) and Multi-Objective Batch-Bayesian Optimization (MOBBO) to identify top-performing MOFs adaptively, autonomously, and efficiently. We showcased that our method (i) requires no specific physical descriptors and only uses building blocks that construct the MOFs for global optimization through qualitative representations, (ii) is application and property independent, and (iii) provides an interpretable model of building blocks with physical justification. By searching only ~1% of the design space, LVGP-MOBBO identified all MOFs on the Pareto front and 97% of the 50 top-performing designs for the CO 2 working capacity and CO 2 /N 2 selectivity properties.

36 MATERIALS SCIENCE↗
DOE OSTI2023

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↗
DOE OSTI2021

Discovery of amivantamab (JNJ-61186372), a bispecific antibody targeting EGFR and MET

A bispecific antibody (BsAb) targeting the epidermal growth factor receptor (EGFR) and mesenchymal–epithelial transition factor (MET) pathways represents a novel approach to overcome resistance to targeted therapies in patients with non–small cell lung cancer. In this study, we sequentially screened a panel of BsAbs in a combinatorial approach to select the optimal bispecific molecule. The BsAbs were derived from different EGFR and MET parental monoclonal antibodies. Initially, molecules were screened for EGFR and MET binding on tumor cell lines and lack of agonistic activity toward MET. Hits were identified and further screened based on their potential to induce untoward cell proliferation and cross-phosphorylation of EGFR by MET via receptor colocalization in the absence of ligand. After the final step, we selected the EGFR and MET arms for the lead BsAb and added low fucose Fc engineering to generate amivantamab (JNJ-61186372). The crystal structure of the anti-MET Fab of amivantamab bound to MET was solved, and the interaction between the two molecules in atomic details was elucidated. Amivantamab antagonized the hepatocyte growth factor (HGF)-induced signaling by binding to MET Sema domain and thereby blocking HGF β-chain—Sema engagement. The amivantamab EGFR epitope was mapped to EGFR domain III and residues K443, K465, I467, and S468. Furthermore, amivantamab showed superior antitumor activity over small molecule EGFR and MET inhibitors in the HCC827-HGF in vivo model. Based on its unique mode of action, amivantamab may provide benefit to patients with malignancies associated with aberrant EGFR and MET signaling.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

Exploring the benefits of utilizing small modular device for sustainable and flexible shale gas water management

Growing shale gas extraction in recent years has triggered wide discussions on the associated freshwater requirement and wastewater management. Many optimization approaches have been developed for shale gas water management; however, most of the studies assumed permanent utilization of wastewater treatment facilities with fixed capacities. Considering the rapidly declining characteristics of shale gas wastewater production, these treatment facilities could remain largely underutilized after the first few months/years of production, making them less economically attractive. To maximize the capacity utilization of treatment facilities and further improve the economic performance of shale gas development, this study develops a systematic optimization framework, where the capacity strategy of conventional treatment facilities and utilization of the recent concept of modular manufacturing are both considered for flexible shale gas water management. The proposed mixed-integer linear programming (MILP) model simultaneously optimizes the design and planning of integrated shale gas and water supply chain, with a focus on capacity planning for both large-scale conventional treatment facilities and small-scale modular devices. A series of Marcellus-based case studies are performed to illustrate the applicability of the proposed model and provide general insights into the trade-offs between the multiple types of treatment facilities. The optimization results reveal that the combinatorial utilization of conventional facilities and modular devices for wastewater treatment (66% by conventional facilities and 34% by modular devices) brings 9.3% more reused water for other well development and 6.2% savings in water-related costs, compared to flexible management of only conventional facilities. Furthermore, this work suggests that taking modular device as auxiliary equipment for shale gas water management is most beneficial to increase the capacity utilization of treatment facilities and achieve a more economic and sustainable shale gas production system.

04 OIL SHALES AND TAR SANDS↗