Finding all optimal solutions to the network flow problem

1986

The problem examined in this paper is as follows: Given a feasible optimum basic solution (f.o.b.s) of the minimum cost network flow problem, find all the f.o.b.s of this problem. The existence of alternative f.o.b.s is characterized by means of elementary circuits of zero cost and length greater than two in the incremental graph associated to the given f.o.b.s. It is shown that any alternative f.o.b.s. can be obtained from the original one by circulating flow through elementary circuits belonging to a succession of incremental graphs. This result leads to the construction of an efficient algorithm to obtain all f.o.b.s. of the network flow problem.

An Exact Algorithm for the Quadratic Assignment Problem on a Tree

1989

The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a redu…

An algorithm for the Rural Postman problem on a directed graph

1986

The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computation…

An optimal method for the mixed postman problem

2005