Semi-Lagrangian relaxation applied to the uncapacitated facility location problem. (English) Zbl 1244.90168
Summary: We show how the performance of general purpose Mixed Integer Programming (MIP) solvers, can be enhanced by using the Semi-Lagrangian Relaxation (SLR) method. To illustrate this procedure we perform computational experiments on large-scale instances of the Uncapacitated Facility Location (UFL) problems with \(unknown\) optimal values. CPLEX solves 3 out of the 36 instances. By combining CPLEX with SLR, we manage to solve 18 out of the 36 instances and improve the best known lower bound for the other instances. The key point has been that, on average, the SLR approach, has reduced by more than 90% the total number of relevant UFL variables.
Keywords:
Lagrangian relaxation; mixed integer programming; uncapacitated facility location (UFL) problemSoftware:
CPLEXReferences:
| [1] | Avella, P., Sassano, A., Vasil’ev, I.: Computational study of large-scale p-median problems. Math. Program. 109(1), 89–114 (2007) · Zbl 1275.90112 · doi:10.1007/s10107-005-0700-6 |
| [2] | Babonneau, F., Beltran, C., Haurie, A.B., Tadonki, C., Vial, J.-Ph.: Proximal-ACCPM: a versatile oracle based optimization method. In: Kontoghiorghes, E.J., Gatu, C. (eds.) Advances in Computational Economics, Finance and Management Science. Advances on Computational Management Science, pp. 200–224. Springer, Berlin (2006) · Zbl 1118.90056 |
| [3] | Baotic, M.: Matlab interface for CPLEX (2004). http://control.ee.ethz.ch/hybrid/cplexint.php |
| [4] | Barahona, F., Chudak, F.: Near-optimal solutions to large scale facility location problems technical report. Technical Report RC21606, IBM Watson Research Center (1999) · Zbl 1140.90442 |
| [5] | Beltran, C., Tadonki, C., Vial, J.-Ph.: Solving the p-median problem with a semi-Lagrangian relaxation. Comput. Optim. Appl. 35(2), 239–260 (2006) · Zbl 1151.90521 · doi:10.1007/s10589-006-6513-6 |
| [6] | Beltran-Royo, C.: A conjugate Rosen’s gradient projection method with global line search for piecewise linear concave optimization. Eur. J. Oper. Res. 182(2), 536–551 (2007) · Zbl 1121.90089 · doi:10.1016/j.ejor.2006.08.057 |
| [7] | Briant, O., Naddef, D.: The optimal diversity management problem. Oper. Res. 52(4), 515–526 (2004) · Zbl 1165.90432 · doi:10.1287/opre.1040.0108 |
| [8] | Canovas, L., Landete, L., Marin, A.: On the facets of the simple plant location packing polytope. Discrete Appl. Math. 124, 27–53 (2002) · Zbl 1175.90326 · doi:10.1016/S0166-218X(01)00328-6 |
| [9] | Cho, D.Ch., Johnson, E.L., Padberg, M.W., Rao, M.R.: On the uncapacitated facility location problem I: Valid inequalities and facets. Math. Oper. Res. 8(4), 590–612 (1983) · Zbl 0536.90030 · doi:10.1287/moor.8.4.590 |
| [10] | Cho, D.Ch., Padberg, M.W., Rao, M.R.: On the uncapacitated facility location problem II: Facets and lifting theorems. Math. Oper. Res. 8(4), 590–612 (1983) · Zbl 0536.90030 · doi:10.1287/moor.8.4.590 |
| [11] | Conn, A.R., Cornuéjols, G.: A projection method for the uncapacitated facility location problem. Math. Program. 46, 373–398 (1990) · Zbl 0705.90050 |
| [12] | de Silva, A., Abramson, D.: A parallel interior point method and its application to facility location problems. Comput. Optim. Appl. 90(3), 249–273 (1998) · Zbl 0897.90145 |
| [13] | du Merle, O., Vial, J.-Ph.: Proximal-ACCPM, a cutting plane method for column generation and Lagrangian relaxation: application to the p-median problem. Technical report, Logilab, HEC, University of Geneva (2002) |
| [14] | Erlenkotter, D.: A dual-based procedure for uncapacitated facility location. Oper. Res. 26, 992–1009 (1978) · Zbl 0422.90053 · doi:10.1287/opre.26.6.992 |
| [15] | Gao, L.-L., Robinson, E.P.: Uncapacitated facility location: General solution procedure and computational experience. Eur. J. Oper. Res. 76(3), 410–417 (1994) · Zbl 0810.90085 · doi:10.1016/0377-2217(94)90277-1 |
| [16] | Ghosh, D.: Neighborhood search heuristics for the uncapacitated facility location problem. Eur. J. Oper. Res. 150, 150–162 (2003) · Zbl 1023.90524 · doi:10.1016/S0377-2217(02)00504-0 |
| [17] | Goffin, J.-L., Haurie, A., Vial, J.-Ph.: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 37, 284–302 (1992) · Zbl 0762.90050 · doi:10.1287/mnsc.38.2.284 |
| [18] | Goffin, J.-L., Vial, J.-Ph.: Convex nondifferentiable optimization: A survey focussed on the analytic center cutting plane method. Optim. Methods Softw. 179, 805–867 (2002) · Zbl 1065.90060 · doi:10.1080/1055678021000060829a |
| [19] | Guignard, M.: A Lagrangean dual ascent algorithm for simple plant location problems. Eur. J. Oper. Res. 35, 193–200 (1988) · Zbl 0696.90025 · doi:10.1016/0377-2217(88)90029-X |
| [20] | Guignard, M.: Lagrangian relaxation. TOP 11(2), 151–228 (2003) · Zbl 1079.90087 · doi:10.1007/BF02579036 |
| [21] | Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. I, II. Springer, Berlin (1996) |
| [22] | Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2000) · Zbl 0967.49010 |
| [23] | Hoefer, M.: Ufllib (2006). http://www.mpi-inf.mpg.de/departments/d1/projects/benchmarks/UflLib/ |
| [24] | Janacek, J., Buzna, L.: An acceleration of Erlenkotter-Koerkel’s algorithms for the uncapacitated facility location problem. Ann. Oper. Res. 164, 97–109 (2008) · Zbl 1169.90387 · doi:10.1007/s10479-008-0343-0 |
| [25] | Kelley, J.E.: The cutting-plane method for solving convex programs. J. SIAM 8, 703–712 (1960) · Zbl 0098.12104 |
| [26] | Kochetov, Y., Ivanenko, D.: Computationally difficult instances for the uncapacitated facility location problem. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Solvers. Springer, Berlin (2005) |
| [27] | Koerkel, M.: On the exact solution of large-scale simple plant location problems. Eur. J. Oper. Res. 39(2), 157–173 (1989) · Zbl 0673.90032 · doi:10.1016/0377-2217(89)90189-6 |
| [28] | Landete, M., Marin, A.: New facets for the two-stage uncapacitated facility location polytope. Comput. Optim. Appl. 44(3), 487–519 (2009) · Zbl 1187.90177 · doi:10.1007/s10589-008-9165-x |
| [29] | Mirchandani, P., Francis, R.: Discrete Location Theory. Wiley, New York (1990) · Zbl 0718.00021 |
| [30] | Mladenovic, N., Brimberg, J., Hansen, P.: A note on duality gap in the simple plant location. Eur. J. Oper. Res. 174(1), 11–22 (2006) · Zbl 1116.90072 · doi:10.1016/j.ejor.2004.12.022 |
| [31] | Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067 |
| [32] | Resende, M.G.G., Werneck, R.F.: A hybrid multistart heuristic for the uncapacitated facility location problem. Eur. J. Oper. Res. 174(1), 54–68 (2006) · Zbl 1116.90074 · doi:10.1016/j.ejor.2005.02.046 |
| [33] | Sun, M.: Solving uncapacitated facility location problems using tabu search. Comput. Oper. Res. 33, 2563–2589 (2006) · Zbl 1086.90038 · doi:10.1016/j.cor.2005.07.014 |
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.
