Search NASA⌕ Search

SEARCH · Search NASA

Results for “branch and bound algorithm”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2015

Kodiak: An Implementation Framework for Branch and Bound Algorithms

Recursive branch and bound algorithms are often used to refine and isolate solutions to several classes of global optimization problems. A rigorous computation framework for the solution of systems of equations and inequalities involving nonlinear real arithmetic over hyper-rectangular variable and parameter domains is presented. It is derived from a generic branch and bound algorithm that has been formally verified, and utilizes self-validating enclosure methods, namely interval arithmetic and, for polynomials and rational functions, Bernstein expansion. Since bounds computed by these enclosure methods are sound, this approach may be used reliably in software verification tools. Advantage is taken of the partial derivatives of the constraint functions involved in the system, firstly to reduce the branching factor by the use of bisection heuristics and secondly to permit the computation of bifurcation sets for systems of ordinary differential equations. The associated software development, Kodiak, is presented, along with examples of three different branch and bound problem types it implements.

Smith, Andrew P.↗
NASA NTRS2003

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↗
NASA NTRS1984

A Simple Algorithm for the Metric Traveling Salesman Problem

An algorithm was designed for a wire list net sort problem. A branch and bound algorithm for the metric traveling salesman problem is presented for this. The algorithm is a best bound first recursive descent where the bound is based on the triangle inequality. The bounded subsets are defined by the relative order of the first K of the N cities (i.e., a K city subtour). When K equals N, the bound is the length of the tour. The algorithm is implemented as a one page subroutine written in the C programming language for the VAX 11/750. Average execution times for randomly selected planar points using the Euclidean metric are 0.01, 0.05, 0.42, and 3.13 seconds for ten, fifteen, twenty, and twenty-five cities, respectively. Maximum execution times for a hundred cases are less than eleven times the averages. The speed of the algorithms is due to an initial ordering algorithm that is a N squared operation. The algorithm also solves the related problem where the tour does not return to the starting city and the starting and/or ending cities may be specified. It is possible to extend the algorithm to solve a nonsymmetric problem satisfying the triangle inequality.

Grimm, M. J.↗
NASA NTRS1997

Algorithms for Multiple Fault Diagnosis With Unreliable Tests

In this paper, we consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for multiple fault diagnosis is NP-hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: (1) near optimal solutions for the MFD problem, and (2) upper bounds for an optimal branch-and-bound algorithm. The proposed method is illustrated using several examples. Computational results indicate that: (1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement), (2) the near optimal algorithm generates the most likely candidates with a very high accuracy, and (3) our algorithm can find the most likely candidates in systems with as many as 1000 faults.

Shakeri, Mojdeh↗
NASA NTRS1981

Theory and implementation of a fast algorithm linear equalizer

The theory and implementation of a multiplication-free linear mean-square error criterion equalizer for data transmission are considered. For many real-time signal processing situations, a large number of multiplications is objectionable. The linear estimation problem on a binary computer is considered where the estimation parameters are constrained to be powers of two and thus all multiplications are replaced by shifts. The optimal solution is obtained from an integer-programming-like problem except that the allowable discrete points are non-integers. The branch-and-bound algorithm is used to obtain the coefficients of the equalization TDL. Specific experimental performance results are given for an equalizer implemented with a 12 bit A/D device and a 8080 microprocessor.

Yan, T. Y.↗
NASA NTRS1981

An algorithm for minimum-cost set-point ordering in a cryogenic wind tunnel

An algorithm for minimum cost ordering of set points in a cryogenic wind tunnel is developed. The procedure generates a matrix of dynamic state transition costs, which is evaluated by means of a single-volume lumped model of the cryogenic wind tunnel and the use of some idealized minimum-costs, which is evaluated by means of a single-volume lumped model of the cryogenic wind tunnel and the use of some idealized minimum-cost state-transition control strategies. A branch and bound algorithm is employed to determine the least costly sequence of state transitions from the transition-cost matrix. Some numerical results based on data for the National Transonic Facility are presented which show a strong preference for state transitions that consume to coolant. Results also show that the choice of the terminal set point in an open odering can produce a wide variation in total cost.

Tripp, J. S.↗
NASA NTRS1986

A survey of the state of the art and focused research in range systems, task 2

Many communication, control, and information processing subsystems are modeled by linear systems incorporating tapped delay lines (TDL). Such optimized subsystems result in full precision multiplications in the TDL. In order to reduce complexity and cost in a microprocessor implementation, these multiplications can be replaced by single-shift instructions which are equivalent to powers of two multiplications. Since, in general, the obvious operation of rounding the infinite precision TDL coefficients to the nearest powers of two usually yield quite poor system performance, the optimum powers of two coefficient solution was considered. Detailed explanations on the use of branch-and-bound algorithms for finding the optimum powers of two solutions are given. Specific demonstration of this methodology to the design of a linear data equalizer and its implementation in assembly language on a 8080 microprocessor with a 12 bit A/D converter are reported. This simple microprocessor implementation with optimized TDL coefficients achieves a system performance comparable to the optimum linear equalization with full precision multiplications for an input data rate of 300 baud. The philosophy demonstrated in this implementation is dully applicable to many other microprocessor controlled information processing systems.

Yao, K.↗
NASA NTRS1991

Stacking-sequence optimization for buckling of laminated plates by integer programming

Integer-programming formulations for the design of symmetric and balanced laminated plates under biaxial compression are presented. Both maximization of buckling load for a given total thickness and the minimization of total thickness subject to a buckling constraint are formulated. The design variables that define the stacking sequence of the laminate are zero-one integers. It is shown that the formulation results in a linear optimization problem that can be solved on readily available software. This is in contrast to the continuous case, where the design variables are the thicknesses of layers with specified ply orientations, and the optimization problem is nonlinear. Constraints on the stacking sequence such as a limit on the number of contiguous plies of the same orientation and limits on in-plane stiffnesses are easily accommodated. Examples are presented for graphite-epoxy plates under uniaxial and biaxial compression using a commercial software package based on the branch-and-bound algorithm.

Haftka, Raphael T.↗
NASA NTRS1991

Stacking-sequence optimization for buckling of laminated plates by integer programming

Integer-programming formulations for the design of symmetric and balanced laminated plates under biaxial compression are presented. Both maximization of buckling load for given total thickness, and the minimization of total thickness subject to a buckling constraint are formulated. The design variables that define the stacking sequence of the laminate are zero-one integers. It is shown that the formulation results in a linear optimization problem that can be solved on readily aviable software. Constraints on the stacking sequence such as a limit on the number of contiguous plies of the same orientation and limits on in-plane stiffnesses are easily accommodated. Examples are presented for graphite-epoxy plates under uniaxial and biaxial compression using a commercial software package based on the branch-and-bound algorithm.

Haftka, Raphael T.↗
NASA NTRS1992

Stacking sequence optimization of simply supported laminates with stability and strain constraints

An integer programming formulation for the design of symmetric and balanced rectangular composite laminates with simply supported boundary conditions subject to buckling and strain constraints is presented. The design variables that define the stacking sequence of the laminate are ply-identity zero-one integers. The buckling constraint is linear in terms of the ply-identity design variables, but strains are nonlinear functions of these variables. A linear approximation is developed for the strain constraints so that the problem can be solved by sequential linearization using the branch and bound algorithm. Examples of graphite-epoxy plates under biaxial compression are presented. Optimum stacking sequences obtained using the linear approximation are compared with global optimum designs obtained using a genetic search procedure.

Nagendra, S.↗
NASA NTRS1992

Generating effective project scheduling heuristics by abstraction and reconstitution

A project scheduling problem consists of a finite set of jobs, each with fixed integer duration, requiring one or more resources such as personnel or equipment, and each subject to a set of precedence relations, which specify allowable job orderings, and a set of mutual exclusion relations, which specify jobs that cannot overlap. No job can be interrupted once started. The objective is to minimize project duration. This objective arises in nearly every large construction project--from software to hardware to buildings. Because such project scheduling problems are NP-hard, they are typically solved by branch-and-bound algorithms. In these algorithms, lower-bound duration estimates (admissible heuristics) are used to improve efficiency. One way to obtain an admissible heuristic is to remove (abstract) all resources and mutual exclusion constraints and then obtain the minimal project duration for the abstracted problem; this minimal duration is the admissible heuristic. Although such abstracted problems can be solved efficiently, they yield inaccurate admissible heuristics precisely because those constraints that are central to solving the original problem are abstracted. This paper describes a method to reconstitute the abstracted constraints back into the solution to the abstracted problem while maintaining efficiency, thereby generating better admissible heuristics. Our results suggest that reconstitution can make good admissible heuristics even better.

Janakiraman, Bhaskar↗
NASA NTRS1991

mu analysis with real parametric uncertainty

The authors give a broad overview, from a LFT (linear fractional transformation)/mu perspective, of some of the theoretical and practical issues associated with robustness in the presence of real parametric uncertainty, with a focus on computation. Recent results on the properties of mu in the mixed case are reviewed, including issues of NP completeness, continuity, computation of bounds, the equivalence of mu and its bounds, and some direct comparisons with Kharitonov-type analysis methods. In addition, some advances in the computational aspects of the problem, including a novel branch and bound algorithm, are briefly presented together with numerical results. The results suggest that while the mixed mu problem may have inherently combinatoric worst-case behavior, practical algorithms with modest computational requirements can be developed for problems of medium size (less than 100 parameters) that are of engineering interest.

Young, Peter M.↗
NASA NTRS1980

Theoretical study of network design methodologies for the aerial relay system

The aerial relay system network design problem is discussed. A generalized branch and bound based algorithm is developed which can consider a variety of optimization criteria, such as minimum passenger travel time and minimum liner and feeder operating costs. The algorithm, although efficient, is basically useful for small size networks, due to its nature of exponentially increasing computation time with the number of variables.

Rivera, J. M.↗
NASA NTRS1994

On k-ary n-cubes: Theory and applications

Many parallel processing networks can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and toruses. In this paper, combinatorial properties of k-ary n-cubes are explored. In particular, the problem of characterizing the subgraph of a given number of nodes with the maximum edge count is studied. These theoretical results are then used to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions.

Mao, Weizhen↗
NASA NTRS2019

A Mixed Integer Efficient Global Optimization Algorithm with Multiple Infill Strategy - Applied to a Wing Topology Optimization Problem

With the advancement in high performance computing and numerical optimization techniques,engineering design optimization problems are becoming more complex, larger scale,higher fidelity, and computationally more demanding, requiring longer run times than ever before. There exists methodologies and techniques that can address some of these challenges but very few can address all, and most are limited in the extent that these concerns can be addressed. With the goal of addressing such challenging engineering problems, we developed anew optimization framework, named AMIEGO, that combines concepts from surrogate-based optimization approaches, gradient-based numerical methods, Partial Least Squares, evolutionary algorithms, and Branch-and-Bound, providing newer capabilities that were not previouslyperceived. However, the original version of this framework, in the process of adaptive samplingto explore and exploit the design space, finds only a single sample point per iteration. The efforthere builds upon this previously developed optimization framework to include multiple infillsampling capability that combines the concept of generalized expected improvement function,unsupervised learning, and multi-objective evolutionary technique. To demonstrate, AMIEGOwith the multiple infill capability (called AMIEGO-MIMOS) solves a series of increasingly difficultengineering design optimization problems. The results reveal the performance of the newapproach is problem dependent. When applied to a ten-bar truss problem, the newly proposedmultiple infill strategy consistently leads to a better design solutions when compared to theexisting CPTV method (implemented with the context of the AMIEGO framework). On theother hand, when applied to a mixed-integer high fidelity wing topology optimization problem- MIMOS, despite showing a steeper convergence at the start, eventually leads to an inferiorsolution as compared to CPTV approach. These results also reveal that a small number ofstarting points, in general, are sufficient to lead to a good overall solution.

Mixed-integer optimization↗
NASA NTRS1991

An approximation based global optimization strategy for structural synthesis

A global optimization strategy for structural synthesis based on approximation concepts is presented. The methodology involves the solution of a sequence of highly accurate approximate problems using a global optimization algorithm. The global optimization algorithm implemented consists of a branch and bound strategy based on the interval evaluation of the objective function and constraint functions, combined with a local feasible directions algorithm. The approximate design optimization problems are constructed using first order approximations of selected intermediate response quantities in terms of intermediate design variables. Some numerical results for example problems are presented to illustrate the efficacy of the design procedure setforth.

Sepulveda, A. E.↗
NASA NTRS1997

Efficient algorithms for robust feature matching

One of the basic building blocks in any point-based registration scheme involves matching feature points that are extracted from the sensed image to their counterparts in the reference image. This leads to the fundamental problem of point matching: given two sets of points, find the affine transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between two point sets be robust to these effects. We measure distances using the generalized Hausdorff distance. Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem both theoretical and applied. We present two approaches to the point matching problem, in an attempt to reduce the computational complexity of the problem, while still providing guarantees on the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-bound approach due to Huttenlocher and Rucklidge. We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. With high probability this method succeeds in finding an approximately optimal match. We establish the efficiency of our approaches empirically.

Mount, David M.↗
NASA NTRS1990

An improved exploratory search technique for pure integer linear programming problems

The development is documented of a heuristic method for the solution of pure integer linear programming problems. The procedure draws its methodology from the ideas of Hooke and Jeeves type 1 and 2 exploratory searches, greedy procedures, and neighborhood searches. It uses an efficient rounding method to obtain its first feasible integer point from the optimal continuous solution obtained via the simplex method. Since this method is based entirely on simple addition or subtraction of one to each variable of a point in n-space and the subsequent comparison of candidate solutions to a given set of constraints, it facilitates significant complexity improvements over existing techniques. It also obtains the same optimal solution found by the branch-and-bound technique in 44 of 45 small to moderate size test problems. Two example problems are worked in detail to show the inner workings of the method. Furthermore, using an established weighted scheme for comparing computational effort involved in an algorithm, a comparison of this algorithm is made to the more established and rigorous branch-and-bound method. A computer implementation of the procedure, in PC compatible Pascal, is also presented and discussed.

Fogle, F. R.↗