On the minimum cost multiple-source unsplittable flow problem

On the minimum cost multiple-source unsplittable flow problem

0.00 Avg rating0 Votes
Article ID: iaor20083376
Country: France
Volume: 41
Issue: 3
Start Page Number: 253
End Page Number: 273
Publication Date: Jul 2007
Journal: RAIRO Operations Research
Authors: ,
Keywords: programming: integer
Abstract:

The minimum cost multiple-source unsplittable flow problem is studied in this paper. A simple necessary condition to get a solution is proposed. It deals with capacities and demands and can be seen as a generalization of the well-known semi-metric condition for continuous multicommdity flows. A cutting plane algorithm is derived using a superadditive approach. The inequalities considered here are valid for single knapsack constraints. They are based on nondecreasing superadditive functions and can be used to strengthen the relaxation of any integer program with knapsack constraints. Some numerical experiments confirm the efficiency of the inequalities introduced in the paper.

Reviews

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