Search NASA⌕ Search

SEARCH · Search NASA

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 325 records · Page 18

Control Allocation with Load Balancing

Next generation aircraft with a large number of actuators will require advanced control allocation methods to compute the actuator commands needed to follow desired trajectories while respecting system constraints. Previously, algorithms were proposed to minimize the l1 or l2 norms of the tracking error and of the actuator deflections. The paper discusses the alternative choice of the l(infinity) norm, or sup norm. Minimization of the control effort translates into the minimization of the maximum actuator deflection (min-max optimization). The paper shows how the problem can be solved effectively by converting it into a linear program and solving it using a simplex algorithm. Properties of the algorithm are also investigated through examples. In particular, the min-max criterion results in a type of load balancing, where the load is th desired command and the algorithm balances this load among various actuators. The solution using the l(infinity) norm also results in better robustness to failures and to lower sensitivity to nonlinearities in illustrative examples.

Bodson, Marc↗

Resource Balancing Control Allocation

Next generation aircraft with a large number of actuators will require advanced control allocation methods to compute the actuator commands needed to follow desired trajectories while respecting system constraints. Previously, algorithms were proposed to minimize the l1 or l2 norms of the tracking error and of the control effort. The paper discusses the alternative choice of using the l1 norm for minimization of the tracking error and a normalized l(infinity) norm, or sup norm, for minimization of the control effort. The algorithm computes the norm of the actuator deflections scaled by the actuator limits. Minimization of the control effort then translates into the minimization of the maximum actuator deflection as a percentage of its range of motion. The paper shows how the problem can be solved effectively by converting it into a linear program and solving it using a simplex algorithm. Properties of the algorithm are investigated through examples. In particular, the min-max criterion results in a type of resource balancing, where the resources are the control surfaces and the algorithm balances these resources to achieve the desired command. A study of the sensitivity of the algorithms to the data is presented, which shows that the normalized l(infinity) algorithm has the lowest sensitivity, although high sensitivities are observed whenever the limits of performance are reached.

Frost, Susan A.↗

JAS3D v. 2.4

JAS3D is a three-dimensional finite element program originally designed to solve Lagrangian quasistatic non-linear mechanics problems, and subsequently extended to include both implicit and explicit dynamics. A set of continuum equations describes the nonlinear mechanics involving large rotation and strain. Innovative multilevel nonlinear iterative methods are used to solve the equations. A wide variety of material constitutive models are available, and contact interface logic is implemented. Two Lagrangian uniform-strain elements are available: an eighth-node hexahedron for solids and a four-node quadrilateral for shells. Both use hourglass stiffness to control zero-energy modes. In addition, a version of the hexahedron is available with uniform pressure and a deviatoric response scalable from the mean response of the original element up to a fully-integrated response. Bodies under analysis may be loaded by surface pressures and concentrated forces, specified displacements, or body forces from gravity, steady-state transport, or thermal expansion.

Heinstein, Martin↗

Foraging with MUSHROOMS: A Mixed-integer Linear Programming Scheduler for Multimessenger Target of Opportunity Searches with the Zwicky Transient Facility

Electromagnetic follow-up of gravitational-wave detections is very resource intensive, taking up hours of limited observation time on dozens of telescopes. Creating more efficient schedules for follow-up will lead to a commensurate increase in counterpart location efficiency without using more telescope time. Widely used in operations research and telescope scheduling, mixed-integer linear programming is a strong candidate to produce these higher-efficiency schedules, as it can make use of powerful commercial solvers that find globally optimal solutions to provided problems. We detail a new target-of-opportunity scheduling algorithm designed with Zwicky Transient Facility in mind that uses mixed-integer linear programming. We compare its performance to gwemopt, the tuned heuristic scheduler used by the Zwicky Transient Facility and other facilities during the third LIGO–Virgo gravitational-wave observing run. This new algorithm uses variable-length observing blocks to enforce cadence requirements and to ensure field observability, along with having a secondary optimization step to minimize slew time. We show that by employing a hybrid method utilizing both this scheduler and gwemopt, the previous scheduler used, in concert, we can achieve an average improvement in detection efficiency of 3%–11% over gwemopt alone for a simulated binary neutron star merger data set consistent with LIGO–Virgo's third observing run, highlighting the potential of mixed-integer target of opportunity schedulers for future multimessenger follow-up surveys.

B Parazin↗

