Branch and Bound algorithms in greenhouse climate control

The horticultural sector has become an increasingly important sector of food production, for which greenhouse climate control plays a vital role in improving its sustainability. One of the methods to control the greenhouse climate is Model Predictive Control, which can be optimized through a branch and bound algorithm. The application of the algorithm in literature is examined and analyzed through small examples, and later extended to greenhouse climate simulation. A comparison is made of various alternative objective functions available in literature. Subsequently, a modidified version of the B&B algorithm is presented, which reduces the number of node evaluations required for optimization. Finally, three alternative algorithms are developed and compared to consider the optimization problem from a discrete to a continuous control space.

Implementing and testing branch-and-bound algorithm for the quadratic 0-1 problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimention is small. For most of them the problem of finding an ε-approximate solution is already NP-hard. The branch-and-bound algorithms are the most used algorithms for solving exactly this sort of problems.

A computational study of a parallel Branch and Bound algorithm for the quadratic 0-1 programming problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimantion is small. For most of them the problem of finding an ε-approximate solution is already NP-hard.

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.

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.

B-LOG: A branch and bound methodology for the parallel execution of logic programs

We propose a computational methodology -"B-LOG"-, which offers the potential for an effective implementation of Logic Programming in a parallel computer. We also propose a weighting scheme to guide the search process through the graph and we apply the concepts of parallel "branch and bound" algorithms in order to perform a "best-first" search using an information theoretic bound. The concept of "session" is used to speed up the search process in a succession of similar queries. Within a session, we strongly modify the bounds in a local database, while bounds kept in a global database are weakly modified to provide a better initial condition for other sessions. We also propose an implementation scheme based on a database machine using "semantic paging", and the "B-LOG processor" based on a scoreboard driven controller.

A branch-and-bound algorithm for optimal AND-OR networks (the algorithm description)

Bibliography: p. 39.

Comparison of the implicit enumeration method and the branch-and-bound method for logical design

Bibliography: p. 91-94.

Pruning and branching methods for designing optimal networks by the branch-and-bound method

Includes bibliographical references.

A branch-and-bound algorithm for optimal NOR networks (the algorithm description)

Bibliography: p. 29.

Results of the synthesis of optimal networks of AND and OR gates for four-variable switching functions by a branch-and-bound computer program /

Bibliography: p. 39 (2d group)

An observation about circular shortest paths: Dealing with additional constraints using branch and bound

Circular shortest paths represent a powerful methodology for image segmentation. The circularity condition ensures that the contour found by the algorithm is closed, a natural requirement for regular objects. Several implementations have been proposed in the past that either promise closure with high probability or ensure closure strictly, but with a mild computational efficiency handicap. Circularity can be viewed as a priori information that helps recover the correct object contour. Our "observation" is that circularity is only one among many possible constraints that can be imposed on shortest paths to guide them to a desirable solution. In this contribution, we illustrate this opportunity under a volume constraint but the concept is generally applicable. We also describe several adornments to the circular shortest path algorithm that proved useful in applications. © 2011 IEEE.

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.

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.

Planejamento da expansão de sistemas de transmissão usando algoritmos tipo dual simplex especializados em uma estrutura branch and bound

Pós-graduação em Engenharia Elétrica - FEIS