This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Croxton, K. L. Articles by Magnanti, T. L. Search for Related Content

Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs

Fisher College of Business, The Ohio State University, 518 Fisher Hall, 2100 Neil Avenue, Columbus, Ohio 43210-1144
Département d’informatique et de recherche opérationnelle and Centre de recherche sur les transports, Université de Montréal, C.P. 6128, succ. Centre-ville, Montreal, Quebec, Canada H3C 3J7
School of Engineering and Sloan School of Management, Massachusetts Institute of Technology, Room 1-206, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139-4307
croxton_4{at}cob.osu.edu
bernard{at}crt.umontreal.ca
magnanti{at}mit.edu

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.

Subject classifications: mathematics; piecewise linear; networks/graphs; multicommodity; theory.
History: Received November 2003; revision received February 2005; accepted August 2005.