Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “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 451 records · Page 25

An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Bi-fidelity Gradient-Based Approach for Nonlinear Well Logging Inverse Problems

Solving a non-linear inverse problem is challenging in computational science and engineering. Sampling based methods require a large number of model valuations; gradientbased methods require fewer model evaluations but only find the local minima. Multifidelity optimization combines the low fidelity model and the high-fidelity model to achieve both high accuracy and high efficiency. In this paper, we present a bi-fidelity approach to solve non-linear inverse problems. In the bi-fidelity inversion method, the low-fidelity model is used to acquire a good initial guess, and the high-fidelity model is used to locate the global minimum. Combined with a multi-start optimization scheme, the proposed approach significantly increases the possibility of finding the global minimum for nonlinear inverse problems with many local minima. The method is tested with two toy problems and then applied to an electromagnetic well logging inverse problem, which is difficult to solve using traditional gradient-based methods. The bi-fidelity method provides promising inversion results and can be easily applied to traditional gradient-based methods.

42 ENGINEERING↗

Solving large-scale sparse eigenvalue problems and linear systems of equations for accelerator modeling

The solutions of sparse eigenvalue problems and linear systems constitute one of the key computational kernels in the discretization of partial differential equations for the modeling of linear accelerators. The computational challenges faced by existing techniques for solving those sparse eigenvalue problems and linear systems call for continuing research to improve on the algorithms so that ever increasing problem size as required by the physics application can be tackled. Under the support of this award, the filter algorithm for solving large sparse eigenvalue problems was developed at Stanford to address the computational difficulties in the previous methods with the goal to enable accelerator simulations on then the world largest unclassified supercomputer at NERSC for this class of problems. Specifically, a new method, the Hemitian skew-Hemitian splitting method, was proposed and researched as an improved method for solving linear systems with non-Hermitian positive definite and semidefinite matrices.

43 PARTICLE ACCELERATORS↗

Standard Problems for CFD Validation for NGNP - Status Report

The U.S. Department of Energy (DOE) is conducting research and development to support the resurgence of nuclear power in the United States for both electrical power generation and production of process heat required for industrial processes such as the manufacture of hydrogen for use as a fuel in automobiles. The project is called the Next Generation Nuclear Plant (NGNP) Project, which is based on a Generation IV reactor concept called the very high temperature reactor (VHTR). The VHTR will be of the prismatic or pebble bed type; the former is considered herein. The VHTR will use helium as the coolant at temperatures ranging from 250°C to perhaps 1000°C. While computational fluid dynamics (CFD) has not previously been used for the safety analysis of nuclear reactors in the United States, it is being considered for existing and future reactors. It is fully recognized that CFD simulation codes will have to be validated for flow physics reasonably close to actual fluid dynamic conditions expected in normal operational and accident situations. The “Standard Problem” is an experimental data set that represents an important physical phenomenon or phenomena, whose selection is based on a phenomena identification and ranking table (PIRT) for the reactor in question. It will be necessary to build a database that contains a number of standard problems for use to validate CFD and systems analysis codes for the many physical problems that will need to be analyzed. The first two standard problems that have been developed for CFD validation consider flow in the lower plenum of the VHTR and bypass flow in the prismatic core. Both involve scaled models built from quartz and designed to be installed in the INL’s matched index of refraction (MIR) test facility. The MIR facility employs mineral oil as the working fluid at a constant temperature. At this temperature, the index of refraction of the mineral oil is the same as that of the quartz. This provides an advantage to the optics used for data gathering. Particle image velocimetry (PIV) is used to take the data. The first standard problem represents several flow physics expected to be present in the lower plenum of the prismatic VHTR. In the lower plenum, heated helium coolant in the form of jets issues downward into the plenum and is then forced to turn ninety degrees and flow toward the exit duct. The lower plenum is filled with cylindrical graphite posts that hold up the core. Figure S-1 provides a plan view of the lower plenum. The red circles represent support posts holding up columns of heated blocks. Grey circles represent support posts under columns of reflector blocks. Helium enters the lower plenum at the junctions of the hexagonal blocks.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem

The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.

97 MATHEMATICS AND COMPUTING↗

Scientific machine learning for closure models in multiscale problems: A review

Here, closure problems are omnipresent when simulating multiscale systems, where some quantities and processes cannot be fully prescribed despite their effects on the simulation's accuracy. Recently, scientific machine learning approaches have been proposed as a way to tackle the closure problem, combining traditional (physics-based) modeling with data-driven (machine-learned) techniques, typically through enriching differential equations with neural networks. This paper reviews the different reduced model forms, distinguished by the degree to which they include known physics, and the different objectives of a priori and a posteriori learning. The importance of adhering to physical laws (such as symmetries and conservation laws) in choosing the reduced model form and choosing the learning method is discussed. The effect of spatial and temporal discretization and recent trends toward discretization-invariant models are reviewed. In addition, we make the connections between closure problems and several other research disciplines: inverse problems, Mori-Zwanzig theory, and multi-fidelity methods. In conclusion, much progress has been made with scientific machine learning approaches for solving closure problems, but many challenges remain. In particular, the generalizability and interpretability of learned models is a major issue that needs to be addressed further.

