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.

215 records · Page 12

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗

Mapping Arbitrarily Sparse Two-body Interactions on One-dimensional Quantum Circuits

We consider an assignment problem arising in Fermionic-swap based mapping of the one-body and two-body interaction terms in simulating time evolution of a sparse second-quantized electronic structure Hamiltonian on a quantum computer. Relative efficiency of different swap networks depends on the relative costs of performing a swap layer and computing a Hamiltonian interaction term. Under the assumption that the interaction term cost dominates the computation, we develop an iterative algorithm that uses hypergraph optimal linear arrangement (HOLA) and partial distance-2 coloring to exploit arbitrary sparsity in the Hamiltonian for efficient computation using swap networks. Using a set of 122 problems from computational chemistry, we demonstrate performance improvements up to 100% relative to the state-of-the-art approaches for one-body terms and up to 86% utilization for two-body terms relative to a theoretical peak utilization. To the best of our knowledge, this is the first study to exploit arbitrary sparsity in orbital interactions for efficient computation on one-dimensional qubit connectivity layouts. The proposed algorithms form the basis for extension to map general k-body interactions that arise in other domains onto generalized qubit connectivity layouts.

quantum computing, Combinatorial Optimization, hyp↗

cuAlign: Scalable Network Alignment on GPU Accelerators

Given two graphs, the objective of network alignment is to find the best one-to-one mapping of vertices in one graph (??) to vertices in the other (??), such that the number of overlaps is maximized. We say that edges(??, ??) ???and(??', ??') ??? are overlapped if ?? is mapped to ??' and ?? is mapped to??'. Network alignment is an important optimization problem with several applications in bioinformatics, computer vision and ontology matching. Since it is an NP-hard problem, efficient heuristics and scalable implementations are necessary. In this work, we introduce a new framework that combines the concepts of intra-network proximity using vertex embedding,Belief Propagation (BP) and approximate weighted matching, and provides qualitative improvements up to22%over state-of-the-art approaches. We also provide scalable implementations on GPU accelerators, demonstrating up to19×speedup for Belief Propagation and 3× speedup for approximate weighted matching relative to previous multithreaded implementation. A combination of combinatorial and algebraic kernels within the network alignment algorithm poses significant hurdles for parallelization. Load imbalance and irregular DRAM traffic limit achievable performance on GPUs. Our novel approach identifies and exploits unique structural proper-ties of the BP-based algorithm and employs code fusion to reduce data movement between different steps of the algorithm. Using a diverse set of inputs, we demonstrate qualitative improvements of our algorithms, and performance gains of our GPU-accelerated implementation. We believe that our work will enable algorithmic improvements and practical applications of network alignment.

Xiang, Lizhi↗

Design Considerations for GPU-based Mixed Integer Programming on Parallel Computing Platforms

Mixed Integer Programming (MIP) is a powerful abstraction in combinatorial optimization that finds real-life application across many significant sectors. The recent proliferation of graphical processing unit (GPU)-based accelerated computing architectures in large-scale parallel computing or supercomputing presents new opportunities as well as challenges in the advancement of MIP solver technology to effectively use the new accelerated computing platforms and scale to large parallel systems. Here, we recount the conventional processor-based strategies and focus on configurations where the most promising intersection lies between parallel MIP solver approaches and the specific strengths of accelerated parallel platforms. We note that the best potential lies in solving problems whose individual matrix sizes (of the linear program relaxation) fit entirely within one accelerator's memory and whose branch-and-bound (or branch-and-cut) trees cannot be fully contained within a small number of computational nodes. Additionally, we identify ideal features of computational linear algebra support on GPU accelerators that would help advance this direction of scalable parallel solution of MIP problems on GPU-based accelerated computing architectures.

Perumalla, Kalyan↗

Optimal experimental design: Formulations and computations

