A heuristic solution procedure for multicommodity integer flows

A heuristic solution procedure for multicommodity integer flows

0.00 Avg rating0 Votes
Article ID: iaor19961337
Country: United Kingdom
Volume: 22
Issue: 10
Start Page Number: 1075
End Page Number: 1087
Publication Date: Dec 1995
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper presents a heuristic method to determine integer-valued solutions for the multi-commodity maximal flow and minimum cost flow 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 arc capacity restrictions that limit the total flow of all commodities along each arc destroy the integrality property for multicommodity flow problems. The proposed heuristic first determines an initial integer-valued solution by dividing the common capacity on each arc among the commodities and decomposing the problem into single commodity flow problems one for each commodity. The heuristic then attempts to reallocate the capacity, one arc 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.

Reviews

Required fields are marked *. Your email address will not be published.