Search NASA⌕ Search

SEARCH · Search NASA

Results for “linear programming 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 289 records · Page 16

Koopman Model Predictive Control for Eco-Driving of Automated Vehicles

In this paper, we develop a data-driven process for building a model predictive control (MPC) for eco-driving of automated vehicles. The process involves performing system identification in which the non-linear vehicle dynamics model is approximated by the Koopman operator, a linear predictor of higher state-dimension, in a data-driven framework. This approach allows us to formulate the eco-driving problem in a constrained quadratic program that leads to a computationally fast MPC. The MPC is then implemented as a closed-loop control of an electric vehicle in numerical simulations for demonstration.

autonomous vehicle↗

Control of Fractional Diffusion Problems via Dynamic Programming Equations

In this study, we explore the approximation of feedback control of integro-differential equations containing a fractional Laplacian term. To obtain feedback control for the state variable of this nonlocal equation, we use the Hamilton–Jacobi–Bellman equation. It is well known that this approach suffers from the curse of dimensionality, and to mitigate this problem we couple semi-Lagrangian schemes for the discretization of the dynamic programming principle with the use of Shepard approximation. This coupling enables approximation of high-dimensional problems. Numerical convergence toward the solution of the continuous problem is provided together with linear and nonlinear examples. The robustness of the method with respect to disturbances of the system is illustrated by comparisons with an open-loop control approach.

97 MATHEMATICS AND COMPUTING↗

Decentralized Low-Rank State Estimation for Power Distribution Systems

This article considers the low-observability state estimation problem in power distribution networks and develops a decentralized state estimation algorithm leveraging the matrix completion methodology. Matrix completion has been shown to be an effective technique in state estimation that exploits the low dimensionality of the power system measurements to recover missing information. This technique can utilize an approximate (linear) load flow model, or it can be used with no physical models in a network where no information about the topology or line admittance is available. The direct application of matrix completion algorithms requires solving a semi-definite programming (SDP) problem, which becomes computationally challenging for large networks. We therefore develop a decentralized algorithm that capitalizes on the popular proximal alternating direction method of multipliers (proximal ADMM). The method allows us to distribute the computation among different areas of the network, leading to a scalable algorithm. By doing all computations at individual control areas and only communicating with neighboring areas, the algorithm eliminates the need for data to be sent to a central processing unit and thus increases efficiency and contributes to the goal of autonomous control of distribution networks. We illustrate the advantages of the proposed algorithm numerically using standard IEEE test cases.

41 EE - Solar Energy Technologies Office (EE-4S)↗

Sequential Linearization Method for Bound-Constrained Mathematical Programs with Complementarity Constraints

Here, we propose an algorithm for solving bound-constrained mathematical programs with complementarity constraints on the variables. Each iteration of the algorithm involves solving a linear program with complementarity constraints in order to obtain an estimate of the active set. The algorithm enforces descent on the objective function to promote global convergence to B-stationary points. We provide a convergence analysis and preliminary numerical results on a range of test problems. We also study the effect of fixing the active constraints in a bound-constrained quadratic program that can be solved on each iteration in order to obtain fast convergence.

97 MATHEMATICS AND COMPUTING↗

Stochastic Unit Commitment: Model Reduction via Learning

As weather-dependent renewable generation increases its share in the generation mix of most electric energy systems, a stochastic unit commitment becomes the natural day-ahead scheduling tool. However, such a tool is generally computationally intractable if a detailed uncertainty description is considered. Taking this into account, we proposed a learning method to make the stochastic unit commitment problem tractable. Here, recent advances in statistical learning and machine learning to address optimization problems can be advantageously applied to the rather intractable stochastic unit commitment problem. Considering these advances, we explore simple learning techniques to drastically reduce the size of a stochastic unit commitment problem without significantly altering its optimal solution. The considered stochastic unit commitment problem is formulated as a two-stage stochastic programming problem. The first stage represents commitment decisions, while the second one represents the operation conditions under different scenarios. Taking into account historical solved instances (or proxies for them), we reduce the size (measured by numbers of constraints and variables) of the stochastic unit commitment problem by (i) fixing unchanged binary variables and by (ii) eliminating inactive inequality constraints. Our numerical results show that the reduced problem generally requires significantly less time to solve while obtaining high-quality solutions, which are very close to or indistinguishable from the one obtained by solving the original problem. We use an Illinois 200-bus system to illustrate and characterize the performance of the proposed problem-reduction method.

