Search NASA⌕ Search

SEARCH · Search NASA

Results for “Integer Optimization”

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

Simultaneous personnel and vehicle shift scheduling in the waste management sector

Highlights: • We consider the problem of simultaneously schedule personnel and vehicle shifts in the waste management sector. • We propose both an optimization model and a heuristic approach. • Important monetary savings can be achieved in the waste collection operations. - Abstract: Urban waste management is becoming an increasingly complex task, absorbing a huge amount of resources, and having a major environmental impact. The design of a waste management system consists in various activities, and one of these is related to the definition of shift schedules for both personnel and vehicles. This activity has a great incidence on the tactical and operational cost for companies. In this paper, we propose an integer programming model to find an optimal solution to the integrated problem. The aim is to determine optimal schedules at minimum cost. Moreover, we design a fast and effective heuristic to face large-size problems. Both approaches are tested on data from a real-world case in Southern Italy and compared to the current practice utilized by the company managing the service, showing that simultaneously solving these problems can lead to significant monetary savings.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

A Convexification-Based Outer-Approximation Method for Convex and Nonconvex MINLP

The advancement of domain reduction techniques has significantly enhanced the performance of solvers in mathematical programming. This paper delves into the impact of integrating convexification and domain reduction techniques within the Outer-Approximation method. We propose a refined convexification-based Outer-Approximation method alongside a Branch-and-Bound method for both convex and nonconvex Mixed-Integer Nonlinear Programming problems. These methods have been developed and incorporated into the open-source Mixed-Integer Nonlinear Decomposition Toolbox for Pyomo-MindtPy. Comprehensive benchmark tests were conducted, validating the effectiveness and reliability of our proposed algorithms. These tests highlight the improvements achieved by incorporating convexification and domain reduction techniques into the Outer-Approximation and Branch-and-Bound methods.

Optimization↗

Optimizing design and dispatch of a renewable energy system with combined heat and power

We embellish a mixed-integer program that prescribes a set of renewable energy, conventional generation, and storage technologies to procure, along with a corresponding dispatch strategy. Specifically, we add combined heat and power to this set. The model minimizes fixed and operational costs less incentives for the use of various technologies, subject to a series of component interoperability and system-wide constraints. The resulting mixed-integer linear program contains hundreds of thousands of variables and constraints. We demonstrate how to efficiently formulate and solve the corresponding instances such that we produce near-optimal solutions in minutes. A previous rendition of the model required hours of solution time for the same instances.

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↗

A Cooperative Control Algorithm for Camera Based Observational Systems

Over the last several years, there has been considerable growth in camera based observation systems for a variety of safety, scientific, and recreational applications. In order to improve the effectiveness of these systems, we frequently desire the ability to increase the number of observed objects, but solving this problem is not as simple as adding more cameras. Quite often, there are economic or physical restrictions that prevent us from adding additional cameras to the system. As a result, we require methods that coordinate the tracking of objects between multiple cameras in an optimal way. In order to accomplish this goal, we present a new cooperative control algorithm for a camera based observational system. Specifically, we present a receding horizon control where we model the underlying optimal control problem as a mixed integer linear program. The benefit of this design is that we can coordinate the actions between each camera while simultaneously respecting its kinematics. In addition, we further improve the quality of our solution by coupling our algorithm with a Kalman filter. Through this integration, we not only add a predictive component to our control, but we use the uncertainty estimates provided by the filter to encourage the system to periodically observe any outliers in the observed area. This combined approach allows us to intelligently observe the entire region of interest in an effective and thorough manner.

99 GENERAL AND MISCELLANEOUS↗

New bounding and decomposition approaches for MILP investment problems: Multi-area transmission and generation planning under policy constraints

A novel two-phase bounding and decomposition approach to compute optimal and near-optimal solutions to large-scale mixed-integer investment planning problems is proposed and it considers a large number of operating subproblems, each of which is a convex optimization. Our motivating application is the planning of power transmission and generation in which policy constraints are designed to incentivize high amounts of intermittent generation in electric power systems. The bounding phase exploits Jensen’s inequality to define a lower bound, which we extend to stochastic programs that use expected-value constraints to enforce policy objectives. The decomposition phase, in which the bounds are tightened, improves upon the standard Benders’ algorithm by accelerating the convergence of the bounds. The lower bound is tightened by using a Jensen’s inequality-based approach to introduce an auxiliary lower bound into the Benders master problem. Upper bounds for both phases are computed using a sub-sampling approach executed on a parallel computer system. Numerical results show that only the bounding phase is necessary if loose optimality gaps are acceptable. But, the decomposition phase is required to attain optimality gaps. Moreover, use of both phases performs better, in terms of convergence speed, than attempting to solve the problem using just the bounding phase or regular Benders decomposition separately.

97 MATHEMATICS AND COMPUTING↗

Predictively Coordinated Vehicle Acceleration and Lane Selection Using Mixed Integer Programming

