Search NASA⌕ Search

SEARCH · Search NASA

Results for “Mixed Integer Linear Programming”

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 55 records · Page 3

Design Considerations of a Coordinative Demand Charge Mitigation Strategy

This paper presents a coordinative demand charge mitigation (DCM) strategy for reducing electricity consumption during system peak periods. Available DCM resources include batteries, diesel generators, controllable loads, and conservation voltage reduction. All resources are directly controlled by load serving entities. A mixed integer linear programming based energy management algorithm is developed to optimally coordinate of DCM resources considering the load payback effect. To better capture system peak periods, two different kinds of load forecast are used: the day-ahead load forecast and the peak-hour probability forecast. Five DCM strategies are compared for reconciling the discrepancy between the two forecasting results. The DCM strategies are tested using actual utility data. Simulation results show that the proposed algorithm can effectively mitigate the demand charge while preventing the system peak from being shifted to the payback hours. We also identify the diminishing return effect, which can help load serving entities optimize the size of their DCM resources.

Hu, Rongxing↗

Distributionally robust facility location problem under decision-dependent stochastic demand

While the traditional facility location problem considers exogenous demand, in some applications, locations of facilities could affect the willingness of customers to use certain types of services, e.g., carsharing, and therefore they also affect realizations of random demand. Moreover, a decision maker may not know the exact distribution of such endogenous demand and how it is affected by location choices. In this paper, we consider a distributionally robust facility location problem, in which we interpret the moments of stochastic demand as functions of facility-location decisions. We reformulate a two-stage decision-dependent distributionally robust optimization model as a monolithic formulation, and then derive exact mixed-integer linear programming reformulation as well as valid inequalities when the means and variances of demand are piecewise linear functions of location solutions. We conduct extensive computational studies, in which we compare our model with a decision-dependent deterministic model, as well as stochastic programming and distributionally robust models without the decision-dependent assumption. Here, the results show superior performance of our approach with remarkable improvement in profit and quality of service under various settings, in addition to computational speed-ups given by formulation enhancements. These results draw attention to the need of considering the impact of location decisions on customer demand within this strategic-level planning problem.

97 MATHEMATICS AND COMPUTING↗

Distributed biomass supply chain cost optimization to evaluate multiple feedstocks for a biorefinery

Conventional practices of siting all biomass preprocessing operations at the biorefinery is widely believed to be the most cost-effective solution for feedstock supply because of economies of scale. Yet, biomass preprocessing operations could be decentralized by moving the preprocessing operations to distributed biomass preprocessing centers, also known as “depots” located near biomass sources. We present a comparative case study with multiple biomass resources to analyze biorefinery feedstock supply logistics designs having distributed depots and a primary depot co-located with the biorefinery. A mixed-integer linear programming model was developed to simultaneously optimize feedstock sourcing decisions, and optimal preprocessing depot locations and size, utilizing biomass resources from agricultural residue, energy and municipal solid waste to meet carbohydrate specifications and feedstock demand for a biochemical conversion process. Findings from a case study in the US showed that a biorefinery could increase its feedstock supply draw area and supply volume by 57.3%, 177.4% respectively without increasing the feedstock delivered cost by adopting distributed depot-in the feedstock supply chain design. A distributed-depot-based supply chain can be more economical by selecting optimal mix of biomass resource, optimal siting and depot scales during feedstock supply chain design. The results from this study indicate that a biorefinery can utilize dynamic blending to meet the feedstock quality specifications as well as larger supply radius in the distributed depot-based supply chain design to access more available biomass to handle potential feedstock supply uncertainty.

09 BIOMASS FUELS↗

Design and dispatch optimization of packaged ice storage systems within a connected community

