New formulation and relaxation to solve a concave-cost network flow problem

New formulation and relaxation to solve a concave-cost network flow problem

0.00 Avg rating0 Votes
Article ID: iaor1998366
Country: United Kingdom
Volume: 48
Issue: 3
Start Page Number: 278
End Page Number: 287
Publication Date: Mar 1997
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: Lagrangean relaxation
Abstract:

This paper studies a minimum cost, multicommodity network flow problem in which the total cost is piecewise linear, concave of the total flow along the arcs. Specifically, the problem can be defined as follows. Given a directed network, a set of pairs of communicating nodes and a set of available capacity ranges and their corresponding variable and fixed cost components for each arc, the problem is to select for each arc a range and identify a path for each commodity between its source and destination nodes so as to minimize the total costs. The paper also extends the problem to the case of piecewise nonlinear, concave cost function. New mathematical programming formulations of the problems are presented. Efficient solution procedures based on Lagrangean relaxations of the problems are developed. Extensive computational results across a variety of networks are reported. These results indicate that the solution procedures are effective for a wide range of traffic loads and different cost structures. They also show that this work represents an improvement over previous work made by other authors. This improvement is the result of the introduction of the new formulations of the problems and their relaxations.

Reviews

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