42 ENGINEERING↗

SU-F-BRD-08: Guaranteed Epsilon-Optimal Treatment Plans with Minimum Number of Beams for SBRT Using RayStation

Purpose: To efficiently find quality-guaranteed treatment plans with the minimum number of beams for stereotactic body radiation therapy using RayStation. Methods: For a pre-specified pool of candidate beams we use RayStation (a treatment planning software for clinical use) to identify the deliverable plan which uses all the beams with the minimum dose to organs at risk (OARs) and dose to the tumor and other structures in specified ranges. Then use the dose matrix information for the generated apertures from RayStation to solve a linear program to find the ideal plan with the same objective and constraints allowing use of all beams. Finally we solve a mixed integer programming formulation of the beam angle optimization problem (BAO) with the objective of minimizing the number of beams while remaining in a predetermined epsilon-optimality of the ideal plan with respect to the dose to OARs. Since the treatment plan optimization is a multicriteria optimization problem, the planner can exploit the multicriteria optimization capability of RayStation to navigate the ideal dose distribution Pareto surface and select a plan of desired target coverage versus OARs sparing, and then use the proposed technique to reduce the number of beams while guaranteeing quality. For the numerical experiments two liver cases and one lung case with 33 non-coplanar beams are considered. Results: The ideal plan uses an impractically large number of beams. The proposed technique reduces the number of beams to the range of practical application (5 to 9 beams) while remaining in the epsilon-optimal range of 1% to 5% optimality gap. Conclusion: The proposed method can be integrated into a general algorithm for fast navigation of the ideal dose distribution Pareto surface and finding the treatment plan with the minimum number of beams, which corresponds to the delivery time, in epsilon-optimality range of the desired ideal plan. The project was supported by the Federal Share of program income earned by Massachusetts General Hospital on C06 CA059267, Proton Therapy Research and Treatment Center and partially by RaySearch Laboratories.

60 APPLIED LIFE SCIENCES↗

McCormick envelopes in mixed-integer PDE-constrained optimization

McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state constraints that may be difficult to handle) in addition to the state equation for a pointwise formulation of the McCormick envelopes and renders bound-tightening procedures that successively improve the resulting convex relaxations computationally intractable. We analyze McCormick envelopes for a model problem class that is governed by a semilinear PDE involving a bilinearity and integrality constraints. We approximate the nonlinearity and in turn the McCormick envelopes by averaging the involved terms over the cells of a partition of the computational domain on which the PDE is defined. This yields convex relaxations that underestimate the original problem up to an a priori error estimate that depends on the mesh size of the discretization. These approximate McCormick relaxations can be improved by means of an optimization-based bound-tightening procedure. We show that their minimizers converge to minimizers to a limit problem with a pointwise formulation of the McCormick envelopes when driving the mesh size to zero. We provide a computational example, for which we certify all of our imposed assumptions. The results point to both the potential of the methodology and the gaps in the research that need to be closed. Our methodology provides a framework first for obtaining pointwise underestimators for nonconvexities and second for approximating them with finitely many linear inequalities in an infinite-dimensional setting.

Approximations and Expansions↗

3D numerical simulation of the long range propagation of acoustical shock waves through a heterogeneous and moving medium