The traditional implementation of cool thermal energy storage (CTES) must be reimagined within the context of a dynamic grid and smart buildings operating as connected communities. As most buildings do not operate central chillers or connect to district cooling loops, this necessitates a broader use of packaged CTES. Our objective is to begin answering the question of how such packaged CTES should be implemented within a connected community. We do so by presenting a simulation–optimization workflow employing building energy modeling software and a mixed-integer linear program to design and dispatch a packaged CTES technology to achieve minimum total annual cost. We demonstrate this methodology on a seven-building case study using current utility rates and find that total annual cooling energy costs can be reduced by 17.8% compared to baseline, after accounting for the cost of storage. We perform three parametric sensitivity studies to evaluate modeling assumptions and obtain the prioritization of storage procurement as a function of annualized life-cycle cost of storage. We find that a community optimization approach provides significantly different results than individual building optimizations and provides greater savings compared to baseline.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Robust trajectory-constrained frequency control for microgrids considering model linearization error

Grid supportive modes integrated within inverter-based resources can improve the frequency response of renewable-rich microgrids. The synthesis of grid supportive modes to guarantee frequency trajectory constraints under a predefined disturbance set is challenging but essential. To tackle this challenge, a numerical optimal control (NOC)-based control synthesis methodology is proposed. Without loss of generality, a wind-diesel fed microgrid is studied, where we aim to design grid supportive functions in the wind turbine. In the control design, linearized models are used, and the linearization-induced errors are quantitatively analyzed by reachability and interval arithmetics and represented in the form of interval uncertainties. Then, the NOC problem can be formulated into a robust mixed-integer linear program. The control structure is strategically configured into two levels to realize online deployment. The proposed control is verified on the modified 33-node microgrid with a full-order three-phase nonlinear model in Simulink. In conclusion, the simulation results show the effectiveness of the proposed control paradigm and the necessity of considering linearization-induced uncertainty.

24 POWER TRANSMISSION AND DISTRIBUTION↗

A Non-Exhaustive Search Algorithm to Identify Distribution Grid Operational Topology

Distribution grid, in general, is constructionally loopy but a radially operated network. Opening and closing of suitable tie-switches allow transition from one topology to another. Identifying the operational topology of a distribution system is essential for accurate control actions. This paper proposes a non-exhaustive search approach to detect the operational topology of the distribution feeder by estimating the switch statuses. In this work, a mixed-integer linear programming approach is proposed that finds the correct operational topology by identifying the system load demand and power flow variables that are closest to the corresponding measured values. The problem is constrained by distribution power flow and radial structure of the feeder. This formulation allows the inclusion of errors in power/line flow measurements making it more suitable for a practical distribution system. The proposed approach finds the correct operational topology without exhaustively searching for all possible topologies. We thoroughly validate the accuracy and effectiveness of the proposed approach in identifying correct operational topology using IEEE 123-node feeder with the help of numerous simulations studies. It is observed that the approach performs well even at very high percentages of load and flow measurement errors.

Missed detection ratio (MDR), Mixed-integer linear↗

Cooperative Routing for an Air–Ground Vehicle Team—Exact Algorithm, Transformation Method, and Heuristics

This paper considers a cooperative vehicle routing problem for an intelligence, surveillance, and reconnaissance mission in the presence of communication constraints between the vehicles. The proposed framework uses a ground vehicle and an unmanned aerial vehicle (UAV) that travel cooperatively and visit a set of targets while satisfying the communication constraints. The problem is formulated as a mixed-integer linear program, and a branch-and-cut algorithm is developed to solve the problem to optimality. Furthermore, a transformation method and a heuristic are also developed for the problem. The effectiveness of all the algorithms is corroborated through extensive computational experiments on several randomly generated instances. Furthermore, this paper is motivated by an intelligence, surveillance, and reconnaissance mission involving a single unmanned aerial vehicle (UAV) and a ground vehicle, where the vehicles must coordinate their activity in the presence of communication constraints. The combination of a small UAV and a ground vehicle is an ideal platform for such missions, since small UAVs can fly at low altitudes and can avoid obstacles or threats that would be problematic for the ground vehicle alone. This paper addresses the coordinated routing problem involving these two vehicles and presents an algorithm to obtain an optimal solution for this problem, fast heuristics to obtain good feasible solutions, and also a transformation method to transform any instance of this cooperative vehicle routing problem to an instance of the one-in-a-set traveling salesman problem.

33 ADVANCED PROPULSION SYSTEMS↗

Dispatch optimization of concentrating solar power with utility-scale photovoltaics

