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 253 records · Page 14

Minimal Energy Routing of a Leader and a Wingmate with Periodic Connectivity

We consider a route planning problem in which two unmanned vehicles are required to complete a set of tasks present at distinct locations, referred to as targets, with minimum energy consumption. The mission environment is hazardous, and to ensure a safe operation, the UVs are required to communicate with each other at every target they visit. The problem objective is to determine the allocation of the tasks to the UVs and plan tours for the UVs to visit the targets such that the weighted sum of the distances traveled by the UVs and the distances traveled by the communicating signals between them is minimized. We formulate this problem as an Integer program and show that naively solving the problem using commercially available off-the-shelf solvers is insufficient in determining scalable solutions efficiently. To address this computational challenge, we develop an approximation and a heuristic algorithm, and employ them to compute high-quality solutions to a special case of the problem where equal weights are assigned to the distances traveled by the vehicles and the communicating signals. For this special case, we show that the approximation algorithm has a fixed approximation ratio of 3.75. We also develop lower bounds to the optimal cost of the problem to evaluate the performance of these algorithms on large-scale instances. We demonstrate the performance of these algorithms on 500 randomly generated instances with the number of targets ranging from 6 to 100, and show that the algorithms provide high-quality solutions to the problem swiftly; the average computation time of the algorithmic solutions is within a fraction of a second for instances with at most 100 targets. Finally, we show that the approximation ratio has a variable ratio for the weighted case of the problem. Specifically, if ρ denotes the ratio of the weights assigned to the distances representing the communication and travel costs, the algorithm has an a posteriori ratio of $3 + \frac{3ρ}{4}$ when ρ ≥ 1, and $\frac{3}{ρ}$ + $\frac{3}{4}$ when ρ ≤ 1.

42 ENGINEERING↗

Astronauts' menu problem.

Consideration of the problems involved in choosing appropriate menus for astronauts carrying out SKYLAB missions lasting up to eight weeks. The problem of planning balanced menus on the basis of prepackaged food items within limitations on the intake of calories, protein, and certain elements is noted, as well as a number of other restrictions of both physical and arbitrary nature. The tailoring of a set of menus for each astronaut on the basis of subjective rankings of each food by the astronaut in terms of a 'measure of pleasure' is described, and a computer solution to this problem by means of a mixed integer programming code is presented.

Lesso, W. G.↗

Round-off errors in cutting plane algorithms based on the revised simplex procedure

This report statistically analyzes computational round-off errors associated with the cutting plane approach to solving linear integer programming problems. Cutting plane methods require that the inverse of a sequence of matrices be computed. The problem basically reduces to one of minimizing round-off errors in the sequence of inverses. Two procedures for minimizing this problem are presented, and their influence on error accumulation is statistically analyzed. One procedure employs a very small tolerance factor to round computed values to zero. The other procedure is a numerical analysis technique for reinverting or improving the approximate inverse of a matrix. The results indicated that round-off accumulation can be effectively minimized by employing a tolerance factor which reflects the number of significant digits carried for each calculation and by applying the reinversion procedure once to each computed inverse. If 18 significant digits plus an exponent are carried for each variable during computations, then a tolerance value of 0.1 x 10 to the minus 12th power is reasonable.

Moore, J. E.↗

International Symposium on Remote Sensing of Environment, 10th, University of Michigan, Ann Arbor, Mich., October 6-10, 1975, Proceedings. Volumes 1 & 2

Topics treated include the application of a Fourier transform spectrometer to infrared remote sensing, the performance optimization of a satellite-borne thematic mapper, a data handling system to be integrated with a digital airborne multispectral scanner, infrared thermography for micro- and mesometeorological measurements, satellite interrogated data collection platforms for river and flood forecasting and the automatic measurement of sea surface temperature from a GOES satellite. Solar and atmospheric effects on satellite imagery derived from aircraft reflectance measurements, methods for determining haze levels from multispectral scanner data, restoration of Landsat images by discrete two-dimensional deconvolution and the automatic classification of aircraft and satellite multispectral images using mixed integer programming are also discussed. Individual items are announced in this issue.

Source record↗

Recent research in network problems with applications

