Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
NASA NTRS1976

Indirect synthesis of multidegree-of-freedom transient systems

The indirect synthesis method is developed and shown to be capable of leading a near-optimal design of multidegree-of-freedom and multidesign-element transient nonlinear dynamical systems. The basis of the approach is to select the open design parameters such that the response of the portion of the system being designed approximates the limiting performances solution. The limiting performance problem can be formulated as one of linear programming by replacing all portions of the system subject to transient disturbances by control forces and supposing that the remaining portions are linear as are the overall kinematic constraints. One then selects the design parameters that respond most closely to the limiting performance solution, which can be achieved by unconstrained curve-fitting techniques.

Chen, Y. H.↗
NASA NTRS1978

The Lovasz bound and some generalizations

The zero error capacity of a discrete memoryless channel is defined as the largest rate at which information can be transmitted over the channel with zero error probability. One channel with five inputs and outputs whose zero capacity remained unsolved until very recently is considered. An extremely powerful and general technique phased in terms of graph theory, for studying combinatorial packing problems is presented. In particular, Delsarte's linear programming bound for cliques in association schemes appears as a special case of the Lovasz bound.

Mceliece, R. J.↗
NASA NTRS2009

A Mixed Integer Linear Program for Airport Departure Scheduling

Aircraft departing from an airport are subject to numerous constraints while scheduling departure times. These constraints include wake-separation constraints for successive departures, miles-in-trail separation for aircraft bound for the same departure fixes, and time-window or prioritization constraints for individual flights. Besides these, emissions as well as increased fuel consumption due to inefficient scheduling need to be included. Addressing all the above constraints in a single framework while allowing for resequencing of the aircraft using runway queues is critical to the implementation of the Next Generation Air Transport System (NextGen) concepts. Prior work on airport departure scheduling has addressed some of the above. However, existing methods use pre-determined runway queues, and schedule aircraft from these departure queues. The source of such pre-determined queues is not explicit, and could potentially be a subjective controller input. Determining runway queues and scheduling within the same framework would potentially result in better scheduling. This paper presents a mixed integer linear program (MILP) for the departure-scheduling problem. The program takes as input the incoming sequence of aircraft for departure from a runway, along with their earliest departure times and an optional prioritization scheme based on time-window of departure for each aircraft. The program then assigns these aircraft to the available departure queues and schedules departure times, explicitly considering wake separation and departure fix restrictions to minimize total delay for all aircraft. The approach is generalized and can be used in a variety of situations, and allows for aircraft prioritization based on operational as well as environmental considerations. We present the MILP in the paper, along with benefits over the first-come-first-serve (FCFS) scheme for numerous randomized problems based on real-world settings. The MILP results in substantially reduced delays as compared to FCFS, and the magnitude of the savings depends on the queue and departure fix structure. The MILP assumes deterministic aircraft arrival times at the runway queues. However, due to taxi time uncertainty, aircraft might arrive either earlier or later than these deterministic times. Thus, to incorporate this uncertainty, we present a method for using the MILP with "overlap discounted rolling planning horizon". The approach is based on valuing near-term decision results more than future ones. We develop a model of taxitime uncertainty based on real-world data, and then compare the baseline FCFS delays with delays using the above MILP in a simple rolling-horizon method and in the overlap discounted scheme.

Gupta, Gautam↗
NASA NTRS2024

Envisioning an Optimal Network of Space-Based Lasers for Orbital Debris Remediation

