Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Integer 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
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Real-time Ridesharing for Transportation Hubs with Demand and Supply Uncertainty

Transportation hubs in major cities generate a significant amount of trips by taxis and for-hail vehicles (FHV), with many of the trips sharing similar destinations. This suggests promising opportunities to leverage the collective travel needs with dedicated ridesharing solutions to reduce the externalities of excessive traffic at transportation hubs. In this study, we develop a novel dynamic ridesharing approach to serve trips from the transportation hub by considering (1) demand (new passengers) and supply (newly available vehicles) in the near future and (2) the uncertainty of future predictions. Our approach consists of two stages. In the first stage, we develop a data structure called hub mobility tree to generate potential combinations of shareable trips as candidate schedules efficiently. Then the generated schedules are used in the second stage to formulate the stochastic hub-based ridesharing problem (SHRP), which is a stochastic integer programming problem with the objective to maximize the total expected ridesharing profit over time. Due to the prohibitive number of shareable trips, we then approximately solve SHRP by the sample average approximate method (SAA), and a dual Lagrangian technique is implemented to further improve the scalability of the solution approach. We demonstrate the performances of the proposed method by simulating the ridesharing service at JFK airport using NYC taxi and FHV data. The results indicate that the proposed method outperforms the myopic ridesharing (maximize profit for a single time step) and the rolling horizon method with point estimation of future demand and supply.

dynamic ridesharing↗
DOE OSTI2025

Automated shaker placement and regularized input estimation for MIMO testing.

Multi-input, multi-output (MIMO) testing is used in component qualification to reproduce operational responses in the laboratory. It is often preferred to single-input and base-shake testing because of the potential for equivalent or better tests using smaller actuators and shorter test suites. Given a target response, two key steps in MIMO test design are selecting actuator locations and solving for input loads. Actuator locations are often manually selected using expert judgment. If an automatic method is used, locations are usually determined by simulating the vibration control problem and minimizing a combination of the input energy and control residuals. To select a configuration, the relative importance of input energy and residuals must be specified. Specifying relative weights is, in general, a manual and subjective process. This paper develops an objective function that compares actuator configurations based on control accuracy and required input energy without any manual parameter tuning. The objective function uses an optimally selected tradeoff parameter for each candidate configuration. To choose actuator locations using the new objective function, a pivoting algorithm for integer programming problems is developed. Starting with an initial configuration (such as the one generated by a greedy algorithm), the pivoting algorithm guarantees an objective function decrease in each iteration until convergence is reached. In a simulation featuring a structure excited by a diffuse acoustic field, electrodynamic shaker locations and regularized inputs are solved for without any analyst-specified parameters. Simulations are performed in MIMO configurations where the number of target responses is less than, equal to, and greater than the number of actuators.

Multi-input multi-output↗
DOE OSTI2022

Partner with a Third-Party Delivery Service or Not? A Prediction-and-Decision Tool for Restaurants Facing Takeout Demand Surges During a Pandemic

Amidst the COVID-19 pandemic, restaurants become more reliant on no-contact pick-up or delivery ways for serving customers. As a result, they need to make tactical planning decisions such as whether to partner with online platforms, to form their own delivery team, or both. In this paper, we develop an integrated prediction-decision model to analyze the profit of combining the two approaches and to decide the needed number of drivers under stochastic demand. We first use the susceptible-infected-recovered (SIR) model to forecast future infected cases in a given region and then construct an autoregressive-moving-average (ARMA) regression model to predict food-ordering demand. Using predicted demand samples, we formulate a stochastic integer program to optimize food delivery plans. We conduct numerical studies using COVID-19 data and food-ordering demand data collected from local restaurants in Nuevo Leon, Mexico, from April to October 2020, to show results for helping restaurants build contingency plans under rapid market changes. Our method can be used under unexpected demand surges, various infection/vaccination status, and demand patterns. Here, our results show that a restaurant can benefit from partnering with third-party delivery platforms when (i) the subscription fee is low, (ii) customers can flexibly decide whether to order from platforms or from restaurants directly, (iii) customers require more efficient delivery, (iv) average delivery distance is long, or (v) demand variance is high.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Co-design optimization of combined heat and power-based microgrids

