The design of branch and bound algorithms for a class of nonlinear integer programs

This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems.     

Some branch and bound techniques for nonlinear optimization

The range of nonlinear optimization problems which can be solved by Linear Programming and the Branch and Bound algorithm is extended by introducing Chains of Linked Ordered Sets and by allowing automatic interpolation of new variables. However this approach involves solving a succession of linear subproblems, whose solutions in general violate the logical requirements of the nonlinear formulation and may lie far from any local or global optimum. The paper describes techniques which are designed to improve the performance of the Branch and Bound algorithm on problems containing chains, and which also yield benefits in integer programming.Each linear subproblem is tightened towards the corresponding nonlinear problem by removing variables which must logically be nonbasic in any feasible solution. This is achieved by a presolve procedure, and also by post-optimal Lagrangian relaxation which tightens the bound on the objective function by assessing the cheapest way to satisfy any violated chain constraints. Frequently fewer subsequent branches are required to find a feasible solution or to prove infeasibility.Formerly of Scicon Ltd.     

A two-stage parallel branch and bound algorithm for mixed integer programs

Mixed integer programming (MIP) models are extensively usedto aid strategic and tactical decision making in many businesssectors. Solving MIP models is a computationally intensive processand there is a need to develop solution approaches that enablelarger models to be solved within acceptable timeframes. Inthis paper, we describe the implementation of a two-stage parallelbranch and bound (PB & B) algorithm for MIP. In stage 1of the algorithm, a multiple heuristic search is implementedin which a number of alternative search trees are investigatedusing a forest search in the hope of finding a good solutionquickly. In stage 2, the search is reorganized so that the branchesof a chosen tree are investigated in parallel. A new heuristicis introduced, based on a best projection criterion, which evaluatesalternative B & B trees in order to choose one for investigationin stage 2 of the algorithm. The heuristic also serves as away of implementing a quality load balancing scheme for stage2 of the algorithm. The results of experimental investigationsare reported for a range of models taken from the MIPLIB libraryof benchmark problems.     

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

A decomposition-based solution method for stochastic mixed integer nonlinear programs

This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem.     

Design of planar articulated mechanisms using branch and bound

This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements elastic stability is of major concern. We derive conditions, modeled by nonlinear matrix inequalities, which guarantee that a stable equilibrium is found and that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities.To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve mechanism design problems of realistic size to global optimality.     

Transportation problem with nonlinear side constraints a branch and bound approach

In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems.     

Solving a class of low rank d.c. programs via a branch and bound approach: A computational experience

Various classes of d.c. programs have been studied in the recent literature due to their importance in applicative problems. In this paper we consider a branch and bound approach for solving a class of d.c. problems. Both stack policies and partitioning rules are analyzed, pointing out their performance effectiveness by means of the results of a computational experience.     

A computational comparison of some branch and bound methods for indefinite quadratic programs

The aim of this paper is to discuss different branch and bound methods for solving indefinite quadratic programs. In these methods the quadratic objective function is decomposed in a d.c. form and the relaxations are obtained by linearizing the concave part of the decomposition. In this light, various decomposition schemes have been considered and studied. The various branch and bound solution methods have been implemented and compared by means of a deep computational test.      

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods.     

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.     

DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

A class of practical interactive branch and bound algorithms for multicriteria integer programming

A practical interactive solution approach to multicriteria integer programming problems is developed. The problem is solved by a branch-and-bound method that employs the Zionts and Wallenius procedure [23] for solving the multicriteria linear programming problem. The development of algorithms for multicriteria decision problems itself is a multicriteria problem, which involves the simultaneous minimization of the number of questions asked of the decision maker and the solution time. Two branch-and-bound algorithms that follow different search strategies to meet different levels of these criteria have been developed. Further, two families of hybrid algorithms that incorporate a combination of the strategies of the two algorithms have also been developed. Strategies for the exploration of the decision-maker's preference structure are discussed. Computational experience with the algorithms is presented. The class of algorithms represents a collection of viable solution strategies applicable to a variety of decision-making styles.     

Strong relaxations for continuous nonlinear programs based on decision diagrams

Decision Diagrams (DDs) have arisen as a powerful tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge. In this paper, we introduce a novel framework that utilizes DDs to model continuous nonlinear programs. This framework, when combined with the array of techniques available for discrete problems, illuminates a new pathway to solving mixed integer nonlinear programs with the help of DDs.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.     

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.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.