97 MATHEMATICS AND COMPUTING↗

Partially Collapsed Gibbs Samplers for Linear Inverse Problems and Applications to X-ray Imaging

Deblurring is one of the most common linear inverse problems in imaging, and most methods for deblurring an image assume that the convolution kernel, the so-called point spread function (PSF), is known or attempt to reconstruct the PSF simultaneously with the image. For many experimental imaging systems, like high energy X-ray radiography systems, the PSF must be computed from calibration imagery. The associated inverse problem is large-scale, so, in order to compute meaningful uncertainties with the reconstruction, it is common to use hierarchical Bayesian models and Markov chain Monte Carlo methods for sampling from the posterior. Classical Gibbs samplers can suffer from long autocorrelation lengths in the Markov chain when the reconstructed quantity in the inverse problem is finely discretized, resulting in poor computational efficiency of the Markov chain. In this work we present partially collapsed Gibbs samplers for linear inverse problems that greatly decrease correlations in the Markov chain, thus increasing the computational efficiency of the algorithms, and we present the results of the enhanced samplers on the problem of reconstructing the point spread function for an X-ray imaging system at the U.S. Department of Energy's Nevada National Security Site.

97 MATHEMATICS AND COMPUTING↗

Investigating the Chinese postman problem on a quantum annealer

The recent availability of quantum annealers has fueled a new area of information technology where such devices are applied to address practically motivated and computationally difficult problems with hardware that exploits quantum mechanical phenomena. D-Wave annealers are promising platforms to solve these problems in the form of quadratic unconstrained binary optimization. Here we provide a formulation of the Chinese postman problem that can be used as a tool for probing the local connectivity of graphs and networks. We treat the problem classically with a tabu algorithm and simulated annealing, and using a D-Wave device. The efficiency of quantum annealing with respect to the simulated annealing has been demonstrated using the optimal time to solution metric. We systematically analyze computational parameters associated with the specific hardware. Our results clarify how the interplay between the embedding due to limited connectivity of the Chimera graph, the definition of logical qubits, and the role of spin-reversal controls the probability of reaching the expected solution

36 MATERIALS SCIENCE↗

Algorithm to solve a chance-constrained network capacity design problem with stochastic demands and finite support

Here, we consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real-world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum-cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance-constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user-defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut-sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches.

97 MATHEMATICS AND COMPUTING↗

Quantum Annealing with Inequality Constraints: The Set Cover Problem

Abstract Quantum annealing is a promising method for solving hard optimization problems by transforming them into quadratic unconstrained binary optimization (QUBO) problems. However, when constraints are involved, particularly multiple inequality constraints, incorporating them into the objective function poses challenges. In this paper, the authors present two novel approaches for solving problems with multiple inequality constraints on a quantum annealer and apply them to the set cover problem (SCP). The first approach uses the augmented Lagrangian method to represent the constraints, while the second approach employs a higher‐order binary optimization (HUBO) formulation. The experiments show that both approaches outperform the standard approach for solving the SCP on the D‐Wave Advantage quantum annealer. The HUBO formulation performs slightly better than the augmented Lagrangian method in solving the SCP, but its scalability in terms of embeddability in the quantum chip is worse. The results demonstrate that the proposed augmented Lagrangian and HUBO methods can successfully implement a large number of inequality constraints, making them applicable to a broad range of constrained problems beyond the SCP.

Djidjev, Hristo N.↗

Properties of definite Bethe–Salpeter eigenvalue problems

The Bethe-Salpeter eigenvalue problem is solved in condensed matter physics to estimate the absorption spectrum of solids. It is a structured eigenvalue problem. Its special structure appears in other approaches for studying electron excitation in molecules or solids also. When the Bethe-Salpeter Hamiltonian matrix is definite, the corresponding eigenvalue problem can be reduced to a symmetric eigenvalue problem. However, its special structure leads to a number of interesting spectral properties. We describe these properties that are crucial for developing efficient and reliable numerical algorithms for solving this class of problems.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Spectral Solutions of Self-adjoint Elliptic Problems with Immersed Interfaces

This paper describes a spectral representation of solutions of self-adjoint elliptic problems with immersed interfaces. The interface is assumed to be a simple non-self-intersecting closed curve that obeys some weak regularity conditions. The problem is decomposed into two problems, one with zero interface data and the other with zero exterior boundary data. The problem with zero interface data is solved by standard spectral methods. The problem with non-zero interface data is solved by introducing an interface space H{sub {Gamma}}({Omega}) and constructing an orthonormal basis of this space. This basis is constructed using a special class of orthogonal eigenfunctions analogously to the methods used for standard trace spaces by Auchmuty (SIAM J. Math. Anal. 38, 894-915, 2006). Analytical and numerical approximations of these eigenfunctions are described and some simulations are presented.

97 MATHEMATICS AND COMPUTING↗

Resolvent-Techniques for Multiple Exercise Problems

