Capacitated facility location: Separation algorithms and computational experience. (English) Zbl 0919.90096

Summary: We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well-known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here, we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems.


90B80 Discrete location and assignment


Full Text: DOI


[1] Aardal, K., 1992. On the solution of one and two-level capacitated facility location problems by the cutting plane approach. Ph.D. Thesis, Université Catholique de Louvain (Louvain-la-Neuve).
[2] Aardal, K., Pochet, Y., Wolsey, L.A., 1995. Capacitated facility location: Valid inequalities and facets. Mathematics of Operations Research 20, 562–582. · Zbl 0846.90088
[3] Bienstock, D., Günlük, O., 1994. Capacitated network design – Polyhedral structure and computation. Working Paper, Columbia University (to appear in INFORMS Journal on Computing). · Zbl 0871.90031
[4] Cho, D.C., Johnson, E.L., Padberg, M.W., Rao, M.R., 1983a. On the uncapacitated plant location problem. I: Valid inequalities and facets. Mathematics of Operations Research 8, 579–589. · Zbl 0536.90029
[5] Cho, D.C., Padberg, M.W., Rao, M.R., 1983b. On the uncapacitated plant location problem. II: Facets and lifting theorems. Mathematics of Operations Research 8, 590–612. · Zbl 0536.90030
[6] Cornuéjols, G., Thizy, J.-M., 1982. Some facets of the simple plant location problem. Mathematical Programming 23, 50–74. · Zbl 0485.90069
[7] Cornuéjols, G., Fisher, M.L., Nemhauser, G.L., 1977. On the uncapacitated location problem. Annals of Discrete Mathematics 1, 163–177.
[8] Cornuéjols, G., Sridharan, R., Thizy, J.-M., 1991. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research 50, 280–297. · Zbl 0734.90046
[9] Deng, Q., Simchi-Levi, D., 1993. Valid inequalities, facets and computational experience for the capacitated concentrator location problem. Research Report, Department of Industrial Engineering and Operations Research, Columbia University, New York.
[10] Guignard, M., 1980. Fractional vertices, cuts and facets for the simple plant location problem. Mathematical Programming 12, 150–162. · Zbl 0439.90061
[11] Leung, J.M.Y., Magnanti, T.L., 1989. Valid inequalities and facets of the capacitated plant location problem. Mathematical Programming 44, 271–291. · Zbl 0686.90021
[12] Magnanti, T.L., Mirchandani, P., Vachani, R., 1995. Modeling and solving the two-facility capacitated network loading problem. Operations Research 43, 142–157. · Zbl 0830.90051
[13] Padberg, M.W., 1973. On the facial structure of set packing polyhedra. Mathematical Programming 5, 199–215. · Zbl 0272.90041
[14] Padberg, M.W., Van Roy, T.J., Wolsey, L.A., 1985. Valid inequalities for fixed charge problems. Operations Research 33, 842–861. · Zbl 0579.90072
[15] Savelsbergh, M.W.P., Sigismondi, G.C., Nemhauser, G.L., 1994. Functional description of MINTO, a Mixed INTeger Optimizer. Operations Research Letters 15, 47–58. · Zbl 0806.90095
[16] Van Roy, T.J., Wolsey, L.A., 1987. Solving mixed-integer programming problems using automatic reformulation. Operations Research 35, 45–57. · Zbl 0614.90082
[17] Wolsey, L.A., 1975. Faces for a linear inequality in 0–1 variables. Mathematical Programming 8, 165–178. · Zbl 0314.90063
[18] Wolsey, L.A., 1989. Submodularity and valid inequalities in capacitated fixed charge networks. Operations Research Letters 8, 119–124. · Zbl 0674.90027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.