A polyhedral approach to an integer multicommodity flow problem

A polyhedral approach to an integer multicommodity flow problem

0.00 Avg rating0 Votes
Article ID: iaor20013560
Country: Netherlands
Volume: 101
Issue: 1/3
Start Page Number: 13
End Page Number: 36
Publication Date: Apr 2000
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: programming: integer
Abstract:

In this paper we propose a branch-and-cut algorithm for the exact solution of an integer multicommodity flow problem. This NP-hard problem finds important applications in transportation, very large scale integration design, and telecommunications. We consider alternative formulations of the problem and describe several classes of valid inequalities. We describe lifting procedures to extend a given valid inequality for the problem with k commodities, to that having a larger number of commodities. We introduce a new large class of valid constraints, the multi-handle comb inequalities. The polyhedral structure of the integer multicommodity polytope is studied in the case of unit edge capacities. We prove that this polytope is full dimensional and show that some multi-handle comb inequalities are facet defining. Also, the lifting procedures are facet preserving under certain conditions. A branch-and-cut algorithm for the exact solution of the problem is then outlined, and separation algorithms for the main classes of inequalities studied in the paper are proposed. Computational results on several classes of test problems are finally reported, with a comparison between two different formulations.

Reviews

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