Many situations involve the propagation of acoustical shock waves through flows. Natural sources such as lightning, volcano explosions, or meteoroid atmospheric entries, emit loud, low frequency, and impulsive sound that is influenced by atmospheric wind and turbulence. The sonic boom produced by a supersonic aircraft and explosion noises are examples of intense anthropogenic sources in the atmosphere. The Buzz-Saw-Noise produced by turbo-engine fan blades rotating at supersonic speed also propagates in a fast flow within the engine nacelle. Simulating these situations is challenging, given the 3D nature of the problem, the long range propagation distances relative to the central wavelength, the strongly nonlinear behavior of shocks associated to a wide-band spectrum, and finally the key role of the flow motion. With this in view, the so-called FLHOWARD (acronym for FLow and Heterogeneous One-Way Approximation for Resolution of Diffraction) method is presented with three-dimensional applications. A scalar nonlinear wave equation is established in the framework of atmospheric applications, assuming weak heterogeneities and a slow wind. It takes into account diffraction, absorption and relaxation properties of the atmosphere, quadratic nonlinearities including weak shock waves, heterogeneities of the medium in sound speed and density, and presence of a flow (assuming a mean stratified wind and 3D turbulent ? flow fluctuations of smaller amplitude). This equation is solved in the framework of the one-way method. A split-step technique allows the splitting of the non-linear wave equation into simpler equations, each corresponding to a physical effect. Each sub-equation is solved using an analytical method if possible, and finite-differences otherwise. Nonlinear effects are solved in the time domain, and others in the frequency domain. Homogeneous diffraction is handled by means of the angular spectrum method. Ground is assumed perfectly flat and rigid. Due to the 3D aspect, the code was massively parallelized using the single program, multiple data paradigm with the Message Passing Interfaces (MPI) for distributed memory architectures. This allows us to handle problems in the order of a thousand billion mesh points in the four dimensions (3 dimensions of space plus time). The validity of the method has been thoroughly evaluated on many cases with known solutions: linear piston, scattering of plane wave by a heterogeneous sphere, propagation in a waveguide with a shear flow, scattering by a finite amplitude vortex and nonlinear propagation in a thermoviscous medium. This validation process allows for a detailed assessment of the advantages and limitations of the method. Finally, applications to atmospheric propagation of shock waves will be presented.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Multi-Stage Stochastic Programming to Joint Economic Dispatch for Energy and Reserve With Uncertain Renewable Energy

To address the uncertain renewable energy in the day-ahead optimal dispatch of energy and reserve, a multi-stage stochastic programming model is established in this paper to minimize the expected total costs. The uncertainties over the multiple stages are characterized by a scenario tree and the optimal dispatch scheme is cast as a decision tree which guarantees the flexibility to decide the reasonable outputs of generation and the adequate reserves accounting for different realizations of renewable energy. Most importantly, to deal with the “Curse of Dimensionality” of stochastic programming, stochastic dual dynamic programming (SDDP) is employed, which decomposes the original problem into several sub-problems according to the stages. Specifically, the SDDP algorithm performs forward pass and backward pass repeatedly until the convergence criterion is satisfied. At each iteration, the original problem is approximated by creating a linear piecewise function. Besides, an improved convergence criterion is adopted to narrow the optimization gaps. The results on the IEEE 118-bus system and real-life provincial power grid show the effectiveness of the proposed model and method.

economic dispatch↗

A preconditioning technique for Schur complement systems arising in stochastic optimization

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time.

99 GENERAL AND MISCELLANEOUS↗

Evaluating demand response opportunities for power systems resilience using MILP and MINLP Formulations

While peak shaving is commonly used to reduce power costs, chemical process facilities that can reduce power consumption on demand during emergencies (e.g., extreme weather events) bring additional value through improved resilience. For process facilities to effectively negotiate demand response (DR) contracts and make investment decisions regarding flexibility, they need to quantify their additional value to the grid. We present a grid–centric mixed–integer stochastic programming framework to determine the value of DR for improving grid resilience in place of capital investments that can be cost prohibitive for system operators. We formulate problems using both a linear approximation and a nonlinear alternating current power flow model. Our numerical results with both models demonstrate that DR can be used to reduce the capital investment necessary for resilience, increasing the value that chemical process facilities bring through DR. Furthermore, the linearized model often underestimates the amount of DR needed in our case studies.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Steps toward fault-tolerant quantum chemistry.

