A HEURISTIC SOLUTION PROCEDURE FOR MULTICOMMODITY INTEGER FLOWS

This paper presents a heuristic method to determine integer-valued solutions for the multi-commodity maximal flow and minimum cost bow problems. It is well known that for single commodity flow problems the optimal solutions are integer-valued provided the necessary data (capacities, supplies, demands) are integers. However, the presence of mutual are capacity restrictions that limit the total flow of all commodities along each are destroy the integrality property for multicommodity bow problems. The proposed heuristic first determines an initial integer-valued solution by dividing the common capacity on each are among the commodities and decomposing the problem into single commodity bow problems one for each commodity. The heuristic then attempts to reallocate the capacity, one are at a time, using parametric analysis and the corresponding dual variable information to search for better solutions. An application of the multicommodity minimum cost integer flow problem to the equipment replacement problem and computational experience for the proposed heuristic are also discussed.