A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

A parallel branch and bound algorithm that solves the asymmetric traveling salesman problem to optimality is described. The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure. The algorithm is organized around a data flow framework for parallel branch and bound. The algorithm begins by converting the cost matrix to a sparser version in such a fashion as to retain the optimality of the final solution. Computational results are presented for three different classes of problem instances: (1) matrix elements drawn from a uniform distribution of integers for instances of size 250 to 10 000 cities, (2) instances of size 250 to 1000 cities that concentrate small elements in the upper left portion of the cost matrix, and (3) instances of size 300 to 3000 cities that are designed to confound neighborhood search heuristics.     

A finite branch-and-bound algorithm for two-stage stochastic integer programs

This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.The authors wish to acknowledge partial financial support from the IBM Research Division, ExxonMobil Upstream Research Company, and the National Science Foundation under awards DMI 95-02722, DMI 00-99726, and DMI 01-15166     

A simple,all primal branch and bound approach to pure and mixed integer binary programs

Many branch and bound procedures for integer programming employ linear programming to obtain bound information. Nodes in the tree structure are defined by explicitly changing bounds on certain variables and/or adding one or more constraints to the parent LP; thus, primal feasibility is destroyed. The design and analysis of the resulting tree structure requires that basis information be stored for each node and that feasibility restoring pivots be used to obtain the node bound. In turn, this may require the introduction of artificial variables and/or dual simplex pivots.This paper describes a simple procedure for branch and bound that does not destroy primal feasibility. Moreover, the information required to be stored to define the node problems is minimal.     

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.     

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.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale nonlinear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis*, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

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.     

Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5

This paper describes parallel, non-shared-memoryimplementation of the classical general mixed integer branch and boundalgorithm, with experiments on the CM-5 family of parallel processors. Themain issue in such an implementation is whether task scheduling and certaindata-storage functions should be handled by a single processor, orspread among multiple processors. The centralized approach riskscreating processing bottlenecks, while the more decentralizedimplementations differ more from the fundamental serial algorithm.Extensive computational tests on standard MIPLIB problems comparecentralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-basedglobal load balancing, along with a distributed control by tokentechnique. Further experiments compare centralized and distributedschemes for storing heuristic pseudo-cost branching data. The distributed storage method is based on continual asynchronous reductionalong a tree of redundant storage sites. On average, decentralized taskscheduling appears at least as effective as central control, butpseudo-cost storage should be kept as centralized as possible.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale non-linear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

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.     

Solving integer programs with a few important binary gub constraints

During a branch and bound search of an integer program, decisions have to be taken about which subproblem to solve next and which variable or special ordered set to branch on. Both these decisions are usually based on some sort of estimated change in the objective caused by different branching. When the next subproblem is chosen, the estimated change in the objective is often found by summing the change caused by changing all integer variables with non-integer values, as if they were independent. For special ordered sets the estimation is done for each set as a whole. The purpose of this paper is to report some results from trying to do a simultaneous estimation for all the variables in a binary gub constraint. By this, the analysed problems contain one or a few constraints saying that the sum ofn binary variables should be equal tom (<n).I am grateful to Scicon Ltd. for giving me access to the SCICONIC source code.     

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.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

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 branch and bound algorithm for the maximum clique problem

We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.

---

Zusammenfassung Wir stellen einen Branch and Bound Algorithmus für das Maximum Clique Problem in einem beliebigen Graphen vor. Das Hauptaugenmerk richtet sich dabei auf die Bestimmung oberer Schranken mit Hilfe von Färbungen von Graphen. Es wird eine Modifikation einer bekannten Färbungsmethode, genannt DSATUR, verwendet, mit der sich gleichzeitig obere und untere Schranken für die Cliquezahl erstellen lassen.

     

A finite concave minimization algorithm using branch and bound and neighbor generation

In this article we present a new finite algorithm for globally minimizing a concave function over a compact polyhedron. The algorithm combines a branch and bound search with a new process called neighbor generation. It is guaranteed to find an exact, extreme point optimal solution, does not require the objective function to be separable or even analytically defined, requires no nonlinear computations, and requires no determinations of convex envelopes or underestimating functions. Linear programs are solved in the branch and bound search which do not grow in size and differ from one another in only one column of data. Some preliminary computational experience is also presented.     

Solving mixed integer nonlinear programs by outer approximation

A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for thel ₁ norm is also given.This work is supported by SERC grant no. SERC GR/F 07972.Corresponding author.     

Parallel branch, cut, and price for large-scale discrete optimization

In discrete optimization, most exact solution approaches are based on branch and bound, which is conceptually easy to parallelize in its simplest forms. More sophisticated variants, such as the so-called branch, cut, and price algorithms, are more difficult to parallelize because of the need to share large amounts of knowledge discovered during the search process. In the first part of the paper, we survey the issues involved in parallelizing such algorithms. We then review the implementation of SYMPHONY and COIN/BCP, two existing frameworks for implementing parallel branch, cut, and price. These frameworks have limited scalability, but are effective on small numbers of processors. Finally, we briefly describe our next-generation framework, which improves scalability and further abstracts many of the notions inherent in parallel BCP, making it possible to implement and parallelize more general classes of algorithms. Mathematics Subject Classification (1991):65K05, 68N99, 68W10, 90-04, 90-08, 90C06, 90C09, 90C10, 90C11, 90C57     

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.