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 73 records · Page 4

Online Model-Free Chance-Constrained Distribution System Voltage Control Using DERs

This paper proposes an online data-driven distributed energy resource management system (DERMS) optimization method using chance-constrained formulation to address distribution system voltage regulation. This is achieved via the local sensitivity factor (LSF)-enabled reformulation of the DER control into a linear programming (LP) problem, which is easy and computationally efficient to solve. The LSF is estimated using online measurements and does not need the assumption of node load information. The latter is usually required for existing optimization-based methods but is difficult to obtain in practice. To mitigate measurement uncertainties, a scenario-based chance-constrained formulation is constructed. Compared with other control methods, the results carried out in a realistic distribution system show that the proposed method can effectively eliminate voltage violation issues.

chance-constrained optimization↗

Optimal Energy Management for Microgrid with Stationary and Mobile Storage

This paper studies energy management in a Microgrid (MG) with solar generation, Battery Energy Management System (BESS) and gridable (V2G) EVs. A two-stage stochastic optimization method is proposed to capture the intermittent solar generation and random EV user behaviors. It is subsequently formulated as a Mixed Integer Linear Programming (MILP) problem. To evalutate the proposed method, real solar generation, loads, BESS and EV data is used in Sample Average Approximation (SAA). Computational results show the correctness of the proposed method as well as steady and tightly bounded optimality gap. Comparisons demonstrate that the proposed stochastic method outperforms its deterministic counterpart at the expense of higher computational cost. It is also observed that moderate number of EVs helps to reduce the overall operational cost of the MG, which sheds light on future EV integration to the smart grid.

Battery Energy Management System (BESS)↗

A Probabilistic Risk Mitigation Model for Cyber-Attacks to PMU Networks

The power grid is becoming more dependent on information and communication technologies. Complex networks of advanced sensors such as phasor measurement units (PMUs) are used to collect real time data to improve the observability of the power system. Recent studies have shown that the power grid has significant cyber vulnerabilities which could increase when PMUs are used extensively. Therefore, recognizing and responding to vulnerabilities are critical to the security of the power grid. This paper proposes a risk mitigation model for optimal response to cyber-attacks to PMU networks. We model the optimal response action as a mixed integer linear programming (MILP) problem to prevent propagation of the cyber-attacks and maintain the observability of the power system.

Cyber-attack↗

Online Model-Free DER Dispatch Via Adaptive Voltage Sensitivity Estimation and Chance Constrained Programming

This paper proposes an online data-driven distributed energy resource management system (DERMS) for distribution system optimal DER dispatch as well as voltage regulation. Here, the key innovation is to leverage the Local Sensitivity Factor (LSF) for transforming the DER control into a computationally efficient linear programming (LP) problem. By taking real-time measurements, the estimation of LSF eliminates the need for an accurate distribution system model as well as full nodal load information, which is difficult to achieve in practice. A robust recursive least squares method is also developed to ensure the robust estimation of LSF, which is initialized using reasonable values from model-derived LSFs. This allows the system to adapt to changing operational conditions effectively. A scenario-based, chance-constrained framework is further employed to ensure voltage remains within acceptable limits in the presence of measurement and estimation uncertainties. Test results on a real-world, 759-node distribution network located in western Colorado, U.S., validate the effectiveness and robustness of the proposed control approach and demonstrate its superior performance as compared to alternative methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Data-Driven Mean-Corrected Recursive Estimation-Based Optimal DER Dispatch for Distribution System Voltage Control

Recent advances in smart inverters offer opportunities to mitigate adverse grid impacts caused by high penetrations of distributed photovoltaics (PV) in distribution grids, such as voltage violations. Here, this paper proposes a novel measurement-driven optimal power flow (OPF)-based distributed energy resource management system (DERMS) voltage regulation via recursive sensitivity estimation informed coordinated control of distributed PV inverters. The proposed approach leverages available grid and controllable DER measurements, eliminating reliance on system model information while being adaptive and robust to volatile operating conditions. A mean-corrected recursive ridge regression (MCRRR) algorithm is proposed for sensitivity estimation, continuously refining the sensitivity model through a closed-form solution. It effectively manages varying grid operating conditions, such as changes in power injections and topology reconfiguration, to facilitate a time-varying update of the Load Sensitivity Factors (LSF). The proposed approach is formulated as a linear programming (LP) problem and is thus scalable to larger-scale distribution systems. Its effectiveness and efficiency are demonstrated on a realistic distribution feeder with high PV penetrations in Southern California, USA.

14 SOLAR ENERGY↗