Autonomous vehicle technology provides the means to optimize motion planning beyond human capacity. In particular, the problem of navigating multi-lane traffic optimally for trip time, energy efficiency, and collision avoidance presents challenges beyond those of single-lane roadways. For example, the host vehicle must simultaneously track multiple obstacles, the drivable region is non-convex, and automated vehicles must obey social expectations. Furthermore, reactive decision-making may result in becoming stuck in an undesirable traffic position. This paper presents a fundamental approach to these problems using model predictive control with a mixed integer quadratic program at its core. Lateral and longitudinal movements are coordinated to avoid collisions, track a velocity and lane, and minimize acceleration. Vehicle-to-vehicle connectivity provides a preview of surrounding vehicles’ motion. Simulation results show a 79% reduction in congestion-induced travel time and an 80% decrease in congestion-induced fuel consumption compared to a rule-based approach.

Dollar, Robert Austin↗

Series FACTS Devices for Increasing Resiliency in Severe Weather Conditions

Severe weather conditions are low-probability, high-impact events that affect grid operations. The majority of power outages are caused by severe weather conditions. Grid resiliency to weather events can be enhanced by decreasing the reliance on its affected sections. One way to do this is to reduce the power flow through lines vulnerable to severe weather. If a line is disconnected, its initial power flow is distributed through the neighbor lines, which may cause congestion in the grid. FACTS devices can be used to control the power flow of lines that have a higher chance of power outages. Most previous works do not consider weather events in power flow control. In this work, a linearized optimal power flow (OPF)–based algorithm is developed to minimize the real power flow of vulnerable lines considering the thermal limits of lines to prevent infeasible solutions; the simulation is fast, making it suitable for large-scale systems. The proposed optimization problem is presented as a mixed-integer linear program (MILP), making it capable of using short-term load forecasting due to its high solution speed. The proposed optimization problem considers multiple lines with different outage probabilities and the uncertainties of the weather forecast. Moreover, it estimates the power reduction in vulnerable lines due to changes in the series FACTS devices. The performance of the proposed optimization problem is tested on IEEE 14-, 30-, and 118-bus systems for several scenarios. The results are validated with the AC power flow results from MATPOWER.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Substation-Level Grid Topology Optimization Using Bus Splitting: Preprint

Operations of substation circuit breakers are of high significance for performing system maintenance and topology optimization. Bus splitting is one type of topology changes where the two bus-bars at a substation become electrically disconnected after certain actions of circuit breakers. As these events involve detailed substation modeling, they are not typically considered in power system routine operation and control. In this paper, an improved substation-level topology optimization is developed by expanding traditional line switching with breaker-level bus splitting, which can further reduce grid congestion and generation costs. A tight McCormick relaxation is proposed to reformulate the bi-linear terms in the resultant topology optimization model. Thus, a tractable mixed-integer linear program formulation is presented which can be efficiently solved for real-time control. Numerical studies on the IEEE 14-bus and 118-bus systems demonstrate the performance and economic benefits of the proposed topology optimization approach.

bus split↗

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↗

REopt: A Platform for Energy System Integration and Optimization: Preprint

REopt is NREL's energy planning platform offering concurrent, multi-technology integration and optimization capabilities to help clients meet their cost savings and energy performance goals. The REopt platform provides techno-economic decision-support analysis throughout the energy planning process, from agency-level screening and macro planning to project development to energy asset operation. REopt employs an integrated approach to optimizing a site?s energy costs by considering electricity and thermal consumption, resource availability, complex tariff structures including time-of-use, demand and sell-back rates, incentives, net-metering, and interconnection limits. Formulated as a mixed integer linear program, REopt recommends an optimally-sized mix of conventional and renewable energy, and energy storage technologies; estimates the net present value associated with implementing those technologies; and provides the cost-optimal dispatch strategy for operating them at maximum economic efficiency. The REopt platform can be customized to address a variety of energy optimization scenarios including policy, microgrid, and operational energy applications. This paper presents the REopt techno-economic model along with two examples of recently completed analysis projects.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

POINT: Partially Observable Imitation Network for Traffic Signal Control

Smart traffic signals bring together transportation infrastructure and advance technologies to improve the mobility and efficiency of urban transportation network. Adaptive traffic signal control studies can be categorized into modeling-based approaches and learning-based approaches. In order to take advantages of these two systems, this study developed an offline-online combined Partial Observable Imitation Network for Traffic signal control (POINT). In the offline system, the traffic signal timing optimization problem was formulated as a Mixed Integer Nonlinear Programming (MINLP) given complete traffic information, i.e., second-by-second speeds and locations of all vehicles. Furthermore, the objective of MINLP is to minimize total travel delays considering individual vehicle trajectories under Connected Vehicle (CV) environment. The calculated optimal solutions under various traffic conditions were considered as the ”expert” decisions. In the online system, an imitation neural network model was developed to learn the ”expert” signal plans generated from offline system. Given partial observable traffic conditions in real time, e.g., the aggregate-level of traffic volume, the POINT model can compute the signal timing parameters in the online system. The numerical results demonstrated that the proposed method outperformed other state-of-the-art signal control method under high and unbalanced traffic demand levels in terms of reducing travel delays and queue length.