Questions of ‘how best to acquire data’ are essential to modelling and prediction in the natural and social sciences, engineering applications, and beyond. Optimal experimental design (OED) formalizes these questions and creates computational methods to answer them. This article presents a systematic survey of modern OED, from its foundations in classical design theory to current research involving OED for complex models. We begin by reviewing criteria used to formulate an OED problem and thus to encode the goal of performing an experiment. We emphasize the flexibility of the Bayesian and decision-theoretic approach, which encompasses information-based criteria that are well-suited to nonlinear and non-Gaussian statistical models. We then discuss methods for estimating or bounding the values of these design criteria; this endeavour can be quite challenging due to strong nonlinearities, high parameter dimension, large per-sample costs, or settings where the model is implicit. A complementary set of computational issues involves optimization methods used to find a design; we discuss such methods in the discrete (combinatorial) setting of observation selection and in settings where an exact design can be continuously parametrized. Finally we present emerging methods for sequential OED that build non-myopic design policies, rather than explicit designs; these methods naturally adapt to the outcomes of past experiments in proposing new experiments, while seeking coordination among all experiments to be performed. Throughout, we highlight important open questions and challenges.

97 MATHEMATICS AND COMPUTING↗

Towards Generalizable and Efficient Circuit Topology Design: A Graph-Transformer-based Surrogate Model with Curriculum Learning

Unlike circuit parameter and sizing optimizations, the automated design of analog circuit topologies poses significant challenges for learning-based approaches. One challenge arises from the combinatorial growth of the topology space with circuit size, which limits the topology optimization efficiency. Moreover, traditional circuit evaluation methods are time-consuming, while the presence of data discontinuity in the topology space makes the accurate prediction of circuit performance exceptionally difficult for unseen topologies. To tackle these challenges, we design a novel Graph-Transformer-based Network (GTN) as the surrogate model for circuit evaluation, offering a substantial acceleration in the speed of circuit topology optimization without sacrificing performance. Our GTN model architecture is designed to embed voltage changes in circuit loops and current flows in connected devices, enabling accurate performance predictions for circuits with unseen topologies. To address the cold start problem when scaling GTN to large-scale circuits, we further introduce a curriculum learning strategy that progressively trains GTN from small-scale to large-scale circuits. This approach enables the model to first learn fundamental physical principles from simpler topologies and gradually adapt to complex configurations, effectively bridging the circuit complexity gap and improving prediction accuracy. Taking the power converter circuit design as an experimental task, our GTN model significantly outperforms an analytical approach and baseline methods directly utilizing graph neural networks. Furthermore, GTN achieves less than 5% relative error and 196× speed-up compared with high-fidelity simulation. Notably, our GTN surrogate model empowers an automatic circuit design framework to discover circuits of comparable quality to those identified through high-fidelity simulation while reducing the time required by up to 98.2%. With curriculum learning, the enhanced GTN achieves a 51% improvement for performance prediction of large-scale circuits compared to the GTN model without this strategy. These advancements establish GTN as a scalable framework for automated analog circuit design across varying circuit complexity levels.