Concentrating solar power (CSP) tower technologies capture thermal radiation from the sun utilizing a field of solar-tracking heliostats. When paired with inexpensive thermal energy storage (TES), CSP technologies can dispatch electricity during peak-market-priced hours, day or night. The cost of utility-scale photovoltaic (PV) systems has dropped significantly in the last decade, resulting in inexpensive energy production during daylight hours. The hybridization of PV and CSP with TES systems has the potential to provide continuous and stable energy production at a lower cost than a PV or CSP system alone. Hybrid systems are gaining popularity in international markets as a means to increase renewable energy portfolios across the world. Typically, CSP-PV hybrid systems have been evaluated using either monthly averages of hourly PV production or scheduling algorithms that neglect the time-of-production value of electricity in the market. To more accurately evaluate a CSP-PV-battery hybrid design, we develop a profit-maximizing mixed-integer linear program ($\mathcal{H}$) that determines a dispatch schedule for the individual sub-systems with a sub-hourly time fidelity. We introduce the mathematical formulation of such a model and show that it is computationally expensive to solve. To improve model tractability and reduce solution times, we offer techniques that: (1) reduce the problem size, (2) tighten the linear programming relaxation of ($\mathcal{H}$) via reformulation and the introduction of cuts, and (3) implement an optimization-based heuristic (that can yield initial feasible solutions for (($\mathcal{H}$) and, at any rate, yields near-optimal solutions). Applying these solution techniques results in a 79% improvement in solve time, on average, for our 48-h instances of (($\mathcal{H}$); corresponding solution times for an annual model run decrease by as much as 93%, where such a run consists of solving 365 instances of (($\mathcal{H}$), retaining only the first 24 h' worth of the solution, and sliding the time window forward 24 h. We present annual system metrics for two locations and two markets that inform design practices for hybrid systems and lay the groundwork for a more exhaustive policy analysis. A comparison of alternative hybrid systems to the CSP-only system reflects that hybrid models can almost double capacity factors while resulting in a 30% improvement related to various economic metrics.

14 SOLAR ENERGY↗

A solution framework for linear PDE-constrained mixed-integer problems

Abstract We present a general numerical solution method for control problems with state variables defined by a linear PDE over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs to derive constraints for a mixed-integer linear program (MILP) leads to systems that are too large to be solved with state-of-the-art solvers for MILPs, especially if we desire an accurate approximation of the state variables. Our framework comprises two techniques to mitigate the rise of computation times with increasing discretization level: First, the linear system is solved for a basis of the control space in a preprocessing step. Second, certain constraints are just imposed on demand via the IBM ILOG CPLEX feature of a lazy constraint callback. These techniques are compared with an approach where the relations obtained by the discretization of the continuous constraints are directly included in the MILP. We demonstrate our approach on two examples: modeling of the spread of wildfire and the mitigation of water contamination. In both examples the computational results demonstrate that the solution time is significantly reduced by our methods. In particular, the dependence of the computation time on the size of the spatial discretization of the PDE is significantly reduced.

97 MATHEMATICS AND COMPUTING↗

Efficient Topology Design Algorithms for Power Grid Stability

The dynamic response of power grids to small disturbances influences their overall stability. This letter examines the effect of network topology on the linearized time-invariant dynamics of electric power systems. The proposed framework utilizes H 2 -norm based stability metrics to study the optimal placement of lines on existing networks as well as the topology design of new networks. The design task is first posed as an NP-hard mixed-integer nonlinear program (MINLP) that is exactly reformulated as a mixed-integer linear program (MILP) using McCormick linearization. To improve computation time, graph-theoretic properties are exploited to derive valid inequalities (cuts) and tighten bounds on the continuous optimization variables. Moreover, a cutting plane generation procedure is put forth that is able to interject the MILP solver and augment additional constraints to the problem on-the-fly. Finally, the efficacy of our approach in designing optimal grid topologies is demonstrated through numerical tests on the IEEE 39-bus network.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Disjunctive optimization model and algorithm for long-term capacity expansion planning of reliable power generation systems

This paper proposes a new optimization model and algorithm for long-term capacity expansion planning of reliable power generation systems. The model optimizes both investment decisions (e.g., size, location, and time to install, retire and decommission facilities) and operation decisions (e.g., on/off status, operating capacity, and expected power output). It is also able to optimize reserve systems (or backup systems), as well as the main systems, to improve power systems reliability. An impact of operational strategies of generators (i.e., participating in electricity production vs. remaining as idle units during operation) on power systems reliability is considered. Probability of equipment failures and capacity failure states are used to rigorously estimate the power systems reliability depending on design and operation strategies. The optimization model is formulated with Generalized Disjunctive Programming (GDP), which is reformulated as a mixed-integer linear programming (MILP) model using the Hull relaxation. Two reliability-related penalties, such as downtime penalty and unmet demand penalty, are included in the objective function to maximize reliability while minimizing the total net present cost. Furthermore, a bilevel decomposition with tailored cuts is developed to reduce computational times of the multi-scale optimization model. The effectiveness of the proposed model is shown by comparing the results with the results obtained from the expansion planning models that do not explicitly consider reliability. In conclusion, we also show that the proposed bilevel decomposition is computationally efficient for solving large scale problems through 5-years and 10-years planning case studies.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

Cost-optimal evaluation of centralized and distributed microgrid topologies considering voltage constraints

Optimal design of hybrid renewable mini-grids requires both economic and power quality considerations. Existing modeling approaches address these considerations via separate or loosely coupled models. Here, we extend REopt—a techno-economic optimization model developed at the National Renewable Energy Laboratory—to consider both within a single model. REopt formulates the design problem as a mixed-integer linear program that solves for a site's optimal technology mix, sizing, and operation to minimize life cycle cost. REopt has traditionally assumed a single node system. In the work presented here, we expand the REopt platform to consider multiple connected nodes with associated voltage constraints. In order to do this, we model power flow using a fixed-point linear approximation method. Additionally, we then use the model to explore design considerations of mini-grids in Sub-Saharan Africa. Specifically, we evaluate under what combinations of transmission line distance and capacity it is technically viable and economically preferable to build multiple isolated mini-grids versus an interconnected, centralized system.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Optimal Scheduling of an Isolated Microgrid With Battery Storage Considering Load and Renewable Generation Uncertainties

By modeling the uncertainty of spinning reserves provided by energy storage with probabilistic constraints, a new optimal scheduling mode is proposed in this paper for minimizing the operating costs of an isolated microgrid (MG) by using chance-constrained programming. The model is transformed into a readily solvable mixed integer linear programming formulation in general algebraic modeling system (GAMS) via a proposed discretized step transformation approach and finally solved by applying the CPLEX solver. By properly setting the confidence levels of the spinning reserve probability constraints, the MG operation can achieve a tradeoff between reliability and economy. The test results on the modified Oak Ridge National Laboratory Distributed Energy Control and Communication lab MG test system reveal that the proposal significantly exceeds the commonly used hybrid intelligent algorithm with much better and more stable optimization results and significantly reduced calculation times.

Li, Yang↗

Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets

We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage can be recast as a mixed-integer linear program (MILP). Moreover, we extend the general moment-based ambiguity set in to the multistage decision-dependent setting, and derive mixed-integer semidefinite programming (MISDP) reformulations of stage-wise subproblems. We develop methods for attaining lower and upper bounds of the optimal objective value of the multistage MISDPs, and approximate them using a series of MILPs. We deploy the Stochastic Dual Dynamic integer Programming (SDDiP) method for solving the problem under the three ambiguity sets with risk-neutral or risk-averse objective functions, and conduct numerical studies on multistage facility-location instances having diverse sizes under different parameter and uncertainty settings. Furthermore, our results show that the SDDiP quickly finds optimal solutions for moderate-sized instances under the first two ambiguity sets, and also finds good approximate bounds for the multistage MISDPs derived under the third ambiguity set. We also demonstrate the efficacy of incorporating decision-dependent distributional ambiguity in multistage decision-making processes.

97 MATHEMATICS AND COMPUTING↗

Shortest path network interdiction with asymmetric uncertainty

Abstract This paper considers an extension of the shortest path network interdiction problem that incorporates robustness to account for parameter uncertainty. The shortest path interdiction problem is a game of two players with conflicting agendas and capabilities: an evader, who traverses the arcs of a network from a source node to a sink node using a path of shortest length, and an interdictor, who maximizes the length of the evader's shortest path by interdicting arcs on the network. It is usually assumed that the parameters defining the network are known exactly by both players. We consider the situation where the evader assumes the nominal parameter values while the interdictor uses robust optimization techniques to account for parameter uncertainty or sensor degradation. We formulate this problem as a nonlinear mixed‐integer semi‐infinite bilevel program and show that it can be converted into a mixed‐integer linear program with a second order cone constraint. We use random geometric networks and transportation networks to perform computational studies and demonstrate the unique decision strategies that our variant produces. Solving the shortest path interdiction problem with asymmetric uncertainty protects the interdictor from investing in a strategy that hinges on key interdictions performing as promised. It also provides an alternate strategy that mitigates the risk of these worst‐case possibilities.

Punla‐Green, She'ifa Z.↗

A Fast Dynamic Internal Predictive Power Scheduling Approach for Power Management in Microgrids: Preprint

This paper presents a Dynamic Internal Predictive Power Scheduling (DIPPS) approach for optimizing power management in microgrids, particularly focusing on external power exchanges among diverse prosumers. DIPPS utilizes a dynamic objective function with a time-varying binary parameter to control the timing of power transfers to the external grid, facilitated by efficient usage of energy storage for surplus renewable power. The microgrid power scheduling problem is modeled as a mixed-integer nonlinear programming (MINLP-PS) and subsequently transformed into a mixed-integer linear programming (MILPPS) optimization through McCormick's relaxation to reduce computational complexity. A predictive window window with 6 data points is solved at an average of 0.92s, a 97.6% improvement over the 38.27s required for the MINLP-PS formulation, implying the numerical feasibility of the DIPPS approach for real-time implementation. Finally, the approach is validated against a static objective using real-world load data across three case studies with different time-varying parameters, demonstrating the ability of DIPPS to optimize power exchanges and efficiently utilize distributed resources while shifting the external power transfers to specified time durations.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Decomposing Loosely Coupled Mixed-Integer Programs for Optimal Microgrid Design

Microgrids are frequently employed in remote regions, in part because access to a larger electric grid is impossible, difficult, or compromises reliability and independence. Although small microgrids often employ spot generation, in which a diesel generator is attached directly to a load, microgrids that combine these individual loads and augment generators with photovoltaic cells and batteries as a distributed energy system are emerging as a safer, less costly alternative. In this work, we present a model that seeks the minimum-cost microgrid design and ideal dispatched power to support a small remote site for one year with hourly fidelity under a detailed battery model; this mixed-integer nonlinear program (MINLP) is intractable with commercial solvers but loosely coupled with respect to time. A mixed-integer linear program (MIP) approximates the model, and a partitioning scheme linearizes the bilinear terms. We introduce a novel policy for loosely coupled MIPs in which the system reverts to equivalent conditions at regular time intervals; this separates the problem into subproblems that we solve in parallel. We obtain solutions within 5% of optimality in at most six minutes across 14 MIP instances from the literature and solutions within 5% of optimality to the MINLP instances within 20 minutes.

97 MATHEMATICS AND COMPUTING↗

Optimal Network Topology for Node-Breaker Representations With AC Power Flow Constraints

It has been demonstrated that network topology optimization (NTO) may change the topology of power system networks, and consequently, provide additional flexibility to reduce network congestion and violations. Most NTO problems are formulated based on the bus-branch model in which it is challenging to represent a realistic picture of all substation configurations. In this paper, we explore advantages of substation reconfiguration modeling based on node-breaker representations for NTO problem with full nonlinear alternating current power flow. It also proposes a tailored solution algorithm to solve this nonconvex mixed-integer nonlinear programming through the outer approximation method. The proposed solution approach iterates between a mixed-integer linear programming and a nonlinear subproblem. Additional enhancements to further accelerate the iteration process are illustrated. Numerical case studies demonstrate the relative economic and operational impact of optimal network topology with node-breaker representations.

42 ENGINEERING↗