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.

Transmission system expansion planning by a branch-and-bound algorithm

A branch and bound (B& B) algorithm using the DC model, to solve the power system transmission expansion planning by incorporating the electrical losses in network modelling problem is presented. This is a mixed integer nonlinear programming (MINLP) problem, and in this approach, the so-called fathoming tests in the B&B algorithm were redefined and a nonlinear programming (NLP) problem is solved in each node of the B& B tree, using an interior-point method. Pseudocosts were used to manage the development of the B&B tree and to decrease its size and the processing time. There is no guarantee of convergence towards global optimisation for the MINLP problem. However, preliminary tests show that the algorithm easily converges towards the best-known solutions or to the optimal solutions for all the tested systems neglecting the electrical losses. When the electrical losses are taken into account, the solution obtained using the Garver system is better than the best one known in the literature.

Planejamento de Fontes Reativas em Sistemas de Energia Elétrica utilizando a técnica de Decomposição de Benders e o algoritmo de Branch-and-Bound

This paper presents the Benders decomposition technique and Branch and Bound algorithm used in the reactive power planning in electric energy systems. The Benders decomposition separates the planning problem into two subproblems: an investment subproblem (master) and the operation subproblem (slave), which are solved alternately. The operation subproblem is solved using a successive linear programming (SLP) algorithm while the investment subproblem, which is an integer linear programming (ILP) problem with discrete variables, is resolved using a Branch and Bound algorithm especially developed to resolve this type of problem.

A branch-and-bound algorithm for the multi-stage transmission expansion planning

This work presents a branch-and-bound algorithm to solve the multi-stage transmission expansion planning problem. The well known transportation model is employed, nevertheless the algorithm can be extended to hybrid models or to more complex ones such as the DC model. Tests with a realistic power system were carried out in order to show the performance of the algorithm for the expansion plan executed for different time frames. © 2005 IEEE.

Branch and bound algorithm for transmission network expansion planning using DC model

This paper presents an algorithm to solve the network transmission system expansion planning problem using the DC model which is a mixed non-linear integer programming problem. The major feature of this work is the use of a Branch-and-Bound (B&B) algorithm to directly solve mixed non-linear integer problems. An efficient interior point method is used to solve the non-linear programming problem at each node of the B&B tree. Tests with several known systems are presented to illustrate the performance of the proposed method. ©2007 IEEE.

Origin of the circumflex branch of the coronary artery. A case report

The left coronary artery usually supplies the circumflex branch which provides several atrial and ventricular branches. During a routine dissection of the coronary artery, we could detect a circumflex branch originating from the right coronary artery. This resulted in an analysis of another 59 hearts without any similar results.

Assessment of branch outage contingencies using the continuation method

This paper provides a contribution to the contingency analysis of electric power systems under steady state conditions. An alternative methodology is presented for static contingency analyses that only use continuation methods and thus provides an accurate determination of the loading margin. Rather than starting from the base case operating point, the proposed continuation power flow obtains the post-contingency loading margins starting from the maximum loading and using a bus voltage magnitude as a parameter. The branch selected for the contingency evaluation is parameterised using a scaling factor, which allows its gradual removal and assures the continuation power flow convergence for the cases where the method would diverge for the complete transmission line or transformer removal. The applicability and effectiveness of the proposed methodology have been investigated on IEEE test systems (14, 57 and 118 buses) and compared with the continuation power flow, which obtains the post-contingency loading margin starting from the base case solution. In general, for most of the analysed contingencies, few iterations are necessary to determine the post-contingency maximum loading point. Thus, a significant reduction in the global number of iterations is achieved. Therefore, the proposed methodology can be used as an alternative technique to verify and even to obtain the list of critical contingencies supplied by the electric power systems security analysis function. © 2013 Elsevier Ltd. All rights reserved.