Lu, Haoshu [New Jersey Institute of Technology (NJ↗

Two-Stage Adaptive Restoration Decision Support System for a Self-Healing Power Grid

Power outages cost American industries and businesses billions of dollars and jeopardize the lives of hospital patients. The losses can be greatly reduced with a fast, reliable, and flexible self-healing tool. This paper is aimed to tackle the challenging task of developing an adaptive restoration decision support system (RDSS). The proposed RDSS determines restoration actions both in planning and real-time phases and adapts to constantly changing system conditions. The comprehensive formulation encompasses practical constraints including ac power flow, dynamic reserve, and load modeling. Here, the combinatorial problem is decomposed into a two-stage formulation solved by an integer L-shaped algorithm. The two stages are then executed online in the RDSS framework employing a sliding window method. The IEEE 39-bus system has been studied under normal and contingency conditions to demonstrate the effectiveness and efficiency of the proposed online RDSS.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Is submodularity testable?

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f: {l_brace}0, 1{r_brace}{sup n} {yields} R. The distance to submodularity is the minimum fraction of values of f that need to be modified to make f submodular. If this distance is more than {epsilon} > 0, then we say that f is {epsilon}-far from being submodular. The aim is to have an efficient procedure that, given input f that is {epsilon}-far from being submodular, certifies that f is not submodular. We analyze a very natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be very efficient in terms of {epsilon}. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.

99 GENERAL AND MISCELLANEOUS↗

Towards computational materials design from first principles using alchemical changes and derivatives.

The design of new materials with specific physical, chemical, or biological properties is a central goal of much research in materials and medicinal sciences. Except for the simplest and most restricted cases brute-force computational screening of all possible compounds for interesting properties is beyond any current capacity due to the combinatorial nature of chemical compound space (set of stoichiometries and configurations). Consequently, when it comes to computationally optimizing more complex systems, reliable optimization algorithms must not only trade-off sufficient accuracy and computational speed of the models involved, they must also aim for rapid convergence in terms of number of compounds 'visited'. I will give an overview on recent progress on alchemical first principles paths and gradients in compound space that appear to be promising ingredients for more efficient property optimizations. Specifically, based on molecular grand canonical density functional theory an approach will be presented for the construction of high-dimensional yet analytical property gradients in chemical compound space. Thereafter, applications to molecular HOMO eigenvalues, catalyst design, and other problems and systems shall be discussed.

99 GENERAL AND MISCELLANEOUS↗

Generalized optimization-based synthesis of membrane systems for multicomponent gas mixture separation

Synthesizing a membrane system to separate multicomponent gas mixture is challenging due to the combinatorial number of feasible configurations and the difficulties in describing the multicomponent permeators. Here we present a mixed-integer nonlinear programming (MINLP) model for synthesizing membrane systems for multicomponent gas mixture separation. The approach employs a richly connected superstructure to represent numerous potential system configurations, and different physics-based surrogate permeator models, such as countercurrent flow or crossflow, to be used in each stage. Moreover, to describe realistic systems, pressure drop equations can be included. We also present solution methods to accelerate the solution process. Through a case study of natural gas sweetening, we demonstrate that the proposed approach is able to obtain good solutions using an off-the-shelf global optimization solver. Finally, we expand the conventional membrane system synthesis problem by introducing feed variability in our model through a case study of an integrated reactor-separation system.

42 ENGINEERING↗

On the Solution of ℓ 0 -Constrained Sparse Inverse Covariance Estimation Problems

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ 1 regularizer to encourage sparsity is common practice, the combinatorial ℓ 0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ 0 constraint. Here, we introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ 0 -constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods.

$\ell_0$-Constrained↗

The Problem of Size in Robust Design

To facilitate the effective solution of multidisciplinary, multiobjective complex design problems, a departure from the traditional parametric design analysis and single objective optimization approaches is necessary in the preliminary stages of design. A necessary tradeoff becomes one of efficiency vs. accuracy as approximate models are sought to allow fast analysis and effective exploration of a preliminary design space. In this paper we apply a general robust design approach for efficient and comprehensive preliminary design to a large complex system: a high speed civil transport (HSCT) aircraft. Specifically, we investigate the HSCT wing configuration design, incorporating life cycle economic uncertainties to identify economically robust solutions. The approach is built on the foundation of statistical experimentation and modeling techniques and robust design principles, and is specialized through incorporation of the compromise Decision Support Problem for multiobjective design. For large problems however, as in the HSCT example, this robust design approach developed for efficient and comprehensive design breaks down with the problem of size - combinatorial explosion in experimentation and model building with number of variables -and both efficiency and accuracy are sacrificed. Our focus in this paper is on identifying and discussing the implications and open issues associated with the problem of size for the preliminary design of large complex systems.

Koch, Patrick N.↗

Quantum Distributed Unit Commitment: An Application in Microgrids

The dawn of quantum computing brings on a revolution in the way combinatorially complex power system problems such as Unit Commitment are solved. The Unit Commitment problem complexity is expected to increase in the future because of the trend toward the increase of penetration of intermittent renewables. Even though quantum computing has proven effective for solving a host of problems, its applications for power systems’ problems have been rather limited. Here, in this paper, a quantum unit commitment is innovatively formulated and the quantum version of the decomposition and coordination alternate direction method of multipliers (ADMM) is established. The above is achieved by devising quantum algorithms and by exploiting the superposition and entanglement of quantum bits (qubits) for solving subproblems, which are then coordinated through ADMM to obtain feasible solutions. The main contributions of this paper include: 1) the innovative development of a quantum model for Unit Commitment; 2) development of decomposition and coordination-supported framework which paves the way for the utilization of limited quantum resources to potentially solve the large-scale discrete optimization problems; 3) devising the novel quantum distributed unit commitment (QDUC) to solve the problem in a larger scale than currently available quantum computers are capable of solving. The QDUC results are compared with those from its classical counterpart, which validate the efficacy of quantum computing.