Developing quantum chemistry programs on the coming generation of exascale computers will be a difficult task. The programs will need to be fault-tolerant and minimize the use of global operations. This work explores the use a task-based model that uses a data-centric approach to allocate work to different processes as it applies to quantum chemistry. After introducing the key problems that appear when trying to parallelize a complicated quantum chemistry method such as coupled-cluster theory, we discuss the implications of that model as it pertains to the computational kernel of a coupled-cluster program - matrix multiplication. Also, we discuss the extensions that would required to build a full coupled-cluster program using the task-based model. Current programming models for high-performance computing are fault-intolerant and use global operations. Those properties are unsustainable as computers scale to millions of CPUs; instead one must recognize that these systems will be hierarchical in structure, prone to constant faults, and global operations will be infeasible. The FAST-OS HARE project is introducing a scale-free computing model to address these issues. This model is hierarchical and fault-tolerant by design, allows for the clean overlap of computation and communication, reducing the network load, does not require checkpointing, and avoids the complexity of many HPC runtimes. Development of an algorithm within this model requires a change in focus from imperative programming to a data-centric approach. Quantum chemistry (QC) algorithms, in particular electronic structure methods, are an ideal test bed for this computing model. These methods describe the distribution of electrons in a molecule, which determine the properties of the molecule. The computational cost of these methods is high, scaling quartically or higher in the size of the molecule, which is why QC applications are major users of HPC resources. The complexity of these algorithms means that MPI alone is insufficient to achieve parallel scaling; QC developers have been forced to use alternative approaches to achieve scalability and would be receptive to radical shifts in the programming paradigm. Initial work in adapting the simplest QC method, Hartree-Fock, to this the new programming model indicates that the approach is beneficial for QC applications. However, the advantages to being able to scale to exascale computers are greatest for the computationally most expensive algorithms; within QC these are the high-accuracy coupled-cluster (CC) methods. Parallel coupledcluster programs are available, however they are based on the conventional MPI paradigm. Much of the effort is spent handling the complicated data dependencies between the various processors, especially as the size of the problem becomes large. The current paradigm will not survive the move to exascale computers. Here we discuss the initial steps toward designing and implementing a CC method within this model. First, we introduce the general concepts behind a CC method, focusing on the aspects that make these methods difficult to parallelize with conventional techniques. Then we outline what is the computational core of the CC method - a matrix multiply - within the task-based approach that the FAST-OS project is designed to take advantage of. Finally we outline the general setup to implement the simplest CC method in this model, linearized CC doubles (LinCC).

99 GENERAL AND MISCELLANEOUS↗

On the Design, Development, and Analysis of Optimized Matrix-Vector Multiplication Routines for Coprocessors

The manycore paradigm shift, and the resulting change in modern computer architectures, has made the development of optimal numerical routines extremely challenging. In this work, we target the development of numerical algorithms and implementations for Xeon Phi coprocessor architecture designs. In particular, we examine and optimize the general and symmetric matrix-vector multiplication routines (gemv/symv), which are some of the most heavily used linear algebra kernels in many important engineering and physics applications. We describe a successful approach on how to address the challenges for this problem, starting with our algorithm design, performance analysis and programing model and moving to kernel optimization. Our goal, by targeting low-level and easy to understand fundamental kernels, is to develop new optimization strategies that can be effective elsewhere for use on manycore coprocessors, and to show significant performance improvements compared to existing state-of-the-art implementations. Therefore, in addition to the new optimization strategies, analysis, and optimal performance results, we finally present the significance of using these routines/strategies to accelerate higher-level numerical algorithms for the eigenvalue problem (EVP) and the singular value decomposition (SVD) that by themselves are foundational for many important applications.

Kabir, Khairul↗

Optimal Power Flow in Multiphase Radial Networks with Delta Connections: Preprint

This paper focuses on multiphase radial distribution networks with mixed wye and delta connections, and proposes a semidefinite relaxation of the AC optimal power flow (OPF) problem. Two multiphase power-flow models are developed to facilitate the integration of delta-connected generation units/loads in the OPF problem. The first model extends traditional branch flow models - and it is referred to as extended branch flow model (EBFM). The second model leverages a linear relationship between per-phase power injections and delta connections, which holds under a balanced voltage approximation (BVA). Based on these models, pertinent OPF problems are formulated and relaxed to semidefinite programs (SDPs). Numerical studies on IEEE test feeders show that SDP relaxations can be solved efficiently by a generic optimization solver. Numerical evidences indicate that solving the resultant SDP under BVA is faster than under EBFM. Moreover, both SDP solutions are numerically exact with respect to voltages and branch flows. It is also shown that the SDP solution under BVA has a small optimality gap, while the BVA model is accurate in the sense that it reflects actual system voltages.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Real-time dispatch optimization for concentrating solar power with thermal energy storage

Concentrating solar power (CSP) plants present a promising path towards utility-scale renewable energy. The power tower, or central receiver, configuration can achieve higher operating temperatures than other forms of CSP, and, like all forms of CSP, naturally pairs with comparatively inexpensive thermal energy storage, which allows CSP plants to dispatch electricity according to market price incentives and outside the hours of solar resource availability. Currently, CSP plants commonly include a steam Rankine power cycle and several heat exchange components to generate high-pressure steam using stored thermal energy. The efficiency of the steam Rankine cycle depends on the temperature of the plant's operating fluid, and so is a main concern of plant operators. However, the variable nature of the solar resource and the conservatism with which the receiver is operated prevent perfect control over the receiver outlet temperature. Therefore, during periods of solar variability, collection occurs at lower-than-design temperature. To support operator decisions in a real-time setting, we develop a revenue-maximizing non-convex mixed-integer, quadradically-constrained program which determines a dispatch schedule with sub-hourly time fidelity and considers temperature-dependent power cycle efficiency. The exact nonlinear formulation proves intractable for real-time decision support. Here we present exact and inexact techniques to improve problem tractability that include a hybrid nonlinear and linear formulation. Our approach admits solutions within approximately 3% of optimality, on average, within a five-minute time limit, demonstrating its usability for decision support in a real-time setting.

