A parallel formulation for the simulation of a generic branch predictor

A parallel formulation for the simulation of a branch prediction algorithm is presented. This parallel formulation identifies independent tasks in the algorithm which can be executed concurrently. The parallel implementation is based on the multithreading model and two parallel programming platforms: pthreads and Cilk++. Improvement in execution performance by up to 7 times is observed for a generic 2-bit predictor in a 12-core multiprocessor system.

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Branch and Bound Algorithm for Multiprocessor Scheduling

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

Produktion, skador och grenegenskaper hos 10-årig tall i ett kombinerat förbands- och avkommeförsök : Volume production, damages and branch properties in a 10-year old combined spacing and progeny trial of Scots pine

A Scots pine (Pinus sylvestris) progeny trial was established in 1990, in the southwestern part of Sweden. The offspring was from 30 plus trees. The trial is located on abandoned agricultural land and has a single tree block design with a variation in spacing. The trial has been damaged by voles. At a tree age of ten years, growth, damages and branch properties were estimated. An analysis of variance on height, diameter and stem volume shows significant difference between spacing and progenies as well as interactions between these factors. As indicated by a better annual height increment and fewer and thinner branches at each whorl the densest spacing has the highest potential to produce quality logs.There were also differences between progenies in growth and quality traits. Some progenies combined good growth and branch characters with low mortality, straight stems and few damages. Other progenies had superior volume production.

A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies; the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances. (C) 2004 Elsevier Ltd. All rights reserved.

Reactive power dispatch and planning using a non-linear branch-and-bound algorithm

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Branch formation in Pulvinularia suecica (Nostocales, Cyanoprokaryota) and considerations on the classification of dichotomously and pseudodichotomously branched genera

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

The hierarchical model of branch planning with random coefficients

We consider the management branch model where the random resources of the subsystem are given by the exponential distributions. The determinate equivalent is a block structure problem of quadratic programming. It is solved effectively by means of the decomposition method, which is based on iterative aggregation. The aggregation problem of the upper level is resolved analytically. This overcomes all difficulties concerning the large dimension of the main problem.

Continuation load flow using automatically determined branch megawatt losses as parameters

The conventional Newton's method is considered to be inadequate for the computation of the maximum loading point (MLP) of power systems since: (i) it encounters difficulties in the vicinity of the MLP: and (ii) the load flow Jacobian matrix becomes singular at the MLP. It is well known that continuation methods are powerful and useful tools that are able to trace the solution PV curve without experiencing such diffculties. However, continuation methods require a parameterisation so that a modified, well conditioned set of load flow equations is obtained. In particular, the Jacobian matrix associated with this modified set of equations should not be singular at the MLP. The authors propose that the actual power losses in transmission branches (lines and transformers) are used to parameterise the approach. Specific procedures for the automatic determination of the most appropriate parameter (branch) are proposed. Such procedures include the utilisation of fast voltage-stability indices. Simulation results are presented to show that the proposed method is able to trace the whole solution PV curve very efficiently.

Constructive heuristic algorithm in branch-and-bound structure applied to transmission network expansion planning

A constructive heuristic algorithm to solve the transmission system expansion planning problem is proposed with the aim of circumventing some critical problems of classical heuristic algorithms that employ relaxed mathematical models to calculate a sensitivity index that guides the circuit additions. The proposed heuristic algorithm is in a branch-and-bound algorithm structure, which can be used with any planning model, such as Transportation model, DC model, AC model or Hybrid models. Tests of the proposed algorithm are presented on real Brazilian systems.

Branch and bound algorithm for transmission system expansion planning using a transportation model

A method for optimal transmission network expansion planning is presented. The transmission network is modelled as a transportation network. The problem is solved using hierarchical Benders decomposition in which the problem is decomposed into master and slave subproblems. The master subproblem models the investment decisions and is solved using a branch-and-bound algorithm. The slave subproblem models the network operation and is solved using a specialised linear program. Several alternative implementations of the branch-and-bound algorithm have been rested. Special characteristics of the transmission expansion problem have been taken into consideration in these implementations. The methods have been tested on various test systems available in the literature.

Specialised branch-and-bound algorithm for transmission network expansion planning

An algorithm is presented that finds the optimal plan long-term transmission for till cases studied, including relatively large and complex networks. The knowledge of optimal plans is becoming more important in the emerging competitive environment, to which the correct economic signals have to be sent to all participants. The paper presents a new specialised branch-and-bound algorithm for transmission network expansion planning. Optimality is obtained at a cost, however: that is the use of a transportation model for representing the transmission network, in this model only the Kirchhoff current law is taken into account (the second law being relaxed). The expansion problem then becomes an integer linear program (ILP) which is solved by the proposed branch-and-bound method without any further approximations. To control combinatorial explosion the branch- and bound algorithm is specialised using specific knowledge about the problem for both the selection of candidate problems and the selection of the next variable to be used for branching. Special constraints are also used to reduce the gap between the optimal integer solution (ILP program) and the solution obtained by relaxing the integrality constraints (LP program). Tests have been performed with small, medium and large networks available in the literature.