High-Performance Algorithm for Solving the Diagnosis Problem

An improved method of model-based diagnosis of a complex engineering system is embodied in an algorithm that involves considerably less computation than do prior such algorithms. This method and algorithm are based largely on developments reported in several NASA Tech Briefs articles: The Complexity of the Diagnosis Problem (NPO-30315), Vol. 26, No. 4 (April 2002), page 20; Fast Algorithms for Model-Based Diagnosis (NPO-30582), Vol. 29, No. 3 (March 2005), page 69; Two Methods of Efficient Solution of the Hitting-Set Problem (NPO-30584), Vol. 29, No. 3 (March 2005), page 73; and Efficient Model-Based Diagnosis Engine (NPO-40544), on the following page. Some background information from the cited articles is prerequisite to a meaningful summary of the innovative aspects of the present method and algorithm. In model-based diagnosis, the function of each component and the relationships among all the components of the engineering system to be diagnosed are represented as a logical system denoted the system description (SD). Hence, the expected normal behavior of the engineering system is the set of logical consequences of the SD. Faulty components lead to inconsistencies between the observed behaviors of the system and the SD. Diagnosis the task of finding faulty components is reduced to finding those components, the abnormalities of which could explain all the inconsistencies. The solution of the diagnosis problem should be a minimal diagnosis, which is a minimal set of faulty components. The calculation of a minimal diagnosis is inherently a hard problem, the solution of which requires amounts of computation time and memory that increase exponentially with the number of components of the engineering system. Among the developments to reduce the computational burden, as reported in the cited articles, is the mapping of the diagnosis problem onto the integer-programming (IP) problem. This mapping makes it possible to utilize a variety of algorithms developed previously for IP to solve the diagnosis problem. In the IP approach, the diagnosis problem can be formulated as a linear integer optimization problem, which can be solved by use of well-developed integer-programming algorithms. This concludes the background information.

Fijany, Amir↗

PDE-constrained Optimization under Uncertainty

Uncertainty is pervasive in all science and engineering applications. Incorporating uncertainty in physical models is therefore both natural and vital. In doing so, we often arrive at parametric systems of partial differential equations (PDEs). When passing from simulation to optimization, we obtain (typically nonconvex) infinite-dimensional optimization problems that, upon discretization, result in extremely large-scale nonlinear programs. For example, consider a linear elliptic PDE on a two- dimensional domain with a single random coeffcient. If we sampled the random input with 10,000 realizations of the coeffcient, the resulting optimization problem would have 10,000 PDE constraints. Furthermore, discretizing each PDE with piecewise linear finite elements on a 100X100 uni- form quadrilateral mesh results in 100,000,000 degrees of freedom. As a result, the critical components for ensuring mesh-independent performance of numerical optimization methods in the deterministic setting, for example, solution regularity and generalized differentiability, are even more critical in the stochastic setting.

42 ENGINEERING↗

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗

The application of general aerodynamic lifting surface elements to problems in unsteady transonic flow

A study was conducted to investigate the feasibility of using combined subsonic and supersonic linear theory as a means for solving unsteady transonic flow problems in an economical and yet realistic manner. With some modification, existing linear theory methods are combined into a single program and a simple algorithm is derived for determining interference between lifting surface elements of different Mach number. The method is applied to a wide variety of problems for which measured unsteady pressure distributions and Mach number distributions are available. By comparing theory and experiment, the transonic method solutions show a significant improvement over uniform flow solutions. It is concluded that with these refinements the method will provide a means for performing realistic transonic flutter and dynamic response analyses at costs which are compatible with current linear theory based solutions.

Cunningham, A. M., Jr.↗

BEST3D user's manual: Boundary Element Solution Technology, 3-Dimensional Version 3.0

The theoretical basis and programming strategy utilized in the construction of the computer program BEST3D (boundary element solution technology - three dimensional) and detailed input instructions are provided for the use of the program. An extensive set of test cases and sample problems is included in the manual and is also available for distribution with the program. The BEST3D program was developed under the 3-D Inelastic Analysis Methods for Hot Section Components contract (NAS3-23697). The overall objective of this program was the development of new computer programs allowing more accurate and efficient three-dimensional thermal and stress analysis of hot section components, i.e., combustor liners, turbine blades, and turbine vanes. The BEST3D program allows both linear and nonlinear analysis of static and quasi-static elastic problems and transient dynamic analysis for elastic problems. Calculation of elastic natural frequencies and mode shapes is also provided.