The rapid increase in resident space objects, including satellites and orbital debris, poses a significant threat to the safety and sustainability of space missions. This paper explores orbital debris remediation using a network of collaborative space-based lasers, leveraging laser ablation for momentum transfer on debris. A novel delta-v vector analysis framework quantifies the e↵ects of multiple simultaneous laser-to-debris (L2D) engagements by using vector composition of the imparted delta-v vectors. The paper introduces the Concurrent LocationScheduling Problem (CLSP), which optimizes the placement of laser platforms and the scheduling of L2D engagements to maximize debris remediation capacity. Due to the computational complexity of the CLSP, it is decomposed into two sequential subproblems: (1) optimal laser platform locations are determined using the Maximal Covering Location Problem, and (2) a novel integer linear programming-based approach schedules L2D engagements within the network configuration to maximize remediation capacity. Computational experiments are conducted to evaluate the proposed framework’s e↵ectiveness under various mission scenarios, demonstrating key network functions such as collaborative nudging, deorbiting, and just-in-time collision avoidance. A sensitivity analysis further examines how varying the number and distribution of laser platforms a↵ects debris remediation capacity, providing insights into optimizing the performance of space-based laser networks.

David O Williams Rogers↗
NASA NTRS1984

Efficient matrix partitioning for optical computing

Techniques for partitioning optical linear algebra problems to make them amenable to solution using optical processors programmed with simple algorithms are explored. Generalized methods for splitting a linear algebra matrix into a series of submatrices are reviewed, showing that simple forms can be pipelined smoothly and that parallel accumulation can be achieved by beam combining on detectors or by summing electronically. The techniques offer simplified bookkeeping, algorithmic independence, and high efficiency. The computational speed will depend on the number of multiplier-accumulators devoted to the task.

Caulfield, H. J.↗
DOE OSTI2023

Resilient Distribution System Restoration with Equitable Load Shedding

A methodology is proposed for the improvement of electric distribution system resilience to high-impact, low-probability catastrophic events. An approach for dynamic network reconfiguration and coordination of distributed energy resources is introduced to assist in restoration efforts. The problem is formulated as a mixed-integer linear program that minimizes generation costs, the cost of lost load, and costs associated with equitable load shedding, while respecting operational limits of generation, loads, and the network. Constraints are imposed on binary switching variables to ensure equitable load shedding in emergency situations. Numerical validation of the proposed approach is conducted on an example distribution feeder, and case studies are performed to analyze the impact of various parameters in the optimization problem formulation.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2026

Extreme-scale EV charging infrastructure planning for last-mile delivery using high-performance parallel computing

Here, this paper addresses stochastic charger location and allocation problems under queue congestion for last-mile delivery using electric vehicles (EVs). The objective is to decide where to open charging stations and how many chargers of each type to install, subject to budgetary and waiting-time constraints. We formulate the problem as a mixed-integer non-linear program, where each station-charger pair is modeled as a multiserver queue with stochastic arrivals and service times to capture the notion of waiting in fleet operations. The model is extremely large, with billions of variables and constraints for a typical metropolitan area; even loading the model in solver memory is difficult, let alone solving it. To address this challenge, we develop a Lagrangian-based dual decomposition framework that decomposes the problem by station and leverages parallelization on high-performance computing systems, where the subproblems are solved by using a cutting plane method and their solutions are collected at the master level. We also develop a three-step rounding heuristic to transform the fractional subproblem solutions into feasible integral solutions. Computational experiments on data from the Chicago metropolitan area with hundreds of thousands of households and thousands of candidate stations show that our approach produces high-quality solutions in cases where existing exact methods cannot even load the model in memory. We also analyze various policy scenarios, demonstrating that combining existing depots with newly built stations under multiagency collaboration substantially reduces costs and congestion. These findings offer a scalable and efficient framework for developing sustainable large-scale EV charging networks.

Capacity allocation↗
DOE OSTI2023

Solving the Unit Commitment Problem: Polyhedral Theory, Symmetry, and Power Flow

In this talk, I will give an overview of mixed integer linear programming (MILP) formulations and extensions thereof which enable the effective solution of the unit commitment problem (UC) when paired with a commercial MILP solver. First, we will place UC in context, stressing the importance of achieving a (near) optimal solution. Then we will discuss the importance of perfect and "good-enough" formulations for individual generators / market participants. Some of these formulations enable symmetry-aware reformulations for identical market participants, which can be critical when symmetry is present. Finally, we will discuss approximations of AC power flow currently used in practice, and the challenges with including these approximations within the UC formulation.

MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Assessing the Optimality of LinDist3Flow for Optimal Tap Selection of Step Voltage Regulators in Unbalanced Distribution Networks

The adoption of distributed energy resources such as photovoltaics (PVs) has increased dramatically during the previous decade. The increased penetration of PVs into distribution networks (DNs) can cause voltage fluctuations that have to be mitigated. One of the key utility assets employed to this end are step-voltage regulators (SVRs). It is desirable to include tap selection of SVRs in optimal power flow (OPF) routines, a task that turns out to be challenging because the resultant OPF problem is nonconvex with added complexities stemming from accurate SVR modeling. While several convex relaxations based on semi-definite programming (SDP) have been presented in the literature for optimal tap selection, SDP based schemes do not scale well and are challenging to implement in large-scale planning or operational frameworks. This paper deals with the optimal tap selection (OPTS) problem for wye-connected SVRs using linear approximations of power flow equations. Specifically, the LinDist3Flow model is adopted and the effective SVR ratio is assumed to be continuous- enabling the formulation of a problem called LinDist3Flow-OPTS, which amounts to a linear program. The scalability and optimality gap of LinDist3Flow-OPTS are evaluated with respect to existing SDP-based and nonlinear programming techniques for optimal tap selection in three standard feeders, namely, the IEEE 13-bus, 123-bus, and 8500-node DNs. For all DNs considered, LinDist3Flow-OPTS achieves an optimality gap of approximately 1% or less while significantly lowering the computational burden.

linear approximations↗
DOE OSTI2022

Assessing the Optimality of LinDist3Flow for Optimal Tap Selection of Step Voltage Regulators in Unbalanced Distribution Networks: Preprint

The adoption of distributed energy resources such as photovoltaics (PVs) has increased dramatically during the previous decade. The increased penetration of PVs into distribution networks (DNs) can cause voltage fluctuations that have to be mitigated. One of the key utility assets employed to this end are step-voltage regulators (SVRs). It is desirable to include tap selection of SVRs in optimal power flow (OPF) routines, a task that turns out to be challenging because the resultant OPF problem is nonconvex with added complexities stemming from accurate SVR modeling. While several convex relaxations based on semi-definite programming (SDP) have been presented in the literature for optimal tap selection, SDP based schemes do not scale well and are challenging to implement in large-scale planning or operational frameworks. This paper deals with the optimal tap selection (OPTS) problem for wye-connected SVRs using linear approximations of power flow equations. Specifically, the LinDist3Flow model is adopted and the effective SVR ratio is assumed to be continuous–enabling the formulation of a problem called LinDist3Flow-OPTS, which amounts to a linear program. The scalability and optimality gap of LinDist3Flow-OPTS are evaluated with respect to existing SDP-based and nonlinear programming techniques for optimal tap selection in three standard feeders, namely, the IEEE 13-bus, 123-bus, and 8500-node DNs. For all DNs considered, LinDist3Flow-OPTS achieves an optimality gap of approximately 1% or less while significantly lowering the computational burden.

linear approximations↗
NASA NTRS1976

Linear stochastic optimal control and estimation

Digital program has been written to solve the LSOCE problem by using a time-domain formulation. LSOCE problem is defined as that of designing controls for linear time-invariant system which is disturbed by white noise in such a way as to minimize quadratic performance index.

Geyser, L. C.↗
DOE OSTI2021

Machine-learning-aided cognitive reconfiguration for flexible-bandwidth HPC and data center networks [Invited]

