Search NASA⌕ Search

SEARCH · Search NASA

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 361 records · Page 20

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↗

Optimizing the design and operation of water networks: Two decomposition approaches

We consider the design and operation of water networks simultaneously. Water network problems can be divided into two categories: the design problem and the operation problem. The design problem involves determining the appropriate pipe sizing and placements of pump stations, while the operation problem involves scheduling pump stations over multiple time periods to account for changes in supply and demand. Our focus is on networks that involve water co-produced with oil and gas. While solving the optimization formulation for such networks, we found that obtaining a primal (feasible) solution is more challenging than obtaining dual bounds using off-the-shelf mixed-integer nonlinear programming solvers. Therefore, we propose two methods to obtain good primal solutions. One method involves a decomposition framework that utilizes a convex reformulation, while the other is based on time decomposition. To test our proposed methods, we conduct computational experiments on a network derived from the PARETO case study.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Routing Problem for Unmanned Aerial Vehicle Patrolling Missions - A Progressive Hedging Algorithm

This paper presents a two-stage stochastic program to model a routing problem involving an Unmanned Aerial Vehicle (UAV) in the context of patrolling missions. In particular, given a set of targets and a set of supplemental targets corresponding to each target, the first stage decisions involve finding the sequence in which the vehicle has to visit the set of targets. Upon reaching each target, the UAV collects information and if the operator of the UAV deems that the information collected is not of sufficient fidelity, then the UAV has to visit all the supplemental targets corresponding to that target to collect additional information before proceeding to visit the next target. The problem is solved using a progressive hedging algorithm and extensive computational results corroborating the effectiveness of the proposed model and the solution methodology is presented.

33 ADVANCED PROPULSION SYSTEMS↗

Resource distribution under spatiotemporal uncertainty of disease spread: Stochastic versus robust approaches

We consider the problem of optimizing locations of distribution centers (DCs) and plans for distributing resources such as test kits and vaccines, under spatiotemporal uncertainties of disease spread and demand for the resources. We aim to balance the operational cost (including costs of deploying facilities, shipping, and storage) and quality of service (reflected by demand coverage), while ensuring equity and fairness of resource distribution across multiple populations. We compare a sample-based stochastic programming (SP) approach with a distributionally robust optimization (DRO) approach using a moment-based ambiguity set. Numerical studies are conducted on instances of distributing COVID-19 vaccines in the United States and test kits, to compare SP and DRO models with a deterministic formulation using estimated demand and with the current resource distribution plans implemented in the US. We demonstrate the results over distinct phases of the pandemic to estimate the cost and speed of resource distribution depending on scale and coverage, and show the “demand-driven” properties of the SP and DRO solutions. Furthermore, our results further indicate that if the worst-case unmet demand is prioritized, then the DRO approach is preferred despite of its higher overall cost. Nevertheless, the SP approach can provide an intermediate plan under budgetary restrictions without significant compromises in demand coverage.

97 MATHEMATICS AND COMPUTING↗

Benders Cut Classification via Support Vector Machines for Solving Two-Stage Stochastic Programs

In this work, we consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification step in each iteration to selectively generate cuts that are more likely to be valuable cuts. The LearnBD algorithm includes two phases: (i) sampling cuts and collecting information from training problems and (ii) solving testing problems with a support vector machine (SVM) cut classifier. We run the LearnBD algorithm on instances of capacitated facility location and multicommodity network design under uncertain demand. Our results show that SVM cut classifier works effectively for identifying valuable cuts, and the LearnBD algorithm reduces the total solving time of all instances for different problems with various sizes and complexities.

97 MATHEMATICS AND COMPUTING↗

Framework for optimization of long-term, multi-period investment planning of integrated urban energy systems