The capabilities of network codes and their extensions are surveyed in regard to specially structured integer programming problems which are solved by using the solutions of a series of ordinary network problems.

Thompson, G. L.↗

The role of service areas in the optimization of FSS orbital and frequency assignments

A relationship is derived, on a single-entry interference basis, for the minimum allowable spacing between two satellites as a function of electrical parameters and service-area geometries. For circular beams, universal curves relate the topocentric satellite spacing angle to the service-area separation angle measured at the satellite. The corresponding geocentric spacing depends only weakly on the mean longitude of the two satellites, and this is true also for alliptical antenna beams. As a consequence, if frequency channels are preassigned, the orbital assignment synthesis of a satellite system can be formulated as a mixed-integer programming (MIP) problem or approximated by a linear programming (LP) problem, with the interference protection requirements enforced by constraints while some linear function is optimized. Possible objective-function choices are discussed and explicit formulations are presented for the choice of the sum of the absolute deviations of the orbital locations from some prescribed ideal location set. A test problem is posed consisting of six service areas, each served by one satellite, all using elliptical antenna beams and the same frequency channels. Numerical results are given for the three ideal location prescriptions for both the MIP and LP formulations. The resulting scenarios also satisfy reasonable aggregate interference protection requirements.

Levis, C. A.↗

Engineering calculations for communications satellite systems planning

Observed solution times were analyzed for the extended gradient and cyclic coordinate search procedures. The times used in the analysis come from computer runs made during a previously-reported experiment conducted to assess the quality of the solutions to a BSS synthesis problem found by the two search methods. The results of a second experiment with a Fixed Satellite Service (FSS) test problem are also presented. Computational results are summarized for mixed integer programming approaches for solving FSS synthesis problems. A promising heuristic algorithm is described. A synthesis model is discussed for orbital arc allotment optimization. Research plans for the near future are also presented.

Reilly, C. H.↗

On orbital allotments for geostationary satellites

The following satellite synthesis problem is addressed: communication satellites are to be allotted positions on the geostationary arc so that interference does not exceed a given acceptable level by enforcing conservative pairwise satellite separation. A desired location is specified for each satellite, and the objective is to minimize the sum of the deviations between the satellites' prescribed and desired locations. Two mixed integer programming models for the satellite synthesis problem are presented. Four solution strategies, branch-and-bound, Benders' decomposition, linear programming with restricted basis entry, and a switching heuristic, are used to find solutions to example synthesis problems. Computational results indicate the switching algorithm yields solutions of good quality in reasonable execution times when compared to the other solution methods. It is demonstrated that the switching algorithm can be applied to synthesis problems with the objective of minimizing the largest deviation between a prescribed location and the corresponding desired location. Furthermore, it is shown that the switching heuristic can use no conservative, location-dependent satellite separations in order to satisfy interference criteria.

Gonsalvez, David J. A.↗

Engineering calculations for communications satellite systems planning

A procedure is described that was used to calculate minimum required satellite separations based on total link carrier to interference requirements. Also summarized are recent results with a switching algorithm for satellite synthesis problems. Analytic solution value bounds for two of the satellite synthesis models studied are described. Preliminary results from an empirical study of alternate mixed integer programming models for satellite synthesis are presented. Research plans for the near future are discussed.

Reilly, Charles H.↗

A satellite system synthesis model for orbital arc allotment optimization

A mixed integer programming formulation of a satellite system synthesis problem if presented, which is referred to as the arc allotment problem (AAP). Each satellite administration is to be allotted a weighted-length segment of the geostationary orbital arc within which its satellites may be positioned at any longitudes. The objective function maximizes the length of the unweighted arc segment allotted to every administration, subject to single-entry co-channel interference restrictions and constraints imposed by the visible arc for each administration. Useful relationships between special cases of AAP and another satellite synthesis problem are established. Solutions to two example problems are presented.

Reilly, Charles H.↗

A k-permutation algorithm for Fixed Satellite Service orbital allotments

A satellite system synthesis problem, the satellite location problem (SLP), is addressed in this paper. In SLP, orbital locations (longitudes) are allotted to geostationary satellites in the Fixed Satellite Service. A linear mixed-integer programming model is presented that views SLP as a combination of two problems: (1) the problem of ordering the satellites and (2) the problem of locating the satellites given some ordering. A special-purpose heuristic procedure, a k-permutation algorithm, that has been developed to find solutions to SLPs formulated in the manner suggested is described. Solutions to small example problems are presented and analyzed.