With the emergent need for clean and reliable energy resources, hybrid energy systems, such as the microgrid, are widely adopted in the United States. A microgrid can consist of various distributed energy resources, for instance, combined heat and power (CHP) systems. Here, the CHP module is a distributed cogeneration technology that produces electricity and recaptures heat generated as a by-product. It is an energy-efficient technology converting heat that would otherwise be wasted to valuable thermal energy. For an optimal system configuration, this study develops a novel co-design optimization framework for CHP-based cogeneration microgrids. The framework provides the stakeholder with a method to optimize investments and attain resilient operations. The proposed co-design framework has a mixed integer programming (MIP) model that outputs decisions for both plant designs and operating controls. The microgrid considered in this study contains six components: the CHP, boiler, heat recovery unit, thermal storage system, power storage system, and photovoltaic plant. After solving the MIP model, the optimal design parameters of each component can be found to minimize the total installation cost of all components in the microgrid. Furthermore, the online costs from energy production, operation, maintenance, machine startup, and disruption-induced unsatisfied loads are minimized by solving the optimal control decisions for operations. Case studies based on designing a CHP-based microgrid with empirical data are conducted. Moreover, we consider both nominal and disruptive operational scenarios to validate the performance of the proposed co-design framework in terms of a cost-effective, resilient system.

42 ENGINEERING↗
DOE OSTI2021

Enhancing Active Distribution Systems Resilience by Fully Distributed Self-Healing Strategy

Distributed restoration can exploit smart grid technologies to enhance the resilience of active distribution networks toward a self-healing smart grid. However, the large number of decision variables, especially the binary ones for reconfiguration, bring challenges to developing scalable distributed distribution service restoration (DDSR) strategies. This paper proposes a fully distributed solution procedure based on the alternating direction method of multipliers (ADMM) for mixed-integer programming problems and applies to develop the DDSR framework. The method consists of relax-drive-polish phases, 1) relaxing binary variables, and applying the convex ADMM as a warm start; 2) driving the solutions toward Boolean values through a proximal operator; 3) fixing the obtained binding binary variables and solving the rest of the problem to polish results and achieve a high-quality suboptimal solution. Then, an autonomous clustering strategy and consensus ADMM are integrated with the proposed method to realize the fully distributed cluster-based framework of DDSR. This framework can first determine DER scheduling and switch status for reconfiguration to energize the out-of-service areas from local faults, and then provide the load restoration solution in a distributed manner for total blackouts in large-scale distribution networks. Furthermore, the effectiveness and scalability of the proposed DDSR framework are demonstrated through testing on the IEEE 123-node, IEEE 8500-node, and synthetic 100k-node test feeders.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Optimization of a Mixed Fleet of Aerial Drones for Medical Supplies: A Case Study of Blood Delivery Logistics

Aerial drones have emerged as an innovative solution for faster transportation of time-sensitive items (e.g., emergency medical supplies), potentially reducing the transmission of contagious diseases and enhancing healthcare availability through contactless autonomous delivery. We study fleet sizing and efficient scheduling of a mixed fleet of drones for delivering time-sensitive medical items having distinct release and due times to minimize the required fleet size and fleet composition, the required number of additional batteries, and the total energy consumption. We continuously track the remaining battery energy of drones to determine the optimal timing for battery replacement, rather than replacing the battery at each node. Using actual drone flight test data, we employed a machine learning (ML) method to estimate the energy consumption of different drone types during flight segments for different operating parameters. We present a novel mixed-integer programming model to efficiently formulate the problem that integrates the estimated energy consumption functions from ML. We propose a new greedy heuristic (GH) algorithm and a customized genetic algorithm (GA) for solving large-scale instances of this problem faster. Results demonstrate that the GH algorithm is substantially faster than the accelerated CPLEX and the GA, while sacrificing the solution quality by a small amount. Results based on an actual blood sample delivery case study from Pendleton, Oregon, United States, show that using a mixed fleet of drones reduces the total cost and total energy consumption up to 18.18% and 28.7%, respectively, compared to using a homogeneous fleet.