This paper proposes a machine-learning (ML)-aided cognitive approach for effective bandwidth reconfiguration in optically interconnected datacenter/high-performance computing (HPC) systems. The proposed approach relies on a Hyper-X-like architecture augmented with flexible-bandwidth photonic interconnections at large scales using a hierarchical intra/inter-POD photonic switching layout. We first formulate the problem of the connectivity graph and routing scheme optimization as a mixed-integer linear programming model. A two-phase heuristic algorithm and a joint optimization approach are devised to solve the problem with low time complexity. Then, we propose an ML-based end-to-end performance estimator design to assist the network control plane with intelligent decision making for bandwidth reconfiguration. Numerical simulations using traffic distribution profiles extracted from HPC applications traces as well as random traffic matrices verify the accuracy performance of the ML design estimator ( < <#comment/> 9 % <#comment/> error) and demonstrate up to 5 × <#comment/> throughput gain from the proposed approach compared with the baseline Hyper-X network using fixed all-to-all intra/inter-portable data center interconnects.

Chen, Xiaoliang (ORCID:0000000278056237)↗
DOE OSTI2020

Optimal electric-distribution-grid planning considering the demand-side flexibility of thermal building systems for a test case in Singapore

The planning of district-scale electric grids, i.e., distribution grids, has traditionally relied on finding the most cost-effective design such that they are able to supply the peak loads in a district. With the advent of electric demand side flexibility (DSF), there is the opportunity to reshape peak loads such that the investment cost of the electric grid decreases in exchange for a minor increase in the operation cost. This paper formulates an optimal planning approach for the electric grid at the district scale, which incorporates the DSF from thermal building systems, e.g., heating ventilation and air-conditioning (HVAC) systems. The problem is formulated as a mixed-integer linear program (MILP) and aims at minimizing the investment cost for the grid along with the operation cost of the flexible loads. This is subjected to the fixed electricity demand and thermal comfort constraints of building occupants. To this end, linear models for the thermal comfort in the buildings and the power flow in electric grid are considered. The approach is tested on a district planning test case based in Singapore, where the results show up to 30.9 % reductions in investment cost and up to 3.7 % reduction in total annualized cost. Urban planning authorities, developers and utility companies can all benefit from the presented approach to make optimized investment decisions. For building operators, the results point to the need of adopting their control systems for DSF.

Troitzsch, Sebastian↗
DOE OSTI2021

A two-stage service restoration method for electric power distribution systems

Improving the reliability of power distribution systems is critically important for both utilities and customers. This calls for an efficient service restoration module within a distribution management system to support the implementation of self-healing smart grid networks. Although the emerging smart grid technologies, including distributed generators (DGs) and remote-controlled switches, enhance the self-healing capability and allow faster recovery, they still pose additional complexity to the service restoration problem, especially under cold load pickup (CLPU) conditions. Herein, a novel two-stage restoration framework is proposed to generate a restoration solutions with a sequence of control actions. The first stage generates a restoration plan that supports both the traditional service restoration using feeder reconfiguration and the grid-forming DG-assisted intentional islanding methods. The second stage generates an optimal sequence of switching operations to bring the outaged system quickly to the final restored configuration. The problem is formulated as a mixed-integer linear program that incorporates system connectivity, operating constraints, and the CLPU models. It is demonstrated that on using a multi-feeder test case, the proposed framework is effective in utilizing all available resources to quickly restore the service and generate an optimal sequence of switching actions to be used by the operator to reach the desired optimal configuration.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

A Generalized Framework for Service Restoration in a Resilient Power Distribution System

An electric power grid is one of the complex infrastructures, and because of its complex nature, there is simply no way that outages can be completely avoided. Thus, a modern society that depends on reliable electric supply requires a resilient electric system that can recover from disruptions while integrating emerging smart grid technologies. Here, this article presents a novel approach for service restoration in a modern power distribution system with controllable switches and distributed generation (DG) resources for any kind of outage. The proposed framework supports both the traditional service restoration using feeder reconfiguration and the grid-forming DG-assisted intentional islands that are dynamically sized using algorithms based on the fault scenario, available resources, and priority of loads. The problem is formulated as a mixed-integer linear program that incorporates critical system connectivity and operating constraints. Simulations are performed to demonstrate the effectiveness of the proposed approach using a large-scale four-feeder 1069-bus three-phase unbalanced distribution test system. It is demonstrated that the framework is effective in utilizing all available resources in quickly restoring the power supply to improve resiliency during extreme events and is scalable for a large-scale unbalanced power distribution system.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Enhancing Distribution Grid Resilience Through Model Predictive Controller Enabled Prioritized Load Restoration Strategy

Effective resilience improvement strategies enable the power grid to cope with disruptive extreme events. Most power grid outages are caused by disruptions in distribution grids. Motivated by the urgent need for power system resilience research, this paper proposes a priority-weighted optimal load restoration technique to enhance the resilience of distribution grids against extreme events. The proposed technique is based on smart distribution technology and framed as sequential multi-step decision process (MDP) and mixed integer linear program (MILP). It is formulated as optimal control problem with a model predictive control (MPC) approach. We applied the devised MILP-MPC-based load restoration technique to a simplified single-bus version of the IEEE 13-bus distribution system with integrated distributed energy resources (DERs) such as wind turbine, photovoitaic array, microturbine, and energy storage device. The technique executes a reducing and rolling horizon optimization in each control step in real-time using the forecasted information of the renewables, the fuel status of the microturbine and the state of charge of the energy storage device. We consider an extreme event which triggered outage of the upstream utility grid and caused islanded operation of the distribution grid. We demonstrated the effectiveness of the proposed MPC approach in restoring the distribution grid loads based on their priority during the main grid outage-caused islanded operation.

61 RADIATION PROTECTION AND DOSIMETRY↗
DOE OSTI2022

Scalable Predictive Control and Optimization for Grid Integration of Large-Scale Distributed Energy Resources

Integrating a large number of distributed energy resources (DERs) into the power grid needs a scalable power balancing method. We formulate the power balancing problem as a look-ahead optimization problem to be solved sequentially by a power distribution system aggregator based on a model predictive control (MPC) framework. Solving large-scale look-ahead control problems requires proper configuration of the control steps. In this paper, to solve large-scale control problems, we propose a variable time granularity where control time steps nearby the current control step have finer resolutions. The aggregator objective includes maximization of power production revenue and minimization of power purchasing expense, renewable power curtailment, and mileage costs for energy storage and electric vehicle (EV) charging stations while satisfying system capacity and operational constraints. The control problem is formulated as a mixed-integer linear program (MILP) and solved using the XpressMP solver. We perform simulations considering a copper plate representation of a large distribution network consisting of 2507 devices (control-lable DERs), including curtailable photovoltaics (PVs), energy storage batteries, EV charging stations, and buildings with heating, ventilation, and air conditioning units (HVACs). We show the effectiveness of the proposed approach in managing DERs interactively for maximum energy trading profit and local supply-demand power balancing. Finally, we demonstrate that the proposed method outperforms other benchmark controllers regarding computation time without compromising operational performance.

DER↗
DOE OSTI2022

Managing Power Systems-Induced Wildfire Risks Using Optimal Scheduled Shutoffs

The increasing demands for electricity and the increase in extreme weather conditions are putting unprecedented pressure on our electric grids. Often, this pressure leads to electrical component failures, which might ignite wildfires. This work develops a novel model to balance the reliability of power network operations and the risk of wildfire ignition by opti- mizing the operational schedule of power transmission networks considering time-varying risk measures that include exogenous and operational factors. Energy storage systems are considered to deliver power during peak wildfire hours and enable temporal load shifting. The problem is formulated as a mixed-integer linear program that maximizes a weighted sum of the served power demand and the reduction in grid-induced wildfire risk. The results demonstrate the ability of the model to significantly reduce wildfire risk without considerable load shedding.

power systems operations↗