A branch and bound algorithm for capacitated vehicle routing is described. Lower bounds are derived by relaxing the subtour elimination and vehicle capacity constraints to yield a perfect b-matching problem. Bounds are strengthened by using Lagrange multipliers to enforce subtour elimination and capacity constraints. Computational results are reported for problems taken from the literature for sizes up to 61 vertices. With the exception of the 48 vertex instance (att48.vrp), the algorithm solves all problems in TSPLIB having 51 or fewer vertices. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We describe an algorithm for finding a minimum cost perfect b-matching in a weighted undirected graph G=(V,E), with arbitrary edge capacities. The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. The most significant step involves a primal-dual tree growth procedure that selectively activates and deactivates facet inducing blossom constraints. The algorithm progressively eliminates half-integral values from the primal solution without creating any new fractional values. We introduce the concept of frozen supervertices to address previously unknown complications that arise due to the presence of non-unit capacity edges. We discuss the relationship of the algorithm to previously published cutting plane methods. The algorithm is guaranteed to terminate in O(|V| 2 |E|) steps, although computational results suggest that much less effort is typically required. Computational results show the algorithm to be effective on problems derived from TSPLIB ranging in size from 532 to 3795 vertices for various b values. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal-dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V|2|E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problem[1] ranging in size from 17 to 11,849 vertices. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Parallel computing adds an extra dimension of complexity to the design of mathematical programming algorithms. This complexity complicates the comparison of algorithms and introduces an additional set of performance metrics. The paper by Barr and Hickman (BH) is well written as they have knitted together expert opinion and their own experience into a reasonable set of guidelines for avoiding the pitfalls that arise in the use of these metrics. BH motivate the guidelines with an insightful summary of fundamental parallel computer issues and how they relate to measuring algorithm effectiveness. Below we expand on those comments of BH which we have found especially relevant. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A parallel version of the shortest augmenting path algorithm for the assignment problem 1s described.Although generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorlthm, using several augmenting paths in parallel does require a new dual variable recalculation Graph Theory -graph algorithms; network problems: path and cmcmt problems: I. 1.