×

Valid inequalities and facets of the capacitated plant location problem. (English) Zbl 0686.90021

The authors investigate the polyhedral structure of the capacitated plant location problem. A family of so-called residual capacity inequalities is considered and it is shown that most of these inequalities are facets. Some modified versions of the capacitated plant location problem are also examined.
Reviewer: J.Terno

MSC:

90B05 Inventory, storage, reservoirs
52Bxx Polytopes and polyhedra
90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Balas and M.W. Padberg, ”Set partitioning: A survey,”Siam Review 18 (1976) 710–760. · Zbl 0347.90064 · doi:10.1137/1018115
[2] I. Barany, T.J. Van Roy and L.A. Wolsey, ”Multi-item capacitated lot sizing problems,”Management Science 30 (1984) 1255–1261. · Zbl 0601.90037 · doi:10.1287/mnsc.30.10.1255
[3] G. Bitran, V. Chandru, D. Sempolinski and J. Shapiro, ”Inverse optimization: An application to the capacitated plant location problem,”Management Science 27 (1981) 1120–1141. · Zbl 0465.90027 · doi:10.1287/mnsc.27.10.1120
[4] D.C. Cho, E.L. Johnson, M.W. Padberg and M.R. Rao, ”On the uncapacitated plant location problem I: Valid inequalities,”Mathematics of Operations Research 8 (1983a) 579–589. · Zbl 0536.90029 · doi:10.1287/moor.8.4.579
[5] D.C. Cho, E.L. Johnson, 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
[6] N. Christofides and J.E. Beasley, ”Extensions to a Lagrangian relaxation approach for the capacitated warehouse location problem,”European Journal of Operational Research 12 (1983) 19–28. · Zbl 0499.90027 · doi:10.1016/0377-2217(83)90179-0
[7] G. Cornuejols, M.L. Fisher and G.L. Nemhauser, ”Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms,”Management Science 23 (1977a) 789–810. · Zbl 0361.90034 · doi:10.1287/mnsc.23.8.789
[8] G. Cornuejols, M.L. Fisher and G.L. Nemhauser, ”On the uncapacitated location problem,”Annals of Discrete Mathematics 1 (1977b) 163–177. · Zbl 0358.90040 · doi:10.1016/S0167-5060(08)70732-5
[9] G. Cornuejols, G.L. Nemhauser and L.A. Wolsey, ”The uncapacitated facility location problem,” MSRR-493, GSIA, Carnegie-Mellon University (Pittsburgh, PA, 1983). · Zbl 0727.90043
[10] 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
[11] 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
[12] H. Crowder and M.W. Padberg, ”Solving large scale symmetric travelling salesman problems to optimality,”Management Science 26 (1980) 495–509. · Zbl 0444.90068 · doi:10.1287/mnsc.26.5.495
[13] G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, ”Solution of a large-scale travelling salesman problem,”Operations Research 2 (1954) 394–410.
[14] D.P. Dykstra and J.L. Riggs, ”An application of facilities location theory to the design of forest harvesting areas,”AIIE Transactions 9 (1977) 270–277.
[15] G.D. Eppen and R.K. Martin, ”Solving multi-item capacitated lot sizing problems using variable redefinition,”Operations Research 35 (1987) 832–848. · Zbl 0639.90046 · doi:10.1287/opre.35.6.832
[16] M.L. Fisher and D.S. Hochbaum, ”Database location in computer networks,”Journal of the ACM 27 (1980) 718–735. · Zbl 0445.68071 · doi:10.1145/322217.322226
[17] A.M. Geoffrion and R. McBride, ”Lagrangian relaxation applied to capacitated facility location problems,”AIIE Transactions 10 (1978) 40–48.
[18] M. Grötschel, ”Polyhedral combinatorics,” in: M. O’hEigeartaigh, J.K. Lenstra and A.H.G. Rinnooy Kan, eds.,Combinatorial Optimization: Annotated Bibliographies (Wiley, New York, 1985) pp. 1–10.
[19] M. Grötschel, M. Jünger and G. Reinelt, ”A cutting plane algorithm for the linear ordering problem,”Operations Research 32 (1984) 1195–1220. · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[20] M Grötschel, M. Jünger and G. Reinelt, ”Facets for the linear ordering problem,”Mathematical Programming 33 (1985) 43–60. · Zbl 0577.05035 · doi:10.1007/BF01582010
[21] M. Grötschel, L. Lovász and A. Schrijver, ”The consequences of the ellipsoid method for combinatorial optimization,”Combinatorica 1 (1981) 169–198. · Zbl 0492.90056 · doi:10.1007/BF02579273
[22] M. Guignard, ”Fractional vertices, cuts and facets of the simple plant location problem,”Mathematical Programming 12 (1980) 150–162. · Zbl 0439.90061
[23] M. Guignard and K. Spielberg, ”A direct dual method for the mixed plant location problem with some side constraints,”Mathematical Programming 17 (1979) 198–228. · Zbl 0416.90052 · doi:10.1007/BF01588244
[24] S.K. Jacobsen, ”Heuristics for the capacitated plant location problem,”European Journal of Operational Research 12 (1983) 253–261. · Zbl 0514.90018 · doi:10.1016/0377-2217(83)90195-9
[25] E.L. Johnson, M.M. Kostreva and U.H. Suhl, ”Solving 0–1 integer programming problems arising from large scale planning models,”Operations Research 33 (1985) 803–820. · Zbl 0569.90056 · doi:10.1287/opre.33.4.803
[26] J. Krarup and P.M. Pruzan, ”The simple plant location problem: Survey and synthesis,”European Journal of Operational Research 12 (1983) 36–81. · Zbl 0506.90018 · doi:10.1016/0377-2217(83)90181-9
[27] G. Laporte, H. Mercure and Y. Nobert, ”Cutting planes based on bin packing solutions for the capacitated vehicle routing problem,” G-86-10, École des Hautes Études Commerciales (Montreal, Canada, 1986).
[28] J.M.Y. Leung, ”Polyhedral structure of capacitated fixed charge problems and a problem in delivery route planning,” Ph.D. thesis, Operations Research Center, MIT (Cambridge, MA, 1985).
[29] J.M.Y. Leung, T.L. Magnanti and R. Vachani, ”Facets and algorithms for capacitated lot sizing,”Mathematical Programming 45 (1989) 331–359. · Zbl 0681.90060 · doi:10.1007/BF01589110
[30] T.L. Magnanti and R.T. Wong, ”Decomposition methods for facility location problems,” in: R.L. Francis and P. Mirchandani, eds.,Discrete Location Theory (Wiley, New York, 1989). · Zbl 0728.90052
[31] K. Martin and L. Schrage, ”Subset coefficient reduction cuts for 0/1 mixed integer programming,”Operations Research 33 (1985) 505–526. · Zbl 0583.90075 · doi:10.1287/opre.33.3.505
[32] G.L. Nemhauser and L.E. Trotter, ”Properties of vertex packing and independence system polyhedra,”Mathematical Programming 6 (1974) 48–61. · Zbl 0281.90072 · doi:10.1007/BF01580222
[33] M.W. Padberg, ”On the facial structure of set packing problems,”Mathematical Programming 5 (1973) 199–215. · Zbl 0272.90041 · doi:10.1007/BF01580121
[34] M.W. Padberg and S. Hong, ”On the symmetric travelling salesman problem: A computational study,”Mathematical Programming Study 12 (1980) 78–107. · Zbl 0435.90071
[35] M.W. Padberg, T.J. Van Roy and L.A. Wolsey, ”Valid linear inequalities for fixed charge problems,”Operations Research 33 (1985) 842–861. · Zbl 0579.90072 · doi:10.1287/opre.33.4.842
[36] G.T. Ross and R.M. Soland, ”Modelling facility location problems as generalized assignment problems,”Management Science 24 (1977) 345–357. · Zbl 0378.90066 · doi:10.1287/mnsc.24.3.345
[37] A.S. Tanenbaum,Computer Networks (Prentice-Hall, Englewood Cliffs, NJ, 1981).
[38] L.E. Trotter, Jr., ”A class of facet producing graphs for vertex packing polyhedra,”Discrete Mathematics 12 (1975) 373–388. · Zbl 0314.05111 · doi:10.1016/0012-365X(75)90077-1
[39] T.J. Van Roy, ”A cross decomposition algorithm for capacitated facility location,”Operations Research 34 (1986) 145–163. · Zbl 0594.90022 · doi:10.1287/opre.34.1.145
[40] T.J. Van Roy and D. Erlenkotter, ”A dual-based procedure for dynamic facility location,”Management Science 28 (1982) 1091–1105. · Zbl 0495.90033 · doi:10.1287/mnsc.28.10.1091
[41] T.J. Van Roy and L.A. Wolsey, ”Valid inequalities and separation for uncapacitated fixed charge networks,”Operations Research Letters 4 (1985) 105–112. · Zbl 0575.90045 · doi:10.1016/0167-6377(85)90012-4
[42] T.J. Van Roy and L.A. Wolsey, ”Valid inequalities for mixed zero–one programs,”Discrete Applied Mathematics 14 (1986) 199–213. · Zbl 0593.90058 · doi:10.1016/0166-218X(86)90061-2
[43] R.T. Wong, ”Location and network design,” in: M. O’hEigeartaigh, J.K. Lenstra and A.H.G. Rinnooy Kan, eds.,Combinatorial Optimization: Annotated Bibliographies (Wiley, New York, 1985) pp. 127–147. · Zbl 0556.90018
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.