LP extreme points and cuts for the fixed-charge network design problem |
| |
Authors: | Anantaram Balakrishnan |
| |
Institution: | (1) Krannert Graduate School of Management, Purdue University, 47907 West Lafayette, IN, USA |
| |
Abstract: | Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple
commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and
carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and
routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design
problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem.
The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear
programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme
points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also
serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions.
We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known
properties of the plant location problem.
Supported in part by grant number ECS-831-6224 of the National Science Foundation. |
| |
Keywords: | Network design cutting planes linear programming extreme points |
本文献已被 SpringerLink 等数据库收录! |
|