×

zbMATH — the first resource for mathematics

A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes. (English) Zbl 1170.90521
Summary: The capacitated \(p\)-median problem (CPMP) consists of finding \(p\) nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
Knapsack; CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Implementing the Dantzig–Fulkerson–Johnson algorithm for large traveling salesman problems. Math. Program. 97, 91153 (2003) · Zbl 1106.90369
[2] Baldacci, R., Hadjiconstantinou, E., Maniezzo, V., Mingozzi, A.: A new method for solving capacitated location problems based on a set partitioning approach. Comput. Oper. Res. 29, 365–386 (2002) · Zbl 0994.90087
[3] Boyd, E.: Generating Fenchel cutting planes for knapsack polyhedra. SIAM J. Optim. 3, 734–750 (1993a) · Zbl 0797.90067
[4] Boyd, E.: Solving integer programs with cutting planes and preprocessing. In: IPCO 1993, pp. 209–220 (1993b) · Zbl 0923.90118
[5] Boyd, E.: Fenchel cutting planes for integer programming. Oper. Res. 42, 53–64 (1994) · Zbl 0809.90104
[6] Boyd, E.: On the convergence Fenchel cutting planes in mixed-integer programming. SIAM J. Optim. 5, 421–435 (1995) · Zbl 0834.90095
[7] Ceselli, A.: Two exact algorithms for the capacitated p-median problem. 4OR 1, 319–340 (2003) · Zbl 1109.90054
[8] Ceselli, A., Righini, G.: A branch and price algorithm for the capacitated p-median problem. Networks 45(3), 125–142 (2005) · Zbl 1101.68722
[9] CPLEX: ILOG CPLEX 10.0 Reference manual. ILOG (2006)
[10] Diaz, J., Fernandez, E.: Hybrid scater search and path relinking for the capacitated p-median problem. Eur. J. Oper. Res. 169(2), 570–585 (2006) · Zbl 1079.90076
[11] Lorena, L., Senne, E.: Local search heuristics for capacitated p-median problems. Netw. Spat. Econ. 3, 407–419 (2003)
[12] Lorena, L., Senne, E.: A column generation approach to capacitated p-median problems. Comput. Oper. Res. 31(6), 863–876 (2004) · Zbl 1048.90132
[13] Maniezzo, V., Mingozzi, A., Baldacci, R.: A Biotomic approach to the capacitated p-median problem. J Heuristics 4, 263–280 (1998) · Zbl 0913.90201
[14] Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[15] Neumaier, A., Shcherbina, O.: Safe bounds in linear and mixed-integer programming. Math. Program. A 99, 283–296 (2004) · Zbl 1098.90043
[16] Pirkul, H.: Efficient algorithms for the capacitated concentrator location problem. Comput. Oper. Res. 13, 197–208 (1987) · Zbl 0617.90019
[17] Pisinger, D.: A minimal algorithm for the 0–1 knapsack problem. Oper. Res. 46, 758–767 (1995) · Zbl 0902.90126
[18] Ramos, M., Saez, J.: Solving capacitated facility location problems by Fenchel cutting planes. J. Oper. Res. Soc. 0, 1–10 (2004)
[19] Ross, G., Soland, R.: Modeling facility location problems as generalized assignment problem. Manage. Sci. 24(3), 345–357 (1977) · Zbl 0378.90066
[20] Savelsbergh, M.: A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6), 831–841 (1997) · Zbl 0895.90161
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.