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.     

The maximum clique problem

In this paper we present a survey of results concerning algorithms, complexity, and applications of the maximum clique problem. We discuss enumerative and exact algorithms, heuristics, and a variety of other proposed methods. An up to date bibliography on the maximum clique and related problems is also provided.     

A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

A study of ACO capabilities for solving the maximum clique problem

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph. We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.     

Test case generators and computational results for the maximum clique problem

In the last years many algorithms have been proposed for solving the maximum clique problem. Most of these algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum cliques. In addition, we provide computational experience with two exact algorithms using the generated test problems.     

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 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 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.     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

A branch and bound algorithm for the robust shortest path problem with interval data

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs.A branch and bound algorithm for this problem is presented.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).     

A new algorithm for solving the general quadratic programming problem

For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs.     

An exact algorithm for the maximum stable set problem

We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to real-life problems show that the algorithm is competitive with the fastest algorithms known so far.This work has been supported by Agenzia Spaziale Italiana.     

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.     

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.     

Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.     

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.     

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.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.