Source record↗

Justice 40 Tool (J40 Tool) v1.0

The Justice 40 tool provides a quantitative framework to support decision-making around equitable energy interventions at the community level. The tool calculates the optimal portfolio of policy interventions that explicitly mitigates energy insecurity of an eligible population, by reducing its disproportionate energy burden. The place-based analysis assumes a spatial census tract-level resolution and distinguishes different sociodemographic groups within each tract. Instead of focusing on a specific technology, the underlying J40 model captures the combined effect of a set of policy interventions, currently including weatherization, rooftop solar, community solar and community wind. For each tract, the model chooses the optimal (least cost) combination of interventions to address the disproportionate burden, considering the specific population demographics and techno-economic potentials of technologies. Mathematically, this problem is formalized as an optimization model and formulated as a linear program.

Heleno, Miguel↗

Mitigation-Aware Bidding Strategies in Electricity Markets

Market power exercise in the electricity markets distorts market prices and diminishes social welfare. Many markets have implemented market power mitigation processes to eliminate the impact of such behavior. The design of mitigation mechanisms has a direct influence on investors' profitability and thus mid-/long-term resource adequacy. In order to evaluate the effectiveness of the existing market power mitigation mechanisms, this paper proposes a mitigation-aware strategic bidding model and studies the bidding strategies of the market participants under current practice. The proposed bidding model has a bilevel structure with strategic participant's profit maximization problem in the upper level and the dispatch problem for market operators in the lower level. In particular, the consideration of potential offer mitigation is incorporated as upper-level constraints based on the conduct and impact tests. This bilevel problem is reduced to a single-level mixed-integer linear program using the KKT optimality conditions, duality theory, and linearization. Numerical results illustrate how a strategic player can exercise market power to achieve a higher profit even under the current market power mitigation process and we analyze the social impact that the market power exercise results.

Wu, Yiqian↗

A Bound- and Equality-Constrained Quadratic Programming Method for Image Reconstruction

Image deblurring is modeled as an ill-posed, linear inverse problem and can be written in terms of an optimization problem. By adding bound and equality constraints and/or penalty terms to the objective function, the problem is regularized and a viable solution exists; however, there are few methods available for solving such constrained problems. Here we formulate two regularized solutions into constrained optimization problems and adapt an iterative augmented Lagrangian solver. Results are shown on synthetic data in one- and two-dimensions, as well as on a radiograph used to calibrate the transmission curve of a pulsed power X-ray source at a U.S. Department of Energy radiography facility.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Mean-Variance Problems for Finite Horizon Semi-Markov Decision Processes

This paper deals with a mean-variance problem for finite horizon semi-Markov decision processes. The state and action spaces are Borel spaces, while the reward function may be unbounded. The goal is to seek an optimal policy with minimal finite horizon reward variance over the set of policies with a given mean. Using the theory of N-step contraction, we give a characterization of policies with a given mean and convert the second order moment of the finite horizon reward to a mean of an infinite horizon reward/cost generated by a discrete-time Markov decision processes (MDP) with a two dimension state space and a new one-step reward/cost under suitable conditions. We then establish the optimality equation and the existence of mean-variance optimal policies by employing the existing results of discrete-time MDPs. We also provide a value iteration and a policy improvement algorithms for computing the value function and mean-variance optimal policies, respectively. In addition, a linear program and the dual program are developed for solving the mean-variance problem.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Global Optimization via Quadratic Disjunctive Programming for Water Networks Design with Energy Recovery

Generalized disjunctive programming (GDP) models with bilinear and concave constraints, often seen in water network design, are challenging optimization problems. This work proposes quadratic and piecewise linear approximations for nonlinear terms to reformulate GDP models into quadratic GDP (QGDP) models that suitable solvers may solve more efficiently. We illustrate the benefits of the quadratic reformulation with a water treatment network design problem in which nonconvexities arise from bilinear terms in the mixers’ mass balances and concave investment cost functions of treatment units. Given the similarities with water network design problems, we suggest quadratic approximation for the GDP model for the optimal design of a large-scale reverse electrodialysis (RED) process. This power technology can recover energy from salinity differences between by-product streams of the water sector, such as desalination brine mixed with regenerated wastewater effluents. The solver Gurobi excels in handling QGDP problems, but weighing the problem’s precision and tractability balance is crucial. The piecewise linear approximation yields more accurate, yet larger QGDP models that may require longer optimization times in large-scale process synthesis problems.