97 MATHEMATICS AND COMPUTING↗

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗

Systematic Process Intensification involving Zeotropic Distillation

Distillation is commonly used for separating homogeneous fluid mixtures. While it is based on a simple thermally driven vapor-liquid equilibrium phenomenon at the two-phase region, different variants of distillation systems exist. These include simple distillation, dividing wall columns, pressure swing distillation, thermally coupled distillation and reactive distillation. Complex separation may also involve multiple distillation in a sequence to achieve the desired products. These sequences can be constructed as direct sequence, indirect sequence or thermally coupled columns. Even when a sequence is fixed, each column in the sequence can have a plethora of design alternatives to consider. All these make the design and intensification of distillation systems a challenging task. The large number of plausible design alternatives increases the combinatorial complexity for screening. Although significant efforts have been made in the past, we still lack a method for systematic identification of novel pathways for process intensification of distillation system. This is due to the lack of a generalized representation of all plausible alternatives in a single modeling and optimization framework. In this work, we first present a general representation of thermally driven vapor-equilibrium phenomenon using abstract building blocks. Specifically, each tray in a distillation column is represented by a liquid block and a vapor block with a shared semi-restricted boundary representing the interface. The arrangement of these building blocks in a two-dimensional grid gives rise to all plausible variants of distillation systems. These systems range from simple distillation, dividing wall columns to task-integrated columns. This enables us to systematically identify both classic and out-of-the-box intensified designs at the column and flowsheet levels. The overall distillation-based separation process synthesis problem is formulated as a single mixed-integer nonlinear programming (MINLP) model. In conclusion, the proposed approach is applied to multi-component zeotropic systems to show the capability of identifying promising intensified alternatives.

42 ENGINEERING↗

A Review of Quantum Computing Technologies in Power System Optimization

As modern power grids increasingly integrate variable renewable generation, distributed energy resources, and energy storage systems, classical optimization techniques are facing unprecedented challenges. This review examines the emerging application of quantum computing to overcome these challenges in power system optimization, including optimal power flow (OPF), unit commitment (UC), economic dispatch (ED), and intelligent switching and topology optimization (IS-TO). Recent research has introduced various quantum methodologies—such as gate-based, annealing-based, variational algorithms, and quantum-inspired algorithms—to address the combinatorial complexity inherent in grid reconfiguration and energy management. The review summaries the quantum algorithms, quantum devices and the power system test cases, highlighting hybrid quantum–classical strategies that leverage the complementary strengths of both paradigms. Some quantum advantages have been observed, including theoretical speedup, accurate simulation results, scalable qubit usage, efficient QUBO mapping. In particular, the review emphasizes the importance of integrating quantum optimization techniques with classical control frameworks, these hybrid approaches demonstrate the potential to improve real-time grid management and operational reliability. A significant portion of the analysis is devoted to the practical limitations of current quantum devices. Present-day quantum hardware, operating in the noisy intermediate-scale quantum (NISQ) era, remains highly sensitive to noise and limited in qubit connectivity, which constrains the scale and accuracy of implemented algorithms. The review delves into specific challenges such as the need for qubit-efficient encoding techniques and error mitigation strategies that are critical for handling real-world grid optimization problems. In addition, the work draws attention to the performance discrepancies between theoretical quantum speedups and experimental validations, underscoring the importance of rigorous benchmark studies using representative power grid test cases. In summary, this review highlights both the promise and limitations of quantum computing for power system optimization. It provides a comprehensive overview of the state-of-the-art technologies, categorizes recent advancements in algorithm design, and discusses practical considerations for implementation, and serves as an informative resource on current research. Future research directions include developing robust hybrid frameworks, advancing qubit-efficient formulations, and scaling up experimental demonstrations to confirm the theoretical advantages of quantum methods in large-scale power system operations.

24 POWER TRANSMISSION AND DISTRIBUTION↗

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↗