DERMS Online: A New Voltage Sensitivity-Enabled Feedback Optimization Framework: Preprint

This paper proposes a distributed energy resource management system (DERMS) solution by developing a new voltage sensitivity enabled feedback optimization framework. The key idea is to adopt a measurement feedback scheme to reformulate the original nonlinear optimization into a linear programming (LP) problem via perturb and observe-based voltage sensitivity analysis. The proposed solution eliminates the dependence on load knowledge and can be implemented online thanks to an efficient open-source solver for LP problems. The proposed DERMS online platform is generalizable to deal with various types of distributed energy resources (DERs), including distributed photovoltaics (PVs), energy storage, electric vehicles, demand response, etc. Comparison results with other control methods on a realistic distribution feeder in Southern California highlight the feasibility as well as benefits for the proposed framework.

distributed energy resources management↗

Online Model-Free Chance-Constrained Distribution System Voltage Control Using DERs: Preprint

This paper proposes an online data-driven distributed energy resource management system (DERMS) optimization method using chance-constrained formulation to address distribution system voltage regulation. This is achieved via the local sensitivity factor (LSF)-enabled reformulation of the DER control into a linear programming (LP) problem, which is easy and computationally efficient to solve. The LSF is estimated using online measurements and does not need the assumption of node load information. The latter is usually required for existing optimization-based methods but is difficult to obtain in practice. To mitigate measurement uncertainties, a scenario-based chance-constrained formulation is constructed. Compared with other control methods, the results carried out in a realistic distribution system show that the proposed method can effectively eliminate voltage violation issues.

chance-constrained optimization↗

QoS-aware edge AI placement and scheduling with multiple implementations in FaaS-based edge computing

Resource constraints on the computing continuum require that we make smart decisions for serving AI-based services at the network edge. AI-based services typically have multiple implementations (e.g., image classification implementations include SqueezeNet, DenseNet, and others) with varying trade-offs (e.g., latency and accuracy). The question then is how should AI-based services be placed across Function-as-a-Service (FaaS) based edge computing systems in order to maximize total Quality-of-Service (QoS). To address this question, we propose a problem that jointly aims to solve (i) edge AI service placement and (ii) request scheduling. These are done across two time-scales (one for placement and one for scheduling). Here we first cast the problem as an integer linear program. We then decompose the problem into separate placement and scheduling subproblems and prove that both are NP-hard. We then propose a novel placement algorithm that places services while considering device-to-device communication across edge clouds to offload requests to one another. Our results show that the proposed placement algorithm is able to outperform a state-of-the-art placement algorithm for AI-based services, and other baseline heuristics, with regard to maximizing total QoS. Additionally, we present a federated learning-based framework, FLIES, to predict the future incoming service requests and their QoS requirements. Our results also show that our FLIES algorithm is able to outperform a standard decentralized learning baseline for predicting incoming requests and show comparable predictive performance when compared to centralized training.

97 MATHEMATICS AND COMPUTING↗

A Bi-Level Formulation And Solution Method For The Integration Of Process Design And Scheduling

Design and operation decisions of manufacturing plants can often be expressed within a hierarchical structure, where optimal decisions at lower operating level provide constraints for the decision raking at a higher decision level. In this work, we are addressing the case of a hierarchical design and scheduling optimization problem. The integration of design and scheduling decisions can play a big role in designing economically profitable plants and improving their operational performance. This problem can be expressed as a bi-level problem, where design related decisions occur at the upper level and operational scheduling decisions at the lower level. Since discrete decisions are involved in both optimization levels, the resulting formulation typically corresponds to bi-level mixed-integer programming problems (B-MIP). The solution of B-MIP problems is very challenging, and typically requires the use of global optimization techniques, with many algorithms not able to guarantee feasibility. To overcome the challenges in solving this class of problems we propose the use of a multi-parametric based algorithm for the solution of bi-level mixed-integer linear and quadratic programming problems, capable of providing the exact and global solution. The main idea of this approach is to treat the lower scheduling problem as a multi-parametric programming problem in which the design decisions are considered as parameters. Here, the resulting parametric solutions can then be substituted into the upper level design problem, which can be solved as a set of single-level deterministic programming problems. Through the developed formulation and algorithm we are able to supply the decision makers with the exact solution of the integrated design and scheduling problem.

42 ENGINEERING↗

Correlative Sparsity in Primal-Dual Interior-Point Methods for LP, SDP, and SOCP

Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in.

97 MATHEMATICS AND COMPUTING↗

