An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

A Projection Method for the Integer Quadratic Knapsack Problem

In this paper we present a new branch and bound algorithm for solving a class of integer quadratic knapsack problems. A previously published algorithm solves the continuous variable subproblems in the branch and bound tree by performing a binary search over the breakpoints of a piecewise linear equation resulting from the Kuhn-Tucker conditions. Here, we first present modifications to a projection method for solving the continuous subproblems. Then we implement the modified projection method in a branch and bound framework and report computational results indicating that the new branch and bound algorithm is superior to the earlier method.     

A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm 1

Known duality statements are used to find tight bounds for the branch and bound process in solving Boolean quadratic optimization problems. To solve the corresponding continuous partial problem, a NEWTON-like procedure is indicated. Superlinear convergence, however, is only obtained in partial cases.     

B&B Frameworks for the Capacity Expansion of High Speed Telecommunication Networks Under Uncertainty

The purpose of this paper is to investigate branch and bound strategies and the comparison of branch and cut with pure branch and bound approaches on high speed telecommunication network design under uncertainty. We model the problem as a two-stage stochastic program with discrete first-stage (investment) variables. Two formulations of the problem are used. The first one with general integer investment variables and the second one, a variant of the first model, with 0-1 investment variables. We present computational results for three solution approaches: the integer L-shaped (Benders) decomposition, a branch and bound framework and a disjunctive cutting plane method. This work was supported by France Telecom.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.     

An extended branch and bound algorithm for linear bilevel programming

For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn–Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit.     

A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions

We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations.     

A new branch and bound algorithm for cell formation problem

Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems.     

A Branch and Contract Algorithm for Problems with Concave Univariate, Bilinear and Linear Fractional Terms

A new deterministic branch and bound algorithm is presented in this paper for the global optimization of continuous problems that involve concave univariate, bilinear and linear fractional terms. The proposed algorithm, the branch and contract algorithm, relies on the use of a bounds-contraction subproblem that aims at reducing the size of the search region by eliminating portions of the domain in which the objective function takes only values above a known upper bound. The solution of contraction subproblems at selected branch and bound nodes is performed within a finite contraction operation that helps reducing the total number of nodes in the branch and bound solution tree. The use of the proposed algorithm is illustrated with several numerical examples.     

Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds

Speed and memory requirements of branch and bound algorithms depend on the selection strategy of which candidate node to process next. The goal of this paper is to experimentally investigate this influence to the performance of sequential and parallel branch and bound algorithms. The experiments have been performed solving a number of multidimensional test problems for global optimization. Branch and bound algorithm using simplicial partitions and combination of Lipschitz bounds has been investigated. Similar results may be expected for other branch and bound algorithms.     

Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region

A global optimization algorithm is presented for maximizing the sum of difference of convex functions ratios problem over nonconvex feasible region. This algorithm is based on branch and bound framework. To obtain a difference of convex programming, the considered problem is first reformulated by introducing new variables as few as possible. By using subgradient and convex envelope, the fundamental problem of estimating lower bound in the branch and bound algorithm is transformed into a relaxed linear programming problem which can be solved efficiently. Furthermore, the size of the relaxed linear programming problem does not change during the algorithm search. Lastly, the convergence of the algorithm is analyzed and the numerical results are reported.     

A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routeing Problems

This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.     

A Reduced Space Branch and Bound Algorithm for Global optimization

A general class of branch and bound algorithms forsolving a wide class of nonlinear programs with branching only in asubset of the problem variables is presented. By reducing the dimension of thesearch space, this technique may dramatically reduce the number ofiterations and time required for convergence to tolerancewhile retaining proven exact convergence in the infinite limit. Thispresentation includes specifications of the class of nonlinearprograms, a statement of a class of branch and bound algorithms, aconvergence proof, and motivating examples with results.     

A graph colouring model for assigning a heterogeneous workforce to a given schedule

We analyze a heterogeneous workforce assignment problem in which the minimum number of workers required to carry out a machine load plan is calculated. The problem is formulated as a restricted vertex colouring problem and a branch and bound algorithm is presented. The special characteristics of the graph to be coloured allow an efficient implementation of the branch and bound. Computational results show that the algorithm can solve problems of 50 activities, 5, 10 and 15 machines and between 2 to 15 different types of workers in just a few seconds.     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

A branch and bound algorithm for determining locations of long-term care facilities

This paper focuses on the problem of determining locations for long-term care facilities with the objective of balancing the numbers of patients assigned to the facilities. We present a branch and bound algorithm by developing dominance properties, a lower bounding scheme and a heuristic algorithm for obtaining an upper bound for the problem. For evaluation of the suggested branch and bound algorithm, computational experiments are performed on a number of test problems. Results of the experiments show that the suggested algorithm gives optimal solutions of problems of practical sizes in a reasonable amount of computation time.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

A branch and bound algorithm for the acyclic subgraph problem

A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.     

A branch and bound algorithm for class based storage location assignment

Class-based storage implementation decisions have significant impact on the required storage space and the material handling cost in a warehouse. In this paper, a nonlinear integer programming model is proposed to capture the above. Effects of storage area reduction on order picking and storage space cost are incorporated. A branch and bound algorithm is developed to solve the model. Computational experience with randomly generated data sets and an industrial case shows that branch and bound algorithm is computationally more efficient than a baseline dynamic programming algorithm. It is further observed that the class based policy results in lower total cost of order picking and storage space than the dedicated policy.