Reilly, Charles H.↗

A satellite system synthesis model for orbital arc allotment optimization

A mixed-integer programming formulation is presented of a satellite system synthesis problem, or geostationary-orbital-planning synthesis problem, which is refered to as the arc allotment problem (AAP). Each satellite administration is to be allotted a weighted-length segment of the geostationary orbital arc within which its satellites may be positioned at any longitude. The objective function maximizes the length of the unweighted arc segment allotted to every administration, subject to single-entry cochannel interference restrictions and constraints imposed by the visible arc for each administration. Useful relationships between special cases of AAP and another satellite synthesis problem are established. Solutions to two example problems are presented.

Reilly, Charles H.↗

Engineering calculations for solving the orbital allotment problem

Four approaches for calculating downlink interferences for shaped-beam antennas are described. An investigation of alternative mixed-integer programming models for satellite synthesis is summarized. Plans for coordinating the various programs developed under this grant are outlined. Two procedures for ordering satellites to initialize the k-permutation algorithm are proposed. Results are presented for the k-permutation algorithms. Feasible solutions are found for 5 of the 6 problems considered. Finally, it is demonstrated that the k-permutation algorithm can be used to solve arc allotment problems.

Reilly, C.↗

Finding fixed satellite service orbital allotments with a k-permutation algorithm

A satellite system synthesis problem, the satellite location problem (SLP), is addressed. In SLP, orbital locations (longitudes) are allotted to geostationary satellites in the fixed satellite service. A linear mixed-integer programming model is presented that views SLP as a combination of two problems: the problem of ordering the satellites and the problem of locating the satellites given some ordering. A special-purpose heuristic procedure, a k-permutation algorithm, has been developed to find solutions to SLPs. Solutions to small sample problems are presented and analyzed on the basis of calculated interferences.

Reilly, Charles H.↗

Towards a theory of automated elliptic mesh generation

The theory of elliptic mesh generation is reviewed and the fundamental problem of constructing computational space is discussed. It is argued that the construction of computational space is an NP-Complete problem and therefore requires a nonstandard approach for its solution. This leads to the development of graph-theoretic, combinatorial optimization and integer programming algorithms. Methods for the construction of two dimensional computational space are presented.

Cordova, J. Q.↗

Analysis and Modeling of Ground Operations at Hub Airports

Building simple and accurate models of hub airports can considerably help one understand airport dynamics, and may provide quantitative estimates of operational airport improvements. In this paper, three models are proposed to capture the dynamics of busy hub airport operations. Two simple queuing models are introduced to capture the taxi-out and taxi-in processes. An integer programming model aimed at representing airline decision-making attempts to capture the dynamics of the aircraft turnaround process. These models can be applied for predictive purposes. They may also be used to evaluate control strategies for improving overall airport efficiency.

Atkins, Stephen↗

Runway Operations Planning: A Two-Stage Heuristic Algorithm

The airport runway is a scarce resource that must be shared by different runway operations (arrivals, departures and runway crossings). Given the possible sequences of runway events, careful Runway Operations Planning (ROP) is required if runway utilization is to be maximized. From the perspective of departures, ROP solutions are aircraft departure schedules developed by optimally allocating runway time for departures given the time required for arrivals and crossings. In addition to the obvious objective of maximizing throughput, other objectives, such as guaranteeing fairness and minimizing environmental impact, can also be incorporated into the ROP solution subject to constraints introduced by Air Traffic Control (ATC) procedures. This paper introduces a two stage heuristic algorithm for solving the Runway Operations Planning (ROP) problem. In the first stage, sequences of departure class slots and runway crossings slots are generated and ranked based on departure runway throughput under stochastic conditions. In the second stage, the departure class slots are populated with specific flights from the pool of available aircraft, by solving an integer program with a Branch & Bound algorithm implementation. Preliminary results from this implementation of the two-stage algorithm on real-world traffic data are presented.

Anagnostakis, Ioannis↗