In order to achieve stringent greenhouse gas emission reductions, a transition of our entire energy system from fossil to renewable resources needs to be designed. Such an energy transition brings two main challenges: most renewables generate variable electric energy, yet most demand is currently not electric (carrier mismatch) and does not always manifest at the same time as supply (temporal mismatch). Integrating multiple energy infrastructures can address both challenges by using the synergy between different energy carriers; building on existing infrastructure, while allowing a robust and flexible integration of the new. This paper proposes an optimization framework for long-term, multi-period investment planning of urban energy systems in an integrated manner. We formulate it as a mixed-integer linear program, combining a capacitated facility location with a multi-dimensional, capacitated network design problem. It includes generation and network expansion planning as well as interconnections between networks and storage infrastructure for each energy system. It can incorporate pathway effects like techno-economic developments, policy measures, and weather variations. The intended use is to support urban decision makers with long-term investment planning, though it can be tailored to fit other geographical or temporal scales. We demonstrate the model using two cases based on an average city in The Netherlands, which wants to reduce its CO 2 -emissions with 95% by 2050. In the first case, we include explicit carbon-emission constraints to study the effects of the carrier mismatch. In the second case, we implement interannual weather variations to analyze the temporal mismatch. The results give valuable insights into the energy transition design strategy for urban decision makers. They also show the future potential, as well as the computational challenges of the optimization framework.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Optimal design of sustainable cellulosic biofuel supply chains: Multiobjective optimization coupled with life cycle assessment and input-output analysis

This article addresses the optimal design and planning of cellulosic ethanol supply chains under economic, environmental, and social objectives. The economic objective is measured by the total annualized cost, the environmental objective is measured by the life cycle greenhouse gas emissions, and the social objective is measured by the number of accrued local jobs. A multiobjective mixed-integer linear programming (mo-MILP) model is developed that accounts for major characteristics of cellulosic ethanol supply chains, including supply seasonality and geographical diversity, biomass degradation, feedstock density, diverse conversion pathways and byproducts, infrastructure compatibility, demand distribution, regional economy, and government incentives. Aspen Plus models for biorefineries with different feedstocks and conversion pathways are built to provide detailed techno-economic and emission analysis results for the mo-MILP model, which simultaneously predicts the optimal network design, facility location, technology selection, capital investment, production planning, inventory control, and logistics management decisions. The mo-MILP problem is solved with an e-constraint method; and the resulting Pareto-optimal curves reveal the tradeoff between the economic, environmental, and social dimensions of the sustainable biofuel supply chains. The proposed approach is illustrated through two case studies for the state of Illinois.

09 BIOMASS FUELS↗

Evaluating demand response opportunities for power systems resilience using MILP and MINLP Formulations

While peak shaving is commonly used to reduce power costs, chemical process facilities that can reduce power consumption on demand during emergencies (e.g., extreme weather events) bring additional value through improved resilience. For process facilities to effectively negotiate demand response (DR) contracts and make investment decisions regarding flexibility, they need to quantify their additional value to the grid. We present a grid–centric mixed–integer stochastic programming framework to determine the value of DR for improving grid resilience in place of capital investments that can be cost prohibitive for system operators. We formulate problems using both a linear approximation and a nonlinear alternating current power flow model. Our numerical results with both models demonstrate that DR can be used to reduce the capital investment necessary for resilience, increasing the value that chemical process facilities bring through DR. Furthermore, the linearized model often underestimates the amount of DR needed in our case studies.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Designing a GIS-based supply chain for producing carinata-based sustainable aviation fuel in Georgia, USA

Carinata is a potential crop for sustainable aviation fuel (SAF) production in the southern USA. However, as a novel crop, the cost-effectiveness and environmental feasibility of carinata feedstock are unknown, and there are questions about the optimal supply chain configuration for carinata-based SAF production. This study aims to design a supply chain model for carinata-based SAF production by optimizing the location of farms and facilities (e.g. storage units, crushing mills, biorefineries) for a minimum transportation cost under a set of supply and demand conditions. An integrated mixed-integer linear programming (MILP) model was combined with geographical information system (GIS) analysis to design a spatially explicit supply chain configuration. The GIS-based network analysis considered all of the counties in Georgia to set the candidate locations of carinata farms and facilities, and determined minimum cost and emission routes between those counties and the airport using existing transportation networks and modes (e.g. road, rail and pipeline). The MILP model determined the final selection of the farms and the number of facilities and their locations over those minimum-cost routes. With this supply chain configuration, the minimum price of SAF was $\$$0.92 L –1 , which is $\$$0.44 higher than conventional aviation fuel (CAF). The associated carbon intensity of SAF was estimated at 940.7 g CO 2 e L –1 , a reduction of 66% relative to the carbon intensity of equivalent CAF. The study found that a carbon tax (or subsidy) of $\$$230.48 t CO 2 e –1 would be needed to overcome the cost differential with CAF and promote carinata-based SAF in Georgia.