29 - ENERGY PLANNING, POLICY AND ECONOMY↗
DOE OSTI2024

Aerial drone fleet deployment optimization with endogenous battery replacements for direct delivery of time-sensitive products

Aerial drones offer a distinct potential to reduce the delivery time and energy consumption for the delivery of time-sensitive and small products. However, there is still a need in the relevant industry to understand the performance of drone-based delivery under different business needs and drone operating conditions. We studied a drone deployment optimization problem for direct delivery of time-sensitive products with release dates to customers maintaining a specified time window. This paper presents a new mixed-integer programming model, new valid inequalities, a new greedy heuristic algorithm, and a Genetic algorithm to help business owners optimally schedule and route their drone fleet minimizing the required fleet size, the required number of additional batteries, and total energy consumption. A realistic feature of the optimization method is that instead of replacing the drone battery after each return to the depot, it keeps track of the remaining energy in the drone battery and decides on battery replacements accounting for the drone routing and the user-specified minimum required battery energy. Numerical results based on real data from drone flight tests and prepared food delivery industry provide insights into the effect of different practical drone operating parameters on the required fleet size, the required number of battery replacements, and energy consumption. Here, results demonstrate that the proposed heuristic algorithm substantially outperforms the accelerated CPLEX in runtime while sacrificing the solution quality by a small amount. Additionally, results show that using a mixed fleet of hexacopter and quadcopter drones reduces the total energy consumption by 48.52% compared to using a homogeneous fleet of only hexacopters.

Drone energy consumption↗
DOE OSTI2020

Novel Geometric Operations for Linear Programming

This report summarizes the work performed under the project "Linear Programming in Strongly Polynomial Time." Linear programming (LP) is a classic combinatorial optimization problem heavily used directly and as an enabling subroutine in integer programming (IP). Specifically IP is the same as LP except that some solution variables must take integer values (e.g. to represent yes/no decisions). Together LP and IP have many applications in resource allocation including general logistics, and infrastructure design and vulnerability analysis. The project was motivated by the PI's recent success developing methods to efficiently sample Voronoi vertices (essentially finding nearest neighbors in high-dimensional point sets) in arbitrary dimension. His method seems applicable to exploring the high-dimensional convex feasible space of an LP problem. Although the project did not provably find a strongly-polynomial algorithm, it explored multiple algorithm classes. The new medial simplex algorithms may still lead to solvers with improved provable complexity. We describe medial simplex algorithms and some relevant structural/complexity results. We also designed a novel parallel LP algorithm based on our geometric insights and implemented it in the Spoke-LP code. A major part of the computational step is many independent vector dot products. Our parallel algorithm distributes the problem constraints across processors. Current commercial and high-quality free LP solvers require all problem details to fit onto a single processor or multicore. Our new algorithm might enable the solution of problems too large for any current LP solvers. We describe our new algorithm, give preliminary proof-of-concept experiments, and describe a new generator for arbitrarily large LP instances.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

SPAROW: Stochastic Programming and Related Optimization Workflows

