A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem

We present a new highly parallel algorithm for fast determination of near-optimal solutions to the NP-hard problem of identifying a maximum distance-2 matching in arbitrary graphs. This problem, known as D2EMIS, has important applications such as determining the maximum capacity of the media access (MAC) layer in wireless ad-hoc networks [1]. It can also be seen as a maximum 2-packing problem [2] on the edge-to-vertex dual graph of the original graph. Our algorithm extends the GRASP [3] philosophy in that partial solutions are constructed by adding in a greedy adaptive manner the “best” nodes that can be found; however, when there are multiple alternatives that can be selected in an iteration, the algorithm branches into as many paths as there are (greedy) alternatives. The algorithm, using appropriate bounds to prune partial solutions that cannot be optimal, produces very fast near-optimal solutions that compare very well against other distributed algorithms and random greedy heuristics proposed before or variants thereof, or exact methods (Integer Programming or Maximum Satisfiability state-of-the-art solvers).     

An exact bit-parallel algorithm for the maximum clique problem

This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.     

The general maximum matching algorithm of micali and vazirani

We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n ^1/2 m) time.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570 and by the Eastman Kodak Company.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

The maximum weight hierarchy matching problem

We study the problem of fusing several reports about a group of objects into a single summary report, which best represents the received reports. A report is a list of labels associated with a group of objects, as reported by some identification device. Reports do not associate which object in the group has been given a specific label, the labels used in each report may be given in various levels of specificity and the information in the reports may be erroneous. Each label used in a report is accompanied by a weight, which provides a confidence measure for the label. The maximum weight hierarchy matching problem seeks a consistent interpretation of the received reports by matching the labels of each object across the reports, such that the total weight of elements used in the matching is maximized. In this paper we prove that this problem is NP-hard and develop an 0.632OPT approximation algorithm, where OPT is the optimal solution. The algorithm shows robust performance in Monte-Carlo simulations.     

A new exact maximum clique algorithm for large and massive sparse graphs

This paper describes a new very efficient branch-and-bound exact maximum clique algorithm BBMCSP, designed for large and massive sparse graphs which appear frequently in real life problems from different fields.State-of-the-art exact maximum clique algorithms encode the adjacency matrix in full but when dealing with sparse graphs some form of compression is required. The new algorithm is based on a leading bit-parallel non-sparse solver but employs a novel sparse encoding for the adjacency matrix. Moreover, it also improves on recent optimizations proposed in literature for the sparse case such as core-based bounds.Reported results show that it is several orders of magnitude better than state-of-the-art. Moreover, a number of real networks with many millions of nodes are solved in a few seconds.     

An efficient procedure for finding best compromise solutions to the multi-objective assignment problem

In this paper, we consider the problem of determining a best compromise solution for the multi-objective assignment problem. Such a solution minimizes a scalarizing function, such as the weighted Tchebychev norm or reference point achievement functions. To solve this problem, we resort to a ranking (or k-best) algorithm which enumerates feasible solutions according to an appropriate weighted sum until a condition, ensuring that an optimal solution has been found, is met. The ranking algorithm is based on a branch and bound scheme. We study how to implement efficiently this procedure by considering different algorithmic variants within the procedure: choice of the weighted sum, branching and bounding schemes. We present an experimental analysis that enables us to point out the best variants, and we provide experimental results showing the remarkable efficiency of the procedure, even for large size instances.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

Generating subproblems in branch and bound algorithms for parallel machines scheduling problem

A branch and bound algorithm (B&B) has been widely used in various discrete and combinatorial optimization fields. To obtain optimal solutions as soon as possible for scheduling problems, three tools, which are branching, bounding and dominance rules, have been developed in the B&B algorithm. One of these tools, a branching is a method for generating subproblems and directly determines size of solution to be searched in the B&B algorithm. Therefore, it is very important to devise effective branching scheme for the problem.In this note, a survey of branching schemes is performed for parallel machines scheduling (PMS) problems with n independent jobs and m machines and new branching schemes that can be used for identical and unrelated PMS problems, respectively, are suggested. The suggested branching methods show that numbers of generated subproblems are much smaller than that of other methods developed earlier and therefore, it is expected that they help to reduce a lot of CPU time required to obtain optimal solutions in the B&B algorithm.     