Water Networks↗

Aerodynamic preliminary analysis system. Part 2: User's manual and program description

A comprehensive aerodynamic analysis program based on linearized potential theory is described. The solution treats thickness and attitude problems at subsonic and supersonic speeds. Three dimensional configurations with or without jet flaps having multiple nonplanar surfaces of arbitrary planform and open or closed slender bodies or noncircular contour are analyzed. Longitudinal and lateral-directional static and rotary derivative solutions are generated. The analysis is implemented on a time sharing system in conjunction with an input tablet digitizer and an interactive graphics input/output display and editing terminal to maximize its responsiveness to the preliminary analysis problem. Nominal case computation time of 45 CPU seconds on the CDC 175 for a 200 panel simulation indicates the program provides an efficient analysis for systematically performing various aerodynamic configuration tradeoff and evaluation studies.

Divan, P.↗

Aerodynamic preliminary analysis system. Part 1: Theory

A comprehensive aerodynamic analysis program based on linearized potential theory is described. The solution treats thickness and attitude problems at subsonic and supersonic speeds. Three dimensional configurations with or without jet flaps having multiple non-planar surfaces of arbitrary planform and open or closed slender bodies of non-circular contour may be analyzed. Longitudinal and lateral-directional static and rotary derivative solutions may be generated. The analysis was implemented on a time sharing system in conjunction with an input tablet digitizer and an interactive graphics input/output display and editing terminal to maximize its responsiveness to the preliminary analysis problem. Nominal case computation time of 45 CPU seconds on the CDC 175 for a 200 panel simulation indicates the program provides an efficient analysis for systematically performing various aerodynamic configuration tradeoff and evaluation studies.

Bonner, E.↗

SU-E-T-136: Assessment of Seasonal Linear Accelerator Output Variations and Associated Impacts

Purpose: Application of process control theory in quality assurance programs promises to allow earlier identification of problems and potentially better quality in delivery than traditional paradigms based primarily on tolerances and action levels. The purpose of this project was to characterize underlying seasonal variations in linear accelerator output that can be used to improve performance or trigger preemptive maintenance. Methods: Review of runtime plots of daily (6 MV) output data acquired using in house ion chamber based devices over three years and for fifteen linear accelerators of varying make and model were evaluated. Shifts in output due to known interventions with the machines were subtracted from the data to model an uncorrected scenario for each linear accelerator. Observable linear trends were also removed from the data prior to evaluation of periodic variations. Results: Runtime plots of output revealed sinusoidal, seasonal variations that were consistent across all units, irrespective of manufacturer, model or age of machine. The average amplitude of the variation was on the order of 1%. Peak and minimum variations were found to correspond to early April and September, respectively. Approximately 48% of output adjustments made over the period examined were potentially avoidable if baseline levels had corresponded to the mean output, rather than to points near a peak or valley. Linear trends were observed for three of the fifteen units, with annual increases in output ranging from 2–3%. Conclusion: Characterization of cyclical seasonal trends allows for better separation of potentially innate accelerator behaviour from other behaviours (e.g. linear trends) that may be better described as true out of control states (i.e. non-stochastic deviations from otherwise expected behavior) and could indicate service requirements. Results also pointed to an optimal setpoint for accelerators such that output of machines is maintained within set tolerances and interventions are required less frequently.

07 ISOTOPE AND RADIATION SOURCES↗

Quadratic Programming for Allocating Control Effort

A computer program calculates an optimal allocation of control effort in a system that includes redundant control actuators. The program implements an iterative (but otherwise single-stage) algorithm of the quadratic-programming type. In general, in the quadratic-programming problem, one seeks the values of a set of variables that minimize a quadratic cost function, subject to a set of linear equality and inequality constraints. In this program, the cost function combines control effort (typically quantified in terms of energy or fuel consumed) and control residuals (differences between commanded and sensed values of variables to be controlled). In comparison with prior control-allocation software, this program offers approximately equal accuracy but much greater computational efficiency. In addition, this program offers flexibility, robustness to actuation failures, and a capability for selective enforcement of control requirements. The computational efficiency of this program makes it suitable for such complex, real-time applications as controlling redundant aircraft actuators or redundant spacecraft thrusters. The program is written in the C language for execution in a UNIX operating system.

Singh, Gurkirpal↗