09 BIOMASS FUELS↗

Holistic fleet optimization incorporating system design considerations

The methodology described in this article enables a type of holistic fleet optimization that simultaneously considers the composition and activity of a fleet through time as well as the design of individual systems within the fleet. Often, real-world system design optimization and fleet-level acquisition optimization are treated separately due to the prohibitive scale and complexity of each problem. Importantly, this means that fleet-level schedules are typically limited to the inclusion of predefined system configurations and are blind to a rich spectrum of system design alternatives. Similarly, system design optimization often considers a system in isolation from the fleet and is blind to numerous, complex portfolio-level considerations. In reality, these two problems are highly interconnected. To properly address this system-fleet design interdependence, we present a general method for efficiently incorporating multi-objective system design trade-off information into a mixed-integer linear programming (MILP) fleet-level optimization. This work is motivated by the authors' experience with large-scale DOD acquisition portfolios. However, the methodology is general to any application where the fleet-level problem is a MILP and there exists at least one system having a design trade space in which two or more design objectives are parameters in the fleet-level MILP.

97 MATHEMATICS AND COMPUTING↗

Probabilistic N - k failure-identification for power systems

This work considers a probabilistic generalization of the N - k failure-identification problem in power transmission networks, where the probability of failure of each component in the network is known a priori and the goal of the problem is to find a set of k components that maximizes disruption to the system loads weighted by the probability of simultaneous failure of the k components. The resulting problem is formulated as a bilevel mixed-integer nonlinear program. Convex relaxations, linear approximations, and heuristics are developed to obtain feasible solutions that are close to the optimum. A general cutting-plane algorithm is proposed to solve the convex relaxation and linear approximations of the N - k problem. Extensive numerical results corroborate the effectiveness of the proposed algorithms on small-, medium-, and large-scale test instances; the test instances include the IEEE 14-bus system, the IEEE single-area and three-area RTS96 systems, the IEEE 118-bus system, the WECC 240-bus test system, the 1354-bus PEGASE system, and the 2383-bus Polish winter-peak test system.

24 POWER TRANSMISSION AND DISTRIBUTION↗

State elimination for mixed‐integer optimal control of partial differential equations by semigroup theory

Abstract Mixed‐integer optimal control problems governed by partial differential equations (MIPDECOs) are powerful modeling tools but also challenging in terms of theory and computation. We propose a highly efficient state elimination approach for MIPDECOs that are governed by partial differential equations that have the structure of an abstract ordinary differential equation in function space. This allows us to avoid repeated calculations of the states for all time steps, and our approach is applied only once before starting the optimization. The presentation of theoretical results is complemented by numerical experiments.

97 MATHEMATICS AND COMPUTING↗

Translational Systems Pharmacology‐Based Predictive Assessment of Drug‐Induced Cardiomyopathy

Drug‐induced cardiomyopathy contributes to drug attrition. We compared two pipelines of predictive modeling: (1) applying elastic net (EN) to differentially expressed genes (DEGs) of drugs; (2) applying integer linear programming (ILP) to construct each drug's signaling pathway starting from its targets to downstream proteins, to transcription factors, and to its DEGs in human cardiomyocytes, and then subjecting the genes/proteins in the drugs' signaling networks to EN regression. We classified 31 drugs with availability of DEGs into 13 toxic and 18 nontoxic drugs based on a clinical cardiomyopathy incidence cutoff of 0.1%. The ILP‐augmented modeling increased prediction accuracy from 79% to 88% (sensitivity: 88%; specificity: 89%) under leave‐one‐out cross validation. The ILP‐constructed signaling networks of drugs were better predictors than DEGs. Per literature, the microRNAs that reportedly regulate expression of our six top predictors are of diagnostic value for natural heart failure or doxorubicin‐induced cardiomyopathy. This translational predictive modeling might uncover potential biomarkers.