Dynamic window reduction for the multiple depot vehicle scheduling problem with time windows

We consider a widespread branch-and-price approach to solve the multiple depot vehicle scheduling problem with time windows. We describe a dynamic time window reduction technique to speed up this approach. The time windows are transferred from nodes to arcs in order to take advantage of dual information and to tighten as much as possible the time variable domains. The performance of the proposed technique is evaluated through computational experiments on randomly generated instances involving several depots and up to 900 tasks.     

Arcs-states models for the vehicle routing problem with time windows and related problems

This paper presents several Arcs-States models that can be applied to numerous vehicle routing problems, one of which is the well-known vehicle routing problem with capacities and time windows. In these models, the variables correspond to the states (i.e. the resource quantities) of the vehicles when they travel through an arc. The LP relaxation of the problem provides a lower bound that can be embedded in a branch and bound algorithm that solves the problem exactly. However, for the pseudo-polynomial number of variables and constraints of our models, column and row generations have to be used. Generally, in a branch and bound algorithm, the lower bound needs to be very efficient to minimize the size of the branch and bound trees as far as possible. One of the models we present, the time-only, relies on a relaxation of the Arcs-States model where a resource is removed from the states in the variables. Although the quality of the bounds decreases, the global resolution time is greatly improved, as illustrated on instances of Solomon's benchmark.     

An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.     

A theoretical development for the total tardiness problem and its application in branch and bound algorithms

This paper deals with the single machine total tardiness problem, and proves that if the job sequences produced by two heuristics, named as Time Forward and Time Backward algorithms, have the same starting and ending job subsequences, then there exists an optimal job sequence with the starting and ending job subsequences. The computation experiments show that there is a significant improvement of the running time of a branch and bound algorithm with the incorporation of the new property.     

A branch, bound, and remember algorithm for the 1|r i |∑t i scheduling problem

This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r _i |∑t _i scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1|r _i |∑t _i scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.     

Push-relabel based algorithms for the maximum transversal problem

We investigate the push-relabel algorithm for solving the problem of finding a maximum cardinality matching in a bipartite graph in the context of the maximum transversal problem. We describe in detail an optimized yet easy-to-implement version of the algorithm and fine-tune its parameters. We also introduce new performance-enhancing techniques. On a wide range of real-world instances, we compare the push-relabel algorithm with state-of-the-art algorithms based on augmenting paths and pseudoflows. We conclude that a carefully tuned push-relabel algorithm is competitive with all known augmenting path-based algorithms, and superior to the pseudoflow-based ones.     

An exact solution to the TLP problem in an NC machine

This paper considers a job sequencing problem for a single numerical controlled machining center. It is assumed that all the considered jobs must be processed on a single machine provided with a tool magazine with C positions, that no job requires more than C tools to be completely machined and that the tools may be loaded and unloaded from the tool magazine only when the machining operations for each job are completed. The decisional problem is referred to as the tool loading problem (TLP) and it determines the jobs machining sequence as well as the tools to load in the machine tool magazine before the machining operations on each job may start. In industrial cases where the tool switching time is both significant relative to job processing time and proportional to the number of tool switches, the performance criterion is the minimization of the number of tool switches. This paper demonstrates that the TLP is a symmetric sequencing problem. The authors enrich a branch-and-bound algorithm proposed in literature for the TLP with the new symmetric formulation. Computational experiments show the significant improvement obtained by the novel symmetric formulation of the TLP.     

A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements

In this study we consider a U-shaped assembly line balancing problem where each task uses a specified set of equipments and each type of equipment has a specified cost. Our problem is to assign the tasks together with their equipments to the workstations so as to minimize the total equipment cost. We formulate the problem as a mixed integer linear programming model that is capable of solving small sized instances. We propose a branch and bound algorithm that uses efficient precedence relations and lower bounds. We find that the algorithm is able to solve moderate sized problem instances in reasonable times.