33 ADVANCED PROPULSION SYSTEMS↗

Optimization Routine for Generating Medical Kits for Spaceflight Using the Integrated Medical Model

The Integrated Medical Model (IMM) is a MATLAB model that provides probabilistic assessment of the medical risk associated with human spaceflight missions.Different simulations or profiles can be run in which input conditions regarding both mission characteristics and crew characteristics may vary. For each simulation, the IMM records the total medical events that occur and “treats” each event with resources drawn from import scripts. IMM outputs include Total Medical Events (TME), Crew Health Index (CHI), probability of Evacuation (pEVAC), and probability of Loss of Crew Life (pLOCL).The Crew Health Index is determined by the amount of quality time lost (QTL). Previously, an optimization code was implemented in order to efficiently generate medical kits. The kits were optimized to have the greatest benefit possible, given amass and/or volume constraint. A 6-crew, 14-day lunar mission was chosen for the simulation and run through the IMM for 100,000 trials. A built-in MATLAB solver, mixed-integer linear programming, was used for the optimization routine. Kits were generated in 10% increments ranging from 10%-100% of the benefit constraints. Conditions wheremass alone was minimized, volume alone was minimized, and where mass and volume were minimizedjointly were tested.

Medical Kit↗

Complete Assembly of Circular and Chloroplast Genomes Based on Global Optimization

This paper focuses on the last two stages of genome assembly, namely scaffolding and gap-filling, and shows that they can be solved as part of a single optimization problem. Our approach is based on modeling genome assembly as a problem of finding a simple path in a specific graph that satisfies as many as possible of the distance constraints encoding the insert-size information. We formulate it as a mixed-integer linear programming problem and apply an optimization solver to find the exact solutions on a benchmark of chloroplasts. We show that the presence of repetitions in the set of unitigs is the main reason for the existence of multiple equivalent solutions that are associated to alternative subpaths. We also describe two sufficient conditions and we design efficient algorithms for identifying these subpaths. Comparisons of the results achieved by our tool with the ones obtained with recent assemblers are presented.

59 BASIC BIOLOGICAL SCIENCES↗

Capacitated p -hub approach for park-and-ride facility location problem under nested logit demand function: polyhedral approaches

By generalizing the unconstrained p-hub approach for the park-and-ride (P&R) facility location problem under the multinomial logit demand function, the capacitated p-hub approach for the problem under the nested logit demand function captures a broader range of real-world cases. To solve this problem optimally, we introduce a mixed-integer linear program and accelerate its solution by enhancing the branch-and-cut procedure. To address the problem at a large scale, we introduce two other polyhedral approaches: variable neighborhood search (VNS) and adaptive randomized rounding (ARR). Downtown areas in Seoul have a high modal share of public transportation and congested road traffic, yet P&R has not been widely implemented. Therefore, we apply the ARR procedure to solve a real-world problem using traffic and geographic data from the Seoul metropolitan area. ARR performs better than VNS and addresses real-world cases. The solutions obtained by ARR present a phased expansion plan that encourages policymakers to start installing a small number of P&Rs immediately.

Capacitated p-hub approach↗

SimCCS: An open-source tool for optimizing CO 2 capture, transport, and storage infrastructure

Commercial-scale carbon capture and storage (CCS) technology will involve deploying infrastructure on a massive and costly scale. This effort will require careful and comprehensive planning to ensure that capture locations, storage sites, and the dedicated CO 2 distribution pipelines are selected in a robust and cost-effective manner. Presented in 2009, SimCCS is an optimization model for integrated system design that enables researchers, stakeholders, and policy makers to design CCS infrastructure networks. SimCCS 2.0 is a complete, ground-up redesign that is now a portable software package, useable and shareable by the CCS research, industrial, policy, and public communities. SimCCS 2.0 integrates multiple new capabilities including a refined optimization model, novel candidate network generation techniques, and optional integration with high-performance computing platforms. Accessing user-provided CO 2 source, sink, and transportation data, SimCCS 2.0 creates candidate transportation routes and formalizes an optimization problem that determines the most cost-effective CCS system design. This optimization problem is further solved either through a high-performance computing interface, or through third-party software on a local desktop computing platform. Finally, SimCCS 2.0 employs an open-access geographic information system framework to enable analysis and visualization capabilities. SimCCS 2.0 is written in Java and is publicly available via GitHub to encourage collaboration, modification, and community development.

42 ENGINEERING↗

Generation of feasible integer solutions on a massively parallel computer using the feasibility pump

Here, we present an approach to parallelize generation of feasible mixed integer solutions of mixed integerlinear programs in distributed memory high performance computing environments. This approachcombines a parallel framework with feasibility pump (FP) as the rounding heuristic. It runs multiple FPinstances with different starting solutions concurrently, while allowing them to share information. Ourcomputational results suggest that the improvement resulting from parallelization using our approach is statistically significant.

97 MATHEMATICS AND COMPUTING↗