Search NASA⌕ Search

SEARCH · Search NASA

Results for “problems”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.

Kim, Youngseo↗
DOE OSTI2020

Analytic Modeling of a Deep Shielding Problem

Previous generations of scientists would make tremendous efforts to simplify non-tractable problems and generate simpler models that preserved the fundamental physics. This process involved applying assumptions and simplifications to reduce the complexity of the problem until it reached a solvable form. Each assumption and simplification was chosen and applied with the intent to preserve the essential physics of the problem, since, if the core physics of the problem were eliminated, the simplified model served no purpose. Moreover, if done correctly, solutions to the reduced model would serve as useful approximations to the original problem. In a sense, solving the simple models laid the ground-work for and provided insight into the more complex problem. Today, however, the affordability of high performance computing has essentially replaced the process for analyzing complex problems. Rather than \building up" a problem by understanding smaller, simpler models, a user generally relies on powerful computational tools to directly arrive at solutions to complex problems. As computational resources grow, users continue trying to simulate new, more complex, or more detailed problems, resulting in continual stress on both the code and computational resources. When these resources are limited, the user will have to make concessions by simplifying the problem while trying to preserve important details. In the context of MCNP, simplifications typically come as reductions in geometry, or by using variance reduction techniques. Both approaches can influence the physics of the problem, leading to potentially inaccurate or non-physical results. Errors can also be introduced as a result of faulty input into a computational tool: something as simple as transposing numbers in a tally input can result in incorrect answers.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2023

Multigrid Reduction in Time for Chaotic and Hyperbolic Problems (Final Report)

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallelin-time methods, with the most common method, parareal, diverging in many cases. The current state-of-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, this work shall continue researching the directions from the current collaboration with Dr. Falgout, which are laid out in the work Toward Parallel in Time for Chaotic Dynamical Systems and showed the first known results of a parallel-in-time speedup for a chaotic problem. This work outlines two key improvements to XBraid for chaotic problems, the so-called “theta” and “delta-correction” methods. Here, these two improvements will be implemented in a high-performance but general way in XBraid and explored for more complicated problems. We will additionally research, as time allows, improvements to these techniques, as well as multigrid relaxation techniques based on Least Squares Shadowing (LSS by Wang) and a nonintrusive block tridiagonal solver based on MGRIT, called TriMGRIT.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Multigrid Reduction in Time for Chaotic and Hyperbolic Problems (Final Report)

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallel-in-time methods, with the most common method, parareal, diverging in many cases. The current state of-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, this work shall continue researching the directions from the current collaboration with Dr. Falgout, which are laid out in the work Toward Parallel in Time for Chaotic Dynamical Systems and showed the first known results of a parallel-in-time speedup for a chaotic problem. This work outlines two key improvements to XBraid for chaotic problems, the so-called “theta” and “delta-correction” methods. Here, these two improvements will be further researched and improved (including with a new relaxation method inspired by on Least Squares Shadowing (LSS)) and explored for more complicated problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Parallel Multigrid in Time and Space for Extreme-Scale Computational Science: Chaotic and Hyperbolic Problems

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallelin-time methods, with the most common method, parareal, diverging in many cases. The current stateof-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, we take inspiration from the Least Squares Shadowing (LSS by Wang) approach for solving chaotic problems. Here, an optimization approach is able to find “well-conditioned” shadow trajectories/solutions to the original “ill-conditioned” chaotic problem. Thus, the new multigrid methods researched here also arise in an optimization context.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Phase field benchmark problems targeting fluid flow and electrochemistry

Here, we continue our development of phase field model benchmark problems with the addition of a third set, complimenting our previously developed problems for diffusion, precipitation, dendritic growth and linear elasticity. These benchmark problems are being jointly developed by the Center for Hierarchical Materials Design (CHiMaD) and the National Institute of Standards and Technology (NIST) along with input from the phase field community. The first problem in this third set targets Stokes flow, with a particular emphasis on flow around an obstruction placed asymmetrically in the domain. While Stokes flow is not traditionally in the canon of phase field problems, it is a class of problems gaining importance in areas such as filtration and water purification. The second problem deals with coupled Cahn-Hilliard diffusion and electrostatic forces, which is an important area in energy storage and battery sciences. We present our own solutions and discuss sources of numerical errors for the Stokes problem as well as simple checks to avoid fundamental issues in the coupled diffusion-electrostatics problem. The latter problem contains some subtleties that we expand on in an Appendix.

36 MATERIALS SCIENCE↗
DOE OSTI2025

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Optimization problems governed by systems of PDEs with uncertainties