14 SOLAR ENERGY↗

Computation of Nonlinear Hydrodynamic Loads on Floating Wind Turbines Using Fluid-Impulse Theory: Preprint

A hydrodynamics computer module was developed for the evaluation of the linear and nonlinear loads on floating wind turbines using a new fluid-impulse formulation for coupling with the FAST program. The recently developed formulation allows the computation of linear and nonlinear loads on floating bodies in the time domain and avoids the computationally intensive evaluation of temporal and nonlinear free-surface problems and efficient methods are derived for its computation. The body instantaneous wetted surface is approximated by a panel mesh and the discretization of the free surface is circumvented by using the Green function. The evaluation of the nonlinear loads is based on explicit expressions derived by the fluid-impulse theory, which can be computed efficiently. Computations are presented of the linear and nonlinear loads on the MIT/NREL tension-leg platform. Comparisons were carried out with frequency-domain linear and second-order methods. Emphasis was placed on modeling accuracy of the magnitude of nonlinear low- and high-frequency wave loads in a sea state. Although fluid-impulse theory is applied to floating wind turbines in this paper, the theory is applicable to other offshore platforms as well.

17 WIND ENERGY↗

Convex Relaxation of OPF in Multiphase Radial Networks with Wye and Delta Connections

This panel presentation focuses on multiphase radial distribution networks with wye and delta connections, and proposes a semidefinite relaxation of the AC optimal power flow (OPF) problem. Two multiphase power flow models are developed to facilitate the integration of delta-connected loads or generation resources in the OPF problem. The first model is referred to as the extended branch flow model (EBFM). The second model leverages a linear relationship between phase-to-ground power injections and delta connections that holds under a balanced voltage approximation (BVA). Based on these models, pertinent OPF problems are formulated and relaxed to semidefinite programs (SDPs). Numerical studies on IEEE test feeders show that the proposed SDP relaxations can be solved efficiently by a generic optimization solver. Numerical evidence also indicates that solving the resultant SDP under BVA is faster than under EBFM. Moreover, both SDP solutions are numerically exact with respect to voltages and branch flows. It is further shown that the SDP solution under BVA has a small optimality gap, and the BVA model is accurate in the sense that it reproduces actual system voltages.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Dispatch optimization of electric thermal energy storage within System Advisor Model

A stand-alone electric thermal energy storage (ETES) system converts low-value electricity into heat using resistance heating elements. During periods of high-value electricity, an ETES system uses a thermodynamic power cycle to convert stored thermal energy back to electricity. These dispatchable systems derive value from their ability to store energy when prices are low and generate electricity when prices are favorable, i.e., energy arbitrage. Consequently, dispatch optimization of system operations, through maximizing revenue subject to system constraints, is essential to evaluate the economic value of a particular system design. While stand-alone ETES systems offer potential advantages as dispatchable grid storage technologies, there is a lack of a neutral third-party, publicly available, open-source model to evaluate the performance, dispatch, and financial viability of these systems. To address this problem, we have developed a techno-economic model for stand-alone ETES systems, within National Renewable Energy Laboratory's (NREL's) System Advisor Model (SAM). We implement a mixed-integer linear program to determine an ETES optimal operating schedule that maximizes electricity sales less maintenance costs caused by operation and cycling given temporal-varying grid electricity prices. Our contributions include a mixed-integer linear program for energy arbitrage of an ETES system, an ETES performance model through a publicly-available software (i.e., SAM), and an exercise of our model through case studies that compare ETES operational strategies and annual financial metrics. With our dispatch optimization model, we were able to improve revenue by 20% compared to a myopic heuristic while reducing the operational cost of the ETES system through decreases in cycle starts, cycles per day, and heater starts.

24 POWER TRANSMISSION AND DISTRIBUTION↗