We study optimal multiple stopping of strong Markov processes with random refraction periods. The refraction periods are assumed to be exponentially distributed with a common rate and independent of the underlying dynamics. Our main tool is using the resolvent operator. In the first part, we reduce infinite stopping problems to ordinary ones in a general strong Markov setting. This leads to explicit solutions for wide classes of such problems. Starting from this result, we analyze problems with finitely many exercise rights and explain solution methods for some classes of problems with underlying Lévy and diffusion processes, where the optimal characteristics of the problems can be identified more explicitly. We illustrate the main results with explicit examples.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Identification of the Diffusion Parameter in Nonlocal Steady Diffusion Problems

The problem of identifying the diffusion parameter appearing in a nonlocal steady diffusion equation is considered. The identification problem is formulated as an optimal control problem having a matching functional as the objective of the control and the parameter function as the control variable. The analysis makes use of a nonlocal vector calculus that allows one to define a variational formulation of the nonlocal problem. In a manner analogous to the local partial differential equations counterpart, we demonstrate, for certain kernel functions, the existence of at least one optimal solution in the space of admissible parameters. We introduce a Galerkin finite element discretization of the optimal control problem and derive a priori error estimates for the approximate state and control variables. Using one-dimensional numerical experiments, we illustrate the theoretical results and show that by using nonlocal models it is possible to estimate non-smooth and discontinuous diffusion parameters.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Simulation of mineral dissolution at the pore scale with evolving fluid-solid interfaces: review of approaches and benchmark problem set

This manuscript presents a benchmark problem for the simulation of single-phase flow, reactive transport, and solid geometry evolution at the pore scale. The problem is organized in three parts that focus on specific aspects: flow and reactive transport (part I), dissolution-driven geometry evolution in two dimensions (part II), and an experimental validation of three-dimensional dissolution-driven geometry evolution (part III). Five codes are used to obtain the solution to this benchmark problem, including Chombo-Crunch, OpenFOAM-DBS, a lattice Boltzman code, Vortex, and dissolFoam. These codes cover a good portion of the wide range of approaches typically employed for solving pore-scale problems in the literature, including discretization methods, characterization of the fluid-solid interfaces, and methods to move these interfaces as a result of fluid-solid reactions. A short review of these approaches is given in relation to selected published studies. Results from the simulations performed by the five codes show remarkable agreement both quantitatively--based on upscaled parameters such as surface area, solid volume, and effective reaction rate--and qualitatively--based on comparisons of shape evolution. This outcome is especially notable given the disparity of approaches used by the codes. Therefore, these results establish a strong benchmark for the validation and testing of pore-scale codes developed for the simulation of flow and reactive transport with evolving geometries. They also underscore the significant advances seen in the last decade in tools and approaches for simulating this type of problem.

58 GEOSCIENCES↗

On Bellman’s and Knuth’s Problems and their Generalizations

Various generalizations of the classical problem of the fastest raising to a power (or the so-called problem on addition chains) are studied in the asymptotic sense. Under weak restrictions, we demonstrate asymptotically tight solutions of the two best known generalizations, namely, Bellman’s problem on the computational complexity (on the minimal number of multiplication operations) of a normed monomial of several variables and Knuth’s problem on the computational complexity of a power system of one variable. We also briefly review some results on the computational complexity for three problems, namely, the computation of p-element systems of normed monomials in q variables, additive computations for systems of p integer linear forms over q variables, and the computation of p-element systems of the free Abelian group with q generators.

97 MATHEMATICS AND COMPUTING↗

An efficient cost reduction procedure for bounded-control LQR problems

A novel approach has been developed for approximating the solution to the constrained LQR problem, based on updating the final state and costate of a related regular problem, and on slightly shifting the switching times (the instants when the control meets the constraints). The main result is the expression of a suboptimal control in feedback form using the solution of some compatible Riccati equation. The gradient method is applied to reduce the cost via explicit algebraic formula for its partial derivatives with respect to the hidden final state/costate of the related regular problem and to the switching times. The numerical method is termed efficient because it does not involve integrations of states or cost trajectories, and reduces to its minimum the dimension of the unknown parameters at the final condition. All the relevant objects are calculated from a few auxiliary matrices, which are computed only once. The scheme is here applied to two case studies whose optimal solutions are known. The first example is a two-dimensional model of the ‘cheapest stop of a train’ problem. The second one refers to the temperature control of a metallic strip leaving a multi-stand rolling mill, a problem with a high-dimensional state.

97 MATHEMATICS AND COMPUTING↗

A way to optimally solve a green time-dependent vehicle routing problem with time windows

This study presents a novel approach to solve the vehicle routing problem by focusing on greenhouse gas emissions and fuel consumption aiming to mitigate adverse environmental effects of transportation. A time-dependent model with time windows is developed to incorporate speed and schedule in transportation planning. The model considers speed limits for different times of the day in a realistic delivery context. Due to the complexity of solving the model, a graph transformation approach is proposed to reduce the complexity of the problem. By means of several steps, the problem is transformed into a vehicle routing problem without time windows. In this way, we can reduce the complexity of the problem. Our method can be used in practice to decrease fuel consumption and greenhouse gas emissions, while total cost is also controlled to some extent. Finally, future research directions and conclusion remarks are provided.

54 ENVIRONMENTAL SCIENCES↗