This paper reviews current theoretical and numerical approaches to optimization problems governed by partial differential equations (PDEs) that depend on random variables or random fields. Such problems arise in many engineering, science, economics and societal decision-making tasks. This paper focuses on problems in which the governing PDEs are parametrized by the random variables/fields, and the decisions are made at the beginning and are not revised once uncertainty is revealed. Examples of such problems are presented to motivate the topic of this paper, and to illustrate the impact of different ways to model uncertainty in the formulations of the optimization problem and their impact on the solution. A linear–quadratic elliptic optimal control problem is used to provide a detailed discussion of the set-up for the risk-neutral optimization problem formulation, study the existence and characterization of its solution, and survey numerical methods for computing it. Different ways to model uncertainty in the PDE-constrained optimization problem are surveyed in an abstract setting, including risk measures, distributionally robust optimization formulations, probabilistic functions and chance constraints, and stochastic orders. Furthermore, approximation-based optimization approaches and stochastic methods for the solution of the large-scale PDE-constrained optimization problems under uncertainty are described. Some possible future research directions are outlined.

Heinkenschloss, Matthias [Rice Univ., Houston, TX ↗
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 OSTI2024

Average Incremental Cost Pricing for the AC Unit Commitment Problem [Rev. 1]

Unit Commitment (UC) problems that consider the Alternating Current (AC) model of the transmission network have long been considered intractable to solve at scale by the power system community. Recently, the Grid-Optimization (GO) Competition held by the Advanced Research Project Agency-Energy (ARPA-E) has facilitated the development of the first algorithms to solve large-scale ACUC problems. This new capability opens a path towards the explicit consideration of the AC transmission network model in UC problems used to clear day-ahead electricity markets. This calls for the analysis of electricity market structures that accommodate both the continuous non-linearity of the AC transmission network and the discrete non-linearity of the UC problem simultaneously. This paper serves as an initial effort to do so by proposing an Average Incremental Cost (AIC) pricing structure that is designed around the ACUC problem. In particular, an AIC one-pass pricing problem is proposed that represents a continuously constrained variant of the ACUC problem and allows for the computation of Locational Incremental Prices (LIPs) for both real and reactive power as the local optimal Lagrange multipliers of the power balance constraints. To avoid degeneracy, the pricing problem includes a small parameter ϵ > 0. Under certain assumptions market participants are shown to realize profit that converges to a non-negative value as ϵ approaches zero, practically ensuring profitability for small values of ϵ. We additionally provide many simple and important examples that provide intuition and insights into the proposed prices. Examples illustrate the basic concept of AIC pricing, the derived profitability results, the existence of multiple LIPs, the importance of including reactive power in the dispatch and pricing problems, the need for reactive power prices, and the improved incentives exhibited by LIPs as compared to traditional Locational Marginal Prices (LMPs). We additionally indicate many directions for future work including analysis of larger test cases.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2023

Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initialization

Obtaining lightweight and accurate approximations of discretized objective functional Hessians in inverse problems governed by partial differential equations (PDEs) is essential to make both deterministic and Bayesian statistical large-scale inverse problems computationally tractable. The cubic computational complexity of dense linear algebraic tasks, such as Cholesky factorization, that provide a means to sample Gaussian distributions and determine solutions of Newton linear systems is a computational bottleneck at large-scale. These tasks can be reduced to log-linear complexity by utilizing hierarchical off-diagonal low-rank (HODLR) matrix approximations. In this work, we show that a class of Hessians that arise from inverse problems governed by PDEs are well approximated by the HODLR matrix format. In particular, we study inverse problems governed by PDEs that model the instantaneous viscous flow of ice sheets. In these problems, we seek a spatially distributed basal sliding parameter field such that the flow predicted by the ice sheet model is consistent with ice sheet surface velocity observations. Here, we demonstrate the use of HODLR Hessian approximation to efficiently sample the Laplace approximation of the posterior distribution with covariance further approximated by HODLR matrix compression. Computational studies are performed which illustrate ice sheet problem regimes for which the Gauss–Newton data-misfit Hessian is more efficiently approximated by the HODLR matrix format than the low-rank (LR) format. We then demonstrate that HODLR approximations can be favorable, when compared to global LR approximations, for large-scale problems by studying the data-misfit Hessian associated with inverse problems governed by the first-order Stokes flow model on the Humboldt glacier and Greenland ice sheet.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Evaluation of a nonlinear variational multiscale method for fluid transport problems

Diverse transport problems, especially those based on fluid flow models, are intrinsically multiscale and nonlinear, characteristics that often lead to intricate dynamics such as the development of instabilities and turbulence. Computational simulations that resolve all scales in these problems are often unfeasible, prompting to coarse-grained simulation strategies in which small-scale features are modeled instead of resolved. Variational Multiscale (VMS) methods, and particularly residual-based Large-Eddy Simulation (LES) approaches, have proven effective and robust for the coarse-grained simulation of complex transport problems. VMS methods avoid the assumption of separable nonlinearity and the reliance on empirical small-scale models by using a variational decomposition of scales together with a residual-based approximation of the small-scales. Evaluation of a nonlinear VMS approach, denoted as VMS n , is presented for the coarse-grained simulation of transient-advective-diffusive-reactive (TADR) transport problems arising from fluid flow models. In contrast to classical VMS approaches that neglect the effect of the small scales on the transport operator, VMS n treats the inter-dependence between large- and small-scales upfront. The treatment of inter-scale coupling involves the solution of a local algebraic nonlinear system describing the evolution of the small-scales. The VMS n approach is complemented with two algebraic approximations of the small-scales: one based on the main diagonal of the transport matrices and another that preserves transport fluxes and is suitable for generic TADR systems. The suitability of the VMS n approach for handling general TADR problems and regimes is evaluated with benchmark incompressible, compressible, and magnetohydrodynamic laminar flow problems, the incompressible Taylor-Green vortex flow, the turbulent free jet, and the two-temperature arc in crossflow. Furthermore, simulation results show that VMS n leads to minor improvements in accuracy with respect to the classical VMS for the laminar flow problems, but to significantly greater accuracy for the turbulent flows and the unsteady plasma flow problems, while using the same cohesive numerical formulation.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2020

MPACT Verification With Magnox Reactor Neutronics Progression Problems

MPACT is a state-of-the-art core simulator designed to perform high-fidelity analysis using whole-core, three-dimensional, pin-resolved neutron transport calculations on modern parallel computing hardware. MPACT was originally developed to model light water reactors, and its capabilities are being extended to simulate gas-cooled, graphite-moderated cores such as Magnox reactors. To verify MPACT’s performance in this new application, the code is being formally benchmarked using representative problems. Progression problems are a series of example models that increase in complexity designed to test a code’s performance. The progression problems include both beginning-of-cycle and depletion calculations. Reference solutions for each progression problem have been generated using Serpent 2, a continuous-energy Monte Carlo reactor physics burnup calculation code.Using the neutron multiplication eigenvalue ke as a metric, MPACT’s performance is assessed on each of the progression problems. Initial results showed that MPACT’s multi-group cross section libraries, originally developed for pressurized water reactor problems, were not sufficient to accurately solve Magnox problems. MPACT’s improved performance on the progression problems is demonstrated using this new optimized cross section library.

Luciano, Nicholas↗
DOE OSTI2022

Verification and Validation of Two Hydrodynamic Methods for Simulations of High Energy Density Physics Problems

A 3D verification and validation suite of test problems is presented and used to evaluate hydrodynamic methods within a radiation hydrodynamics code, xRAGE. These test problems exercise different levels of complexity, building towards ICF problems which in addition to hydrodynamics also include three temperature plasma physics, thermal conduction, and radiation diffusion. Among the problems in the test suite are the Kidder ball problem, the Verney shell problem, and a 5-material compression problem, which exercise different purely hydrodynamic methods implemented within xRAGE. There is excellent agreement between 2D and 3D XRAGE simulation results and between the xRAGE results and the benchmark solutions. Two 3D ICF test problems are also presented, based on an OMEGA direct drive capsule experiment and on a NIF indirect drive capsule experiment. It is demonstrated that the newer unsplit hydrodynamic method in xRAGE produces more vorticity relative to the older default method. For the indirect drive capsule, the 3D simulations are in reasonable agreement with the experimental values of ion temperature and neutron production.

47 OTHER INSTRUMENTATION↗
DOE OSTI2025

Designing a Framework for Solving Multiobjective Simulation Optimization Problems

Multiobjective simulation optimization (MOSO) problems are optimization problems with multiple conflicting objectives, where evaluation of at least one of the objectives depends on a black-box numerical code or real-world experiment, which we refer to as a simulation. Whereas an extensive body of research is dedicated to developing new algorithms and methods for solving these and related problems, it is challenging and time-consuming to integrate these techniques into real-world production-ready solvers. This is partly because of the diversity and complexity of modern state-of-the-art MOSO algorithms and methods and partly because of the complexity and specificity of many real-world problems and their corresponding computing environments. The complexity of this problem is only compounded when introducing potentially complex and/or domain-specific surrogate-modeling techniques, problem formulations, design spaces, and data acquisition functions. Here, this paper carefully surveys the current state of the art in MOSO algorithms, techniques, and solvers, as well as problem types and computational environments where MOSO is commonly applied. We then present several key challenges in the design of a parallel multiobjective simulation optimization framework (ParMOO) and how they have been addressed. Finally, we provide two case studies demonstrating how customized ParMOO solvers can be quickly built and deployed to solve real-world MOSO problems.

engineering design optimization↗
DOE OSTI2021

Performance Results for Sensor Assignment Problem as Solved on a Multi-Node Cluster

An earlier report described a procedure for optimal sensor set selection and its implementation on a computational cluster. This new and innovative capability was developed to facilitate a reduction in operations staffing levels to improve plant economics. By automating surveillance and maintenance tasks through early detection of degrading sensors and equipment, staff can be more efficiently deployed. The method uses automated reasoning and domain knowledge in the form of the conservation equations to infer from plant measurements the state of equipment health. Inclusion of domain knowledge addresses the problem that exists with pure data-driven methods that there are no rigorous guidelines for determining what constitutes an adequate sensor set. Formalizing the procedure for sensor set selection as we have done results in a more reliable and explainable diagnosis of plant equipment health. Importantly, from the standpoint of the plant owner, personnel are provided with an early and explicit diagnosis of an equipment problem. That in principle automates the process and eliminates having to send personnel into the plant to find the cause as typically occurs when a data-driven method detects an anomaly. In this report we describe first results obtained using a computational cluster to solve the sensor set selection problem as framed above. The case described addresses the problem of equipment health monitoring in the high-pressure (HP) feedwater system of a pressurized light water reactor as seen through the eyes of our collaborating utility partner. Maintenance of this system can amount to millions of dollars per year if equipment health issues go undiagnosed and lead to loss of function. On examining the potential that is inherent in the installed sensor set for diagnosing equipment health degradation, it was found that greater fault resolution capability can be achieved using a sensor set that is 20 percent fewer in number. The take-away is that compared to the installed sensor set there exists a more strategic assignment of sensors that will furnish better health monitoring capability and with fewer sensors. Where the problem defies solution by manual inspection, as is the case here, one can be found by an algorithm. The solution was obtained in four hours using 30 computational cores. The HP feedwater problem as posed above illustrates the added value of approaching the sensor selection problem as one amenable to algorithmic solution. This problem is of interest to advanced reactor designers and to utilities that are setting up remote monitoring and diagnostic centers.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2024

Progressive Hedging Decomposition for Solutions of Large-Scale Process Family Design Problems

In previous work, we have introduced a mathematical model for solving a discretized version of the process family design problem. This involves two sets of decision variables. One set selects which unit module designs are included in the process platform out of a candidate set of options; the other set determines which of these unit module designs are assigned to each variant. In this work, we exploit a parallelized Progressive Hedging (PH) algorithm to solve even larger scale design problems. PH is a well-known algorithm traditionally used to solve stochastic programming problems. While our problem is not a two-stage stochastic programming problem, the structure is similar, and it can be directly mapped to the PH approach, which we employ here to solve this deterministic optimization problem. We decompose our problem by process variant. We treat the platform unit module design variables as first-stage and the assignment of unit module designs to variants as second-stage, solving the problem using mpi-sppy. We demonstrate this approach on case studies of CC, water desalination, and refrigeration.

Stinchfield, Georgia↗
DOE OSTI2023

Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems

Challenging combinatorial optimization problems are ubiquitous in science and engineering. Several quantum methods for optimization have recently been developed, in different settings including both exact and approximate solvers. Addressing this field of research, this manuscript has three distinct purposes. First, we present an intuitive method for synthesizing and analyzing discrete (i.e., integer-based) optimization problems, wherein the problem and corresponding algorithmic primitives are expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. This compact representation often allows for more efficient problem compilation, automated analyses of different encoding choices, easier interpretability, more complex runtime procedures, and richer programmability, as compared to previous approaches, which we demonstrate with a number of examples. Second, we perform numerical studies comparing several qubit encodings; the results exhibit a number of preliminary trends that help guide the choice of encoding for a particular set of hardware and a particular problem and algorithm. Our study includes problems related to graph coloring, the traveling salesperson problem, factory/machine scheduling, financial portfolio rebalancing, and integer linear programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables, demonstrating that compact (binary) encodings are more amenable to QAOA than previously understood. We expect this toolkit of programming abstractions and low-level building blocks to aid in designing quantum algorithms for discrete combinatorial problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