LP extreme points and cuts for the fixed-charge network design problem.(English)Zbl 0637.90095
Summary: Many design decisions in transportation, 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 uncapacited 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 strengthening 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.
MSC:
| 90C35 | Programming involving graphs or networks |
Cite
Full Text:DOI
References:
| [1] | A. Balakrishnan, ”Valid inequalities and algorithms for the network design problem with an application to LTL consolidation,” Dissertation, Sloan School of Management, Massachusetts Institute of Technology (Cambridge, MA, 1984). |
| [2] | A. Balakrishnan and S.C. Graves, ”A composite algorithm for the concave-cost LTL consolidation problem,” Working paper No. 877, Krannert Graduate School of Management, Purdue University (West Lafayette, 1985). |
| [3] | D.C. Cho, E.L. Johnson, M.W. Padberg and M.R. Rao, ”On the uncapacitated plant location problem I: Valid inequalities and facets,”Mathematics of Operations Research 8 (1983a) 579–589. ·Zbl 0536.90029 ·doi:10.1287/moor.8.4.579 |
| [4] | D.C. Cho, M.W. Padberg and M.R. Rao, ”On the uncapacitated plant location problem II: Facets and lifting theorems,”Mathematics of Operations Research 8 (1983b) 590–612. ·Zbl 0536.90030 ·doi:10.1287/moor.8.4.590 |
| [5] | V. Chvatal, ”Edmonds polytopes and a hierarchy of combinatiorial problems,”Discrete Mathematics 4 (1973) 305–337 ·Zbl 0253.05131 ·doi:10.1016/0012-365X(73)90167-2 |
| [6] | G. Cornuejols, M. Fisher and G.L. Nemhauser, ”On the uncapacitated plant location problems,”Annals of Discrete Mathematics 1 (1977) 163–177. ·Zbl 0358.90040 ·doi:10.1016/S0167-5060(08)70732-5 |
| [7] | G. Cornuejols and J.M. Thizy, ”Some facets of the simple plant location polytope,”Mathematical Programming 23 (1982) 50–74. ·Zbl 0485.90069 ·doi:10.1007/BF01583779 |
| [8] | H. Crowder, E.L. Johnson and M.W. Padberg, ”Solving large-scale zero-one linear programming problems,”Operations Research 31 (1983) 803–834. ·Zbl 0576.90065 ·doi:10.1287/opre.31.5.803 |
| [9] | D. Erlenkotter, ”A dual-based procedure for uncapacitated facility location,”Operations Research 26 (1978) 992–1009. ·Zbl 0422.90053 ·doi:10.1287/opre.26.6.992 |
| [10] | M. Grotschel and W.R. Pulleybland, ”Weakly bipartite graphs and the max cut problem,”Operations Research Letters 1 (1981) 23–27. ·Zbl 0494.90078 ·doi:10.1016/0167-6377(81)90020-1 |
| [11] | M. Guignard, ”Fractional vertices, cuts and facets of the simple plant location problem,”Mathematical Programming 12 (1980) 150–162. ·Zbl 0439.90061 |
| [12] | A.S. Lapaugh and C.H. Papadimitriou, ”The even-path problem for graphs and digraphs,”Network 14 (1984) 507–513. ·Zbl 0552.68059 ·doi:10.1002/net.3230140403 |
| [13] | E.L. Lawler,Combinatioal Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). ·Zbl 0413.90040 |
| [14] | T.L. Magnanti and R.T. Wong, ”Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria,”Operations Research 29 (1981) 464–484. ·Zbl 0455.90064 ·doi:10.1287/opre.29.3.464 |
| [15] | T.L. Magnanti and R.T. Wong, ”Netwok design and transporation planning: Models and algorithms,”Transporation Science 18 (1984) 1–55. ·doi:10.1287/trsc.18.1.1 |
| [16] | T.L. Magnanti, R.T. Wong and P. Mireault, ”Tailoring Benders decomposition for uncapacitated network design,”Mathematical Programming Study 26 (1986) 112–154. ·Zbl 0596.90098 |
| [17] | W.B. Powell and Y. Sheffi, ”The load planning problem of LTL motor carriers: Problem description and a proposed solution approach,”Transportation Research 17A (1983) 471–480. |
| [18] | R.L. Rardin and U. Choe, ”Tighter relaxations of fixed charge network flow problem,” Technical report No. J-79-18, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, 1979). |
| [19] | A. Schrijver, ”On cutting planes,”Annals of Discrete Mathematics 9 (1980) 291–296. ·Zbl 0441.90070 ·doi:10.1016/S0167-5060(08)70085-2 |
| [20] | H.P. Williams, ”Experiments in the formulation of integer programming problems,”Mathematical Programming Study 2 (1974) 180–197. ·Zbl 0353.90062 |
| [21] | R.T. Wong, ”A dual ascent approach for Steiner tree problems on a directed graph,”Mathematical Programming 28 (1984) 271–287. ·Zbl 0532.90092 ·doi:10.1007/BF02612335 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