59 BASIC BIOLOGICAL SCIENCES↗

Cutting planes for the multistage stochastic unit commitment problem

As renewable energy penetration rates continue to increase in power systems worldwide, new challenges arise for system operators in both regulated and deregulated electricity markets to solve the security-constrained coal-fired unit commitment problem with intermittent generation (due to renewables) and uncertain load, in order to ensure system reliability and maintain cost effectiveness. In this paper, we study a security-constrained coal-fired stochastic unit commitment model, which we use to enhance the reliability unit commitment process for day-ahead power system operations. In our approach, we first develop a deterministic equivalent formulation for the problem, which leads to a large-scale mixed-integer linear program. Then, we verify that the turn on/off inequalities provide a convex hull representation of the minimum-up/down time polytope under the stochastic setting. Next, we develop several families of strong valid inequalities mainly through lifting schemes. In particular, by exploring sequence independent lifting and subadditive approximation lifting properties for the lifting schemes, we obtain strong valid inequalities for the ramping and general load balance polytopes. Lastly, branch-and-cut algorithms are developed to employ these valid inequalities as cutting planes to solve the problem. Our computational results verify the effectiveness of the proposed approach.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

A mixed-integer PDE-constrained optimization formulation for constructing electromagnetic cloaks with multiple materials

We study the design of an electromagnetic cloak from multiple materials with an additional constraint on the mass of the cloak. Our problem is an example of a topology optimization problem, and we formulate this problem as a mixed-integer partial-differential equation constrained optimization (MIPDECO) problem, where Maxwell’s equation models the propagation of the wave through the cloak and surrounding medium. We use binary variables to model the assignment of the different materials, and their relevant properties (permittivity and density). The mass constraint adds a nontrivial constraint to this problem. We propose a two-phase strategy to solve this problem. In the first phase, we solve a continuous relaxation, and then propose a new variant of the feasibility pump that exploits the structure of the PDE to obtain an initial integral solution candidate. In the second phase, we use a trust-region approach to improve this incumbent. We also consider a continuation or mesh-sequencing approach to find better solutions faster on consecutively finer meshes. We present detailed numerical results to illustrate the effectiveness of our approaches for constructing multi-material cloaks with a mass constraint.

Calculus of Variations and Optimization↗

The potential of quantum annealing for rapid solution structure identification

Abstract The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing’s performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.

97 MATHEMATICS AND COMPUTING↗

Algorithms for Heterogeneous, Multiple Depot, Multiple Unmanned Vehicle Path Planning Problems

Unmanned vehicles, both aerial and ground, are being used in several monitoring applications to collect data from a set of targets. This article addresses a problem where a group of heterogeneous aerial or ground vehicles with different motion constraints located at distinct depots visit a set of targets. The vehicles also may be equipped with different sensors, and therefore, a target may not be visited by any vehicle. The objective is to find an optimal path for each vehicle starting and ending at its respective depot such that each target is visited at least once by some vehicle, the vehicle–target constraints are satisfied, and the sum of the length of the paths for all the vehicles is minimized. Two variants of this problem are formulated (one for ground vehicles and another for aerial vehicles) as mixed-integer linear programs and a branchand- cut algorithm is developed to compute an optimal solution to each of the variants. Computational results show that optimal solutions for problems involving 100 targets and 5 vehicles can be obtained within 300 seconds on average, further corroborating the effectiveness of the proposed approach.

33 ADVANCED PROPULSION SYSTEMS↗

Sequence of polyhedral relaxations for nonlinear univariate functions

Here, given a nonlinear, univariate, bounded, and differentiable function f(x), this article develops a sequence of Mixed Integer Linear Programming (MILP) and Linear Programming (LP) relaxations that converge to the graph of f(x) and its convex hull, respectively. Theoretical convergence of the sequence of relaxations to the graph of the function and its convex hull is established. For nonlinear non-convex optimization problems, the relaxations presented in this article can be used to construct tight MILP and LP relaxations. These MILP and the LP relaxations can also be used with MILP-based and spatial branch-and-bound based global optimization algorithms, respectively.

42 ENGINEERING↗