×

An improved cut-and-solve algorithm for the single-source capacitated facility location problem. (English) Zbl 1390.90008

Summary: In this paper, we present an improved cut-and-solve algorithm for the single-source capacitated facility location problem. The algorithm consists of three phases. The first phase strengthens the integer program by a cutting plane algorithm to obtain a tight lower bound. The second phase uses a two-level local branching heuristic to find an upper bound, and if optimality has not yet been established, the third phase uses the cut-and-solve framework to close the optimality gap. Extensive computational results are reported, showing that the proposed algorithm runs 10–80 times faster on average compared to state-of-the-art problem-specific algorithms.

MSC:

90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C10 Integer programming
90C11 Mixed integer programming
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahuja R, Orlin J, Pallottino S, Scaparra M, Scutellà M (2004) A multi-exchange heuristic for the single-source capacitated facility location problem. Manag Sci 50(6):749-760 · Zbl 1232.90257 · doi:10.1287/mnsc.1030.0193
[2] Avella P, Boccia M, Salerno S (2011) A computational study of dicut reformulation for the single source capacitated facility location problem. Stud Inf Univ 9(3):21-42
[3] Balas E, Zemel E (1978) Facets of the knapsack polytope from minimal covers. SIAM J Appl Math 34(1):119-148 · Zbl 0385.90083 · doi:10.1137/0134010
[4] Barceló J, Casanovas J (1984) A heuristic Lagrangean algorithm for the capacitated plant location problem. Eur J Oper Res 15(2):212-226 · Zbl 0544.90025 · doi:10.1016/0377-2217(84)90211-X
[5] Barceló J, Fernández E, Jörnsten K (1991) Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem. Eur J Oper Res 53(1):38-45 · Zbl 0734.90044 · doi:10.1016/0377-2217(91)90091-9
[6] Barceló J, Hallefjord Å, Fernández E, Jörnsten K (1990) Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing. Oper Res Spektrum 12(2):79-88 · Zbl 0713.90041 · doi:10.1007/BF01784983
[7] Bitran G, Chandru V, Sempolinski D, Shapiro J (1981) Inverse optimization: an application to the capacitated plant location problem. Manag Sci 27(10):1120-1141 · Zbl 0465.90027 · doi:10.1287/mnsc.27.10.1120
[8] Boccia M, Sforza A, Sterle C, Vasilyev I (2008) A cut and branch approach for the capacitated p-median problem based on Fenchel cutting planes. J Math Modell Algorithms 7(1):43-58 · Zbl 1170.90521 · doi:10.1007/s10852-007-9074-5
[9] Boyd EA (1993) Generating Fenchel cutting planes for Knapsack polyhedra. SIAM J Optim 3(4):734-750 · Zbl 0797.90067 · doi:10.1137/0803038
[10] Ceselli A, Righini G (2005) A branch-and-price algorithm for the capacitated p-median problem. Networks 45(3):125-142 · Zbl 1101.68722 · doi:10.1002/net.20059
[11] Chen C, Ting C (2008) Combining Lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem. Transp Res Part E Logist Transp Rev 44(6):1099-1122 · doi:10.1016/j.tre.2007.09.001
[12] Climer S, Zhang W (2006) Cut-and-solve: an iterative search strategy for combinatorial optimization problems. Artif Intell 170(8):714-738 · Zbl 1131.90050 · doi:10.1016/j.artint.2006.02.005
[13] Contreras I, Díaz J (2008) Scatter search for the single source capacitated facility location problem. Ann Oper Res 157(1):73-89 · Zbl 1153.90481 · doi:10.1007/s10479-007-0193-1
[14] Cornuejols G, Sridharan R, Thizy J (1991) A comparison of heuristics and relaxations for the capacitated plant location problem. Eur J Oper Res 50(3):280-297 · Zbl 0734.90046 · doi:10.1016/0377-2217(91)90261-S
[15] Correia I, Gouveia L, Saldanha-da Gama L (2010) Discretized formulations for capacitated location problems with modular distribution costs. Eur J Oper Res 204(2):237-244 · Zbl 1178.90223 · doi:10.1016/j.ejor.2009.10.027
[16] Díaz J, Fernández E (2002) A branch-and-price algorithm for the single source capacitated plant location problem. J Oper Res Soc 53:728-740 · Zbl 1130.90354 · doi:10.1057/palgrave.jors.2601353
[17] Fischetti M, Lodi A (2003) Local branching. Math Progr 98(1-3):23-47 · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[18] Fischetti M, Polo C, Scantamburlo M (2004) A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks 44(2):61-72 · Zbl 1055.90054 · doi:10.1002/net.20017
[19] Gadegaard S, Klose A, Nielsen L (2016) A “cut-and-solve” solver for the single source capacitated facility location problem. GitHub, source code (v1.2.0). https://github.com/SuneGadegaard/SSCFLPsolver · Zbl 1131.90050
[20] Geoffrion A (1974) Lagrangean relaxation for integer programming. In: Approaches to integer programming. Vol. 2 of Mathematical Programming Studies. Springer, Berlin, pp 82-114 · Zbl 0395.90056
[21] Gu Z, Nemhauser G, Savelsbergh M (1998) Lifted cover inequalities for 0-1 integer programs: computation. INFORMS J Comput 10(4):427-437 · doi:10.1287/ijoc.10.4.427
[22] Holmberg K, Rönnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur J Oper Res 113(3):544-559 · Zbl 0947.90059 · doi:10.1016/S0377-2217(98)00008-3
[23] Kaparis K, Letchford A (2010) Separation algorithms for 0-1 knapsack polytopes. Math Progr 124(1-2):69-91 · Zbl 1198.90297 · doi:10.1007/s10107-010-0359-5
[24] Karp, R.; Miller, R. (ed.); Thatcher, J. (ed.); Bohlinger, J. (ed.), Reducibility among combinatorial problems, 85-103 (1972), Berlin · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9
[25] Klincewicz J, Luss H (1986) A Lagrangian relaxation heuristic for capacitated facility location with single-source constraints. J Oper Res Soc 37:495-500 · Zbl 0588.90025 · doi:10.1057/jors.1986.84
[26] Klose A, Görtz S (2007) A branch-and-price algorithm for the capacitated facility location problem. Eur J Oper Res 179(3):1109-1125 · Zbl 1163.90607 · doi:10.1016/j.ejor.2005.03.078
[27] Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0-1 knapsack problem. Manag Sci 45(3):414-424 · Zbl 1231.90338 · doi:10.1287/mnsc.45.3.414
[28] Neebe A, Rao M (1983) An algorithm for the fixed-charge assigning users to sources problem. J Oper Res Soc 34:1107-1113 · Zbl 0521.90075 · doi:10.1057/jors.1983.242
[29] Nemhauser G, Wolsey L (1988) Integer and combinatorial optimization. Wiley, New York · Zbl 0652.90067 · doi:10.1002/9781118627372
[30] Pirkul H (1987) Efficient algorithms for the capacitated concentrator location problem. Comput Oper Res 14(3):197-208 · Zbl 0617.90019 · doi:10.1016/0305-0548(87)90022-0
[31] Rönnqvist M, Tragantalerngsak S, Holt J (1999) A repeated matching heuristic for the single-source capacitated facility location problem. Eur J Oper Res 116(1):51-68 · Zbl 1009.90064 · doi:10.1016/S0377-2217(98)00045-9
[32] Sridharan R (1993) A Lagrangian heuristic for the capacitated plant location problem with single source constraints. Eur J Oper Res 66(3):305-312 · Zbl 0771.90062 · doi:10.1016/0377-2217(93)90219-D
[33] Weismantel R (1997) On the 0/1 knapsack polytope. Math Progr 77(3):49-68 · Zbl 0891.90130 · doi:10.1007/BF02614517
[34] Yang Z, Chu F, Chen H (2012) A cut-and-solve based algorithm for the single-source capacitated facility location problem. Eur J Oper Res 221(3):521-532 · Zbl 1253.90143 · doi:10.1016/j.ejor.2012.03.047
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.