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.

New enhancements to cut, fade, and dissolve detection processes in video segmentation

We present improved algorithms for cut, fade, and dissolve detection which are fundamental steps in digital video analysis. In particular, we propose a new adaptive threshold determination method that is shown to reduce artifacts created by noise and motion in scene cut detection. We also describe new two-step algorithms for fade and dissolve detection, and introduce a method for eliminating false positives from a list of detected candidate transitions. In our detailed study of these gradual shot transitions, our objective has been to accurately classify the type of transitions (fade-in, fade-out, and dissolve) and to precisely locate the boundary of the transitions. This distinguishes our work from other early work in scene change detection which tends to focus primarily on identifying the existence of a transition rather than its precise temporal extent. We evaluate our improved algorithms against two other commonly used shot detection techniques on a comprehensive data set, and demonstrate the improved performance due to our enhancements.

Security constrained optimal active power flow via network model and interior point method

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

Surface characterization of Ti-7.5Mo alloy modified by biomimetic method

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.

O problema de corte de placas defeituosas

O problema tratado neste trabalho consiste em cortar uma placa retangular em peças menores retangulares, de modo que a perda seja minimizada. A placa, entretanto, contém defeitos bem localizados. Propomos uma abordagem em grafo E/OU para representação das soluções possíveis e um método de enumeração implícita para determinar a solução ótima. Resultados computacionais demonstram a efetividade da abordagem.

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.

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.

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.

Two-level network design with intermediate facilities: An application to electrical distribution systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times. © 2010 Elsevier Ltd.

Application of an iterative method and an evolutionary algorithm in fuzzy optimization

This work develops two approaches based on the fuzzy set theory to solve a class of fuzzy mathematical optimization problems with uncertainties in the objective function and in the set of constraints. The first approach is an adaptation of an iterative method that obtains cut levels and later maximizes the membership function of fuzzy decision making using the bound search method. The second one is a metaheuristic approach that adapts a standard genetic algorithm to use fuzzy numbers. Both approaches use a decision criterion called satisfaction level that reaches the best solution in the uncertain environment. Selected examples from the literature are presented to compare and to validate the efficiency of the methods addressed, emphasizing the fuzzy optimization problem in some import-export companies in the south of Spain. © 2012 Brazilian Operations Research Society.

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.