SAND2026-16703O SPAROW: Stochastic Programming and Related Optimization Workflows is a Python library tool that facilitates the development and solution of stochastic programming problems. It provides a user-friendly class structure for defining stochastic programs through scenario-based representations of uncertainties. SPAROW incorporates multiple optimization strategies, including integer programming with all scenarios, progressive hedging, Benders decomposition, and Snoglode, a novel technique developed by Carnegie Mellon University. It also features interfaces to external solvers and functions that are commonly used in analysis workflows, making it applicable to a wide range of scientific and engineering design challenges, particularly in power grid planning. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Hart, William [Sandia National Lab. (SNL-NM), Albu↗
DOE OSTI2024

A Mixed Integer Linear Programming-basedDistributed Energy Management for Three-phaseUnbalanced Active Distribution Network

A mixed integer linear programming (MILP)–baseddistributed energy management for three-phase unbalancedactive distribution network is proposed. Modern distributionnetworks have becoming more and more active with increasingdeployment of microgrids, distributed energy resources (DERs)as well as controllable loads. Considering various ownership andcontrol models of microgrids, DERs and controllable loads, adistributed energy management was formulated using the alternatingdirection method of multipliers (ADMM) algorithm. ByADMM, the distribution management system (DMS) and theseactive components are coordinated through price signals, whichare adjusted according to the generation-load mismatch per nodeper phase. To enable resolution of the ADMM-based distributedoptimization using more accessible and popular MILP solver,different linearization techniques were proposed to linearize theaugmented Lagrangian terms and other nonlinear terms. Resultsof case studies on a three-phase active distribution network withthree microgrids and several DERs and controllable loads validatedthe effectiveness of proposed MILP-based distributed energymanagement. In addition, the capability of proposed method inmitigating phase power unbalance has been demonstrated.

Liu, Guodong↗
DOE OSTI2021

Optimizing design and dispatch of a renewable energy system

Renewable energy technologies are becoming increasingly important due to their cost-competitiveness, and because of enhanced climate concerns. We demonstrate the capabilities of an integer-programming optimization model that minimizes capital (investment) and operational costs, and utility charges, while adhering to system sizing constraints, demand requirements, and interoperability characteristics of the systems chosen. Furthermore, the model recommends an optimally sized mix of renewable energy, conventional generation, and energy storage technologies, while simultaneously optimizing the corresponding dispatch strategy. Our case studies explore several venues, i.e., a small campus and a local hospital, with complex utility rate tariffs, multi-technology integration opportunities, and incentives for renewable power production. Using an optimization model, versus applying rules of thumb, can produce millions of dollars in savings over a 25-year time horizon and result in thousands of kilowatts of installed renewable energy.

25 ENERGY STORAGE↗
DOE OSTI2023

Mathematical Programming Models for Shale Oil & Gas Development: A Review and Perspective

Here, in this paper, we provide a comprehensive review of mathematical programming models for shale oil & gas development, and we offer a perspective on outstanding research opportunities. We distinguish contributions in five major topic areas, namely: (1) development planning, (2) water management, (3) production optimization, (4) supplies, gathering & processing, and (5) life cycle analysis & sustainability. We highlight how various types of mathematical programming models (i.e., linear programs, nonlinear programs, mixed-integer linear programs, mixed-integer nonlinear programs) have been proposed primarily by the Process Systems Engineering community to address the respective decision-making problems, and we highlight instances of successful deployment in industry. Finally, based on a critical assessment of the existing body of work, we identify opportunities for future research across the major topic areas.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

A shared-mobility-based framework for evacuation planning and operations under forecast uncertainty

To meet evacuation needs from carless populations who need personalized assistance to evacuate safely, in this article we propose a ridesharing-based evacuation program that recruits volunteer drivers before a disaster strikes, and then matches volunteer drivers with evacuees once demand is realized. Here we optimize resource planning and evacuation operations under uncertain spatiotemporal demand, and construct a two-stage stochastic mixed-integer program to ensure high demand fulfillment rates. We consider three formulations to improve the number of evacuees served, by minimizing an expected penalty cost, imposing a probabilistic constraint, and enforcing a constraint on the conditional value at risk of the total number of unserved evacuees, respectively. We discuss the benefits and disadvantages of the different risk measures used in the three formulations, given certain carless population sizes and the variety of evacuation modes available. We also develop a heuristic approach to provide quick, dynamic and conservative solutions. We demonstrate the performance of our approaches using five different networks of varying sizes based on regions of Charleston County, South Carolina, an area that experienced a mandatory evacuation order during Hurricane Florence, and utilize real demographic data and hourly traffic count data to estimate the demand distribution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Model Predictive Control of Discrete-Continuous Energy Systems via Generalized Disjunctive Programming

Generalized Disjunctive Programming (GDP) provides an alternative framework to model optimization problems with both discrete and continuous variables. The key idea behind GDP involves the use of logical disjunctions to represent discrete decisions in the continuous space, and logical propositions to denote algebraic constraints in the discrete space. Compared to traditional mixed-integer programming (MIP), the inherent logic structure in GDP yields tighter relaxations that are exploited by global branch and bound algorithms to improve solution quality. In this paper, we present a general GDP model for optimal control of hybrid systems that exhibit both discrete and continuous dynamics. Specifically, we use GDP to formulate a model predictive control (MPC) model for piecewise-affine systems with implicit switching logic. As an example, the GDP-based MPC approach is used as a supervisory control to improve energy efficiency in residential buildings with binary on/off, relay-based thermostats. A simulation study is used to demonstrate the validity of the proposed approach, and the improved solution quality compared to existing MIPbased control approaches.

Bhattacharya, Arnab↗
DOE OSTI2021

Multi-Period Active Distribution Network Planning Using Multi-Stage Stochastic Programming and Nested Decomposition by SDDIP

This paper presents a multi-period active distribution network planning (ADNP) with distributed generation (DG). The objective of the proposed ADNP is to minimize the total planning cost, subject to both investment and operation constraints. The paper proposes a multi-stage stochastic optimization model to address DG uncertainties over several periods, in which the decisions are made sequentially by only using the present-stage information. A nested decomposition method is proposed which applies the stochastic dual dynamic integer programming (SDDIP) method to address computational intractabilities of the proposed ADNP approach. The presented numerical results and discussions on a 33-bus distribution system and a large-scale 906-bus system verify the effectiveness of the proposed ADNP method and its solution method.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Domain Decomposition for Integer Optimal Control with Total Variation Regularization

Total variation integer optimal control problems admit solutions and necessary optimality conditions via geometric variational analysis. In spite of the existence of said solutions, algorithms which solve the discretized objective suffer from high numerical cost associated with the combinatorial nature of integer programming. Hence, such methods are often limited to small and medium-sized problems. We propose a globally convergent, coordinate descent–inspired algorithm that allows tractable subproblem solutions restricted to a partition of the domain. Our decomposition method solves relatively small trust-region subproblems that modify the control variable on a subdomain only. Given nontrivial subdomain overlap, we prove that a global first-order necessary optimality condition is equivalent to a first-order necessary optimality condition per subdomain. We additionally show that a sufficient decrease is achieved on a single subdomain by way of a trust-region subproblem solver using geometric measure–theoretic arguments, which we integrate with a greedy patch selection to prove convergence of our algorithm. In conclusion, we demonstrate the practicality of our algorithm on a benchmark large-scale, PDE-constrained integer optimal control problem and find that our method is faster than the state of the art.

domain decomposition↗
DOE OSTI2024

Compressing branch-and-bound trees

A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? Here we believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Dispatch optimization of a concentrating solar power system under uncertain solar irradiance and energy prices

The integration of thermal energy storage into a concentrating solar power system allows for mitigating some of the risk associated with uncertain solar irradiance and uncertain energy prices. We solve a 48 h dispatch optimization model with continually updated conditional point forecasts of both direct normal irradiance (DNI) and electricity prices with a rolling-horizon scheme at hourly resolution over the course of a year. Joint, conditional forecasts for DNI and prices are formed using an autoregressive moving-average time series model with exogenous weather predictors. We guide dispatch using a mixed-integer programming model, but in order to evaluate performance we use the System Advisor Model (SAM) of the National Renewable Energy Laboratory. SAM is a techno-economic simulation model that accounts for plant thermodynamics with higher fidelity. Our conditional DNI forecasts improve annual revenue by 4%–12% over using historical forecasts based on data from previous years. Conditional price forecasts improve annual revenue by 6%–19% in the real-time market over analogous historical forecasts. Updating these forecasts every six hours, rather than every 24 h, further improves annual revenue by 5%–6%. Here, we also investigate a method that values terminal inventory in our dispatch optimization model, again when used in a rolling-horizon scheme.

14 SOLAR ENERGY↗