Dynamic Ride-Matching for Large-Scale Transportation Systems

Efficient dynamic ride-matching (DRM) in large-scale transportation systems is a key driver in transport simulations to yield answers to challenging problems. Although the DRM problem is simple to solve, it quickly becomes a computationally challenging problem in large-scale transportation system simulations. Therefore, this study thoroughly examines the DRM problem dynamics and proposes an optimization-based solution framework to solve the problem efficiently. To benefit from parallel computing and reduce computational times, the problem’s network is divided into clusters utilizing a commonly used unsupervised machine learning algorithm along with a linear programming model. Then, these sub-problems are solved using another linear program to finalize the ride-matching. At the clustering level, the framework allows users adjusting cluster sizes to balance the trade-off between the computational time savings and the solution quality deviation. A case study in the Chicago Metropolitan Area, U.S., illustrates that the framework can reduce the average computational time by 58% at the cost of increasing the average pick up time by 26% compared with a system optimum, that is, non-clustered, approach. Another case study in a relatively small city, Bloomington, Illinois, U.S., shows that the framework provides quite similar results to the system-optimum approach in approximately 62% less computational time.

33 ADVANCED PROPULSION SYSTEMS↗

Modeling the AC Power Flow Equations with Optimally Compact Neural Networks: Application to Unit Commitment

Nonlinear power flow constraints render a variety of power system optimization problems computationally intractable. Emerging research shows, however, that the nonlinear AC power flow equations can be successfully modeled using neural networks. These neural networks can be exactly transformed into mixed integer linear programs and embedded inside challenging optimization problems, thus replacing nonlinearities that are intractable for many applications with tractable piecewise linear approximations. Such approaches, though, suffer from an explosion of the number of binary variables needed to represent the neural network. Accordingly, this paper develops a technique for training an "optimally compact'' neural network, i.e., one that can represent the power flow equations with a sufficiently high degree of accuracy while still maintaining a tractable number of binary variables. We demonstrate the use of this neural network as an approximator of the nonlinear power flow equations by embedding it in the AC unit commitment problem, transforming the problem from a mixed integer nonlinear program into a more manageable mixed integer linear program. We use the 14-, 57-, and 89-bus networks as test cases and compare the AC-feasibility of commitment decisions resulting from the neural network, DC, and linearized power flow approximations. Our results show that the neural network model outperforms both the DC and linearized power flow approximations when embedded in the unit commitment problem. The neural network formulation most often selects a feasible unit commitment schedule, and furthermore, it only s

AC power flow↗

Better relaxations of classical discrete optimization problems.

A mathematical program is an optimization problem expressed as an objective function of multiple variables subject to set of constraints. When the optimization problem has specific structure, the problem class usually has a special name. A linear program is the optimization of a linear objective function subject to linear constraints. An integer program is a linear program where some of the variables must take only integer values. A semidefinite program is a linear program where the variables are arranged in a matrix and for all feasible solutions, this matrix must be positive semidefinite. There are general-purpose solvers for each of these classes of mathematical program. There are usually many ways to express a problem as a correct, say, linear program. However, equivalent formulations can have significantly different practical tractability. In this poster, we present new formulations for two classic discrete optimization problems, maximum cut (max cut) and the graphical traveling salesman problem (GTSP), that are significantly stronger, and hence more computationally tractable, than any previous formulations of their class. Both partially answer longstanding open theoretical questions in polyhedral combinatorics.

99 GENERAL AND MISCELLANEOUS↗

Utilising demand response for distribution service restoration to achieve grid resiliency against natural disasters

The increased frequency of power outages due to natural disasters in recent years has highlighted the urgency of enhancing distribution grid resilience. The effective distribution service restoration (DSR) is an important measure for a resilient distribution grid. In this work, the authors demonstrate that DSR can be significantly improved by leveraging the flexibility provided by the inclusion of demand response (DR). The authors propose a framework for this by considering integrated control of household-level flexible appliances to vary the load demand at the distribution-grid level to improve DSR. The overall framework of the proposed system is modelled as a three-step method considering three optimization problems to (i) calculate feasible controllable aggregated load range for each bus, (ii) determine candidate buses to perform DR and their target load demand, and (iii) maintain the load level in each house through home energy management during the DSR, considering uncertainties in load and solar generation sequentially. The optimization problems are formulated as linear programming, mixed-integer linear programming, and multistage stochastic programming (solved using the stochastic dual dynamic programming) models. Finally, case studies performed in the IEEE 123-node test feeder show improvements in resilience in terms of energy restored compared to the restoration process without DR.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Generating moment matching scenarios using optimization techniques

An optimization based method is proposed to generate moment matching scenarios for numerical integration and its use in stochastic programming. The main advantage of the method is its flexibility: it can generate scenarios matching any prescribed set of moments of the underlying distribution rather than matching all moments up to a certain order, and the distribution can be defined over an arbitrary set. This allows for a reduction in the number of scenarios and allows the scenarios to be better tailored to the problem at hand. The method is based on a semi-infinite linear programming formulation of the problem that is shown to be solvable with polynomial iteration complexity. A practical column generation method is implemented. The column generation subproblems are polynomial optimization problems; however, they need not be solved to optimality. It is found that the columns in the column generation approach can be efficiently generated by random sampling. The number of scenarios generated matches a lower bound of Tchakaloff's. The rate of convergence of the approximation error is established for continuous integrands, and an improved bound is given for smooth integrands. Extensive numerical experiments are presented in which variants of the proposed method are compared to Monte Carlo and quasi-Monte Carlo methods on both numerical integration problems and stochastic optimization problems. The benefits of being able to match any prescribed set of moments, rather than all moments up to a certain order, is also demonstrated using optimization problems with 100-dimensional random vectors. Here, empirical results show that the proposed approach outperforms Monte Carlo and quasi-Monte Carlo based approaches on the tested problems.

97 MATHEMATICS AND COMPUTING↗

SU-C-202-01: Incorporating Time-Dependent Hypoxia in IMRT Planning

Purpose: To incorporate uncertainties in oxygenation of tumor cells into radiation therapy planning via robust optimization. The model is demonstrated using a clinical prostate cancer case. Methods: The tumor oxygenation levels are determined based on pre- and mid-treatment PET scans. To account for oxygenation changes, we use a radio-sensitivity factor for the effective dose necessary to treat hypoxic cells. Due to the unpredictable nature of re-oxygenation of hypoxic cells, the radio-sensitivity factor and its change is modeled to reside in a time-dependent uncertainty set. This uncertainty can adapt to both pre- and mid-treatment scans, resulting in a two-stage robust treatment planning model. We develop a robust counterpart reformulation that transforms the original NP-hard problem into a linear program consisting of finitely many linear constraints, which can be solved efficiently. Results: The robust plan is compared to both the corresponding fractionated plan which ignores hypoxia, and to the commonly practiced dose-escalated plan that uniformly increases dose based on initial oxygen concentrations. For PTV, the robust plan improves D{sub 50}, D{sub 95}, and EUD by 4% on average compared to fractionated, and by 11% compared to the optimal escalated plan. Moreover, the robust plan spared organs at risk similar to the fractionated plan, while the escalated plan led to over 170% increase of Bladder D{sub 30}. Conclusion: The proposed robust adaptive model can improve tumor coverage by increasing dose to hypoxic tumor voxels that is overlooked by common fractionated treatments. In addition, the robust model anticipates the re-oxygenation process, thus reducing the excess dose at later fractions in comparison to uniform dose-escalation methods.

60 APPLIED LIFE SCIENCES↗

Optimal Mitigation Planning For Adversarial Scenarios

We propose a generalized framework which performs an optimal partitioning of a limited budget into various organizational sectors in order to improve the cybersecurity of a smart device or component in the Cyber Physical Energy System (CPS). The framework identifies the adversarial threats and possible attack sequences which can be performed to exploit cyber vulnerabilities of the component. Thereafter, we formulate an Mixed Integer Linear Programming (MILP) optimization problem which aims to evaluate the optimal budget partitions in order to minimize the number of highly likely attack sequences. Though we provide results for using the framework in CPES, the proposed methodology can be extended for multiple domains with a set of known adversarial and mitigation actions.

Purohit, Sumit [Pacific Northwest National Laborat↗

The allocation of a variable series reactor considering AC constraints and contingencies

The Variable Series Reactors (VSRs) can efficiently control the power flow through the adjustment of the line reactance. When they are appropriately allocated in the power network, the transmission congestion and generation cost can be reduced. Our work proposes a planning model to optimally allocate VSRs considering AC constraints and multi-scenarios including base case and contingencies. The planning model is originally a non-convex large scale mixed integer nonlinear program (MINLP), which is generally intractable. The proposed Benders approach decomposes the MINLP model into a mixed integer linear program (MILP) master problem and a number of nonlinear subproblems. Numerical case studies based on IEEE 118-bus demonstrate the high performance of the proposed approach.

24 POWER TRANSMISSION AND DISTRIBUTION↗