Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “branch and bound”

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

Parallel Interior Point Solver - Simple Branch & Bound

The purpose of this software package is to solve large-scale block-angular mixed-integer (linear) programs specified in SMPS format; the major application of this software package is to solving large-scale stochastic mixed-integer programs, which are block-angular.

Oxberry, Geoffrey↗

Parallel Interior Point Solver - Simple Branch & Bound

The purpose of this software package is to solve large-scale block-angular mixed-integer (linear) programs specified in SMPS format; the major application of this software package is to solving large-scale stochastic mixed-integer programs, which are block-angular.

Oxberry, Geoffrey↗

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.↗

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↗

Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem

We propose a quantum branch-and-bound algorithm based on the general scheme of the branch-and-bound method and the quantum nested searching algorithm and examine its computational efficiency. We also compare this algorithm with a similar classical algorithm on the example of the travelling salesman problem. We show that in the vast majority of problems, the classical algorithm is quicker than the quantum algorithm due to greater adaptability. However, the operation time of the quantum algorithm is constant for all problem, whereas the classical algorithm runs very slowly for certain problems. In the worst case, the quantum branch-and-bound algorithm is proved to be several times more efficient than the classical algorithm.

97 MATHEMATICS AND COMPUTING↗

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. Additionally, to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.

97 MATHEMATICS AND COMPUTING↗

Optimization Method to Branch and Bound Large SBO State Spaces Under Dynamic Probabilistic Risk Assessment via use of LENDIT Scales and S2R2 Sets

Traditional Probabilistic Risk Assessment (PRA) methods have been developed and are quite effective in evaluating risk associated with complex systems, but lack the capability to evaluate complex dynamic systems. These time and energy scales associated with the transient may vary as a function of transition time to a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems, while complete, results in issues associated with combinatorial explosion. In order to address the combinatorial complexity arising from the number of possible state configurations and discretization of transition times, a characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets – ‘state, system, resource and response’ (S2R2) – describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to ‘branch and bound’ the state space investigated by DPRA. In this paper we introduce the concept of LENDIT scales and S2R2 sets applied to a branch-and-bound algorithm and apply the methods to a station black out transient (SBO).

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

A Branch and Bound Approach for Truss Topology Design Problems with Valid Inequalities

One of the classical problems in the structural optimization field is the Truss Topology Design Problem (TTDP) which deals with the selection of optimal configuration for structural systems for applications in mechanical, civil, aerospace engineering, among others. In this paper we consider a TTDP where the goal is to find the stiffest truss, under a given load and with a bound on the total volume. The design variables are the cross-section areas of the truss bars that must be chosen from a given finite set. This results in a large-scale non-convex problem with discrete variables. This problem can be formulated as a Semidefinite Programming Problem (SDP problem) with binary variables. We propose a branch and bound algorithm to solve this problem. In this paper it is considered a binary formulation of the problem, to take advantage of its structure, which admits a Knapsack problem as subproblem. Thus, trying to improve the performance of the Branch and Bound, at each step, some valid inequalities for the Knapsack problem are included.

42 ENGINEERING↗

PIPS-SBB: A Parallel Distributed-Memory Branch-and-Bound Algorithm for Stochastic Mixed-Integer Programs

Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed- integer programs, problem instances can exceed available memory on a single workstation. In order to overcome this limitation, we present PIPS-SBB: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels of the optimization process. We also show promising results on the SIPLIB benchmark by combining methods known for accelerating Branch and Bound (B&B) methods with new ideas that leverage the structure of SMIPs. Finally, we expect the performance of PIPS-SBB to improve further as more functionality is added in the future.

97 MATHEMATICS AND COMPUTING↗

Improving the efficiency of branch-and-bound complete-search NMR assignment using the symmetry of molecules and spectra

Nuclear magnetic resonance (NMR) assignment of small molecules is presented as a typical example of a combinatorial optimization problem in chemical physics. Three strategies that help improve the efficiency of solution search by the branch and bound method are presented: 1. reduction of the size of the solution space by resort to a condensed structure formula, wherein symmetric nuclei are grouped together; 2. partitioning of the solution space based on symmetry, that becomes the basis for an efficient branching procedure; and 3. a criterion of selection of input restrictions that leads to increased gaps between branches and thus faster pruning of non-viable solutions. Although the examples chosen to illustrate this work focus on small-molecule NMR assignment, the results are generic and might help solving other combinatorial optimization problems.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Bifurcation Analysis Using Rigorous Branch and Bound Methods

For the study of nonlinear dynamic systems, it is important to locate the equilibria and bifurcations occurring within a specified computational domain. This paper proposes a new approach for solving these problems and compares it to the numerical continuation method. The new approach is based upon branch and bound and utilizes rigorous enclosure techniques to yield outer bounding sets of both the equilibrium and local bifurcation manifolds. These sets, which comprise the union of hyper-rectangles, can be made to be as tight as desired. Sufficient conditions for the existence of equilibrium and bifurcation points taking the form of algebraic inequality constraints in the state-parameter space are used to calculate their enclosures directly. The enclosures for the bifurcation sets can be computed independently of the equilibrium manifold, and are guaranteed to contain all solutions within the computational domain. A further advantage of this method is the ability to compute a near-maximally sized hyper-rectangle of high dimension centered at a fixed parameter-state point whose elements are guaranteed to exclude all bifurcation points. This hyper-rectangle, which requires a global description of the bifurcation manifold within the computational domain, cannot be obtained otherwise. A test case, based on the dynamics of a UAV subject to uncertain center of gravity location, is used to illustrate the efficacy of the method by comparing it with numerical continuation and to evaluate its computational complexity.

Smith, Andrew P.↗

Performance analysis of parallel branch and bound search with the hypercube architecture

With the availability of commercial parallel computers, researchers are examining new classes of problems which might benefit from parallel computing. This paper presents results of an investigation of the class of search intensive problems. The specific problem discussed is the Least-Cost Branch and Bound search method of deadline job scheduling. The object-oriented design methodology was used to map the problem into a parallel solution. While the initial design was good for a prototype, the best performance resulted from fine-tuning the algorithm for a specific computer. The experiments analyze the computation time, the speed up over a VAX 11/785, and the load balance of the problem when using loosely coupled multiprocessor system based on the hypercube architecture.

Mraz, Richard T.↗

Optimal material selection using branch and bound techniques

A methodology for structural synthesis is presented in which the optimal material selection for the structural members is treated in terms of (0,1) variables. Structural member sizes and material selection variables are treated simultaneously as design variables. Optimization is carried out by generating and solving a sequence of explicit approximate problems using a branch and bound strategy. Intermediate design variables and intermediate response quantities are used to enhance the quality of the approximate design problems. Numerical results for example problems are presented to illustrate the efficiency of the design procedure set forth.

Sepulveda, A. E.↗

Branch-and-Bound algorithm applied to uncertainty quantification of a Boiling Water Reactor Station Blackout

Evaluation of the impacts of uncertainty and sensitivity in modeling presents a significant set of challenges in particular to high fidelity modeling. Computational costs and validation of models creates a need for cost effective decision making with regards to experiment design. Experiments designed to validate computation models can be used to reduce uncertainty in the physical model. In some cases, large uncertainty in a particular aspect of the model may or may not have a large impact on the final results. For example, modeling of a relief valve may result in large uncertainty, however, the actual effects on final peak clad temperature in a reactor transient may be small and the large uncertainty with respect to valve modeling may be considered acceptable. Additionally, the ability to determine the adequacy of a model and the validation supporting it should be considered within a risk informed framework. Low fidelity modeling with large uncertainty may be considered adequate if the uncertainty is considered acceptable with respect to risk. In other words, models that are used to evaluate the probability of failure should be evaluated more rigorously with the intent of increasing safety margin. Probabilistic risk assessment (PRA) techniques have traditionally been used to identify accident conditions and transients. Traditional classical event tree methods utilize analysts’ knowledge and experience to identify the important timing of events in coordination with thermal-hydraulic modeling. These methods lack the capability to evaluate complex dynamic systems. In these systems, time and energy scales associated with transient events may vary as a function of transition times and energies to arrive at a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems. Unfortunately DPRA methods introduce issues associated with combinatorial explosion of states. This study presents a methodology to address combinatorial explosion using a Branch-and-Bound algorithm applied to Dynamic Event Trees (DET), which utilize LENDIT (L – Length, E – Energy, N – Number, D – Distribution, I – Information, and T – Time) as well as a set theory to describe system, state, resource, and response (S2R2) sets to create bounding functions for the DET. The optimization of the DET in identifying high probability failure branches is extended to create a Phenomenological Identification and Ranking Table (PIRT) methodology to evaluate modeling parameters important to safety of those failure branches that have a high probability of failure. The PIRT can then be used as a tool to identify and evaluate the need for experimental validation of models that have the potential to reduce risk. Finally, in order to demonstrate this methodology, a Boiling Water Reactor (BWR) Station Blackout (SBO) case study is presented.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