Variable disaggregation in network flow problems with piecewise linear costs

Variable disaggregation in network flow problems with piecewise linear costs

0.00 Avg rating0 Votes
Article ID: iaor20081455
Country: United States
Volume: 55
Issue: 1
Start Page Number: 146
End Page Number: 157
Publication Date: Jan 2007
Journal: Operations Research
Authors: , ,
Keywords: programming: integer
Abstract:

We study mixed-integer programming formulations, based upon variable disaggregation, for generic multicommodity network flow problems with nonconvex piecewise linear costs, a problem class that arises frequently in many application domains in telecommunications, transportation, and logistics. We present several structural results for these formulations, and we analyze the results of extensive experiments on a large set of instances with various characteristics. In particular, we show that the linear programming relaxation of an extended disaggregated model approximates the objective function by its lower convex envelope in the space of commodity flows. Together, the theoretical and computational results allow us to suggest which formulation might be the most appropriate, depending on the characteristics of the problem instances.

Reviews

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