Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Avella, P., Sassano, A., Vasil’ev, I.: Computational study of large-scale p-median problems. Math. Program. 109(1), 89–114 (2007)
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)
Baotic, M.: Matlab interface for CPLEX (2004). http://control.ee.ethz.ch/hybrid/cplexint.php
Barahona, F., Chudak, F.: Near-optimal solutions to large scale facility location problems technical report. Technical Report RC21606, IBM Watson Research Center (1999)
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)
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)
Briant, O., Naddef, D.: The optimal diversity management problem. Oper. Res. 52(4), 515–526 (2004)
Canovas, L., Landete, L., Marin, A.: On the facets of the simple plant location packing polytope. Discrete Appl. Math. 124, 27–53 (2002)
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)
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)
Conn, A.R., Cornuéjols, G.: A projection method for the uncapacitated facility location problem. Math. Program. 46, 373–398 (1990)
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)
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)
Erlenkotter, D.: A dual-based procedure for uncapacitated facility location. Oper. Res. 26, 992–1009 (1978)
Gao, L.-L., Robinson, E.P.: Uncapacitated facility location: General solution procedure and computational experience. Eur. J. Oper. Res. 76(3), 410–417 (1994)
Ghosh, D.: Neighborhood search heuristics for the uncapacitated facility location problem. Eur. J. Oper. Res. 150, 150–162 (2003)
Goffin, J.-L., Haurie, A., Vial, J.-Ph.: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 37, 284–302 (1992)
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)
Guignard, M.: A Lagrangean dual ascent algorithm for simple plant location problems. Eur. J. Oper. Res. 35, 193–200 (1988)
Guignard, M.: Lagrangian relaxation. TOP 11(2), 151–228 (2003)
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. I, II. Springer, Berlin (1996)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2000)
Hoefer, M.: Ufllib (2006). http://www.mpi-inf.mpg.de/departments/d1/projects/benchmarks/UflLib/
Janacek, J., Buzna, L.: An acceleration of Erlenkotter-Koerkel’s algorithms for the uncapacitated facility location problem. Ann. Oper. Res. 164, 97–109 (2008)
Kelley, J.E.: The cutting-plane method for solving convex programs. J. SIAM 8, 703–712 (1960)
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)
Koerkel, M.: On the exact solution of large-scale simple plant location problems. Eur. J. Oper. Res. 39(2), 157–173 (1989)
Landete, M., Marin, A.: New facets for the two-stage uncapacitated facility location polytope. Comput. Optim. Appl. 44(3), 487–519 (2009)
Mirchandani, P., Francis, R.: Discrete Location Theory. Wiley, New York (1990)
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)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
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)
Sun, M.: Solving uncapacitated facility location problems using tabu search. Comput. Oper. Res. 33, 2563–2589 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been partially supported by the Spanish government subsidy MTM2009-14039-C06-03 and by the ‘Comunidad de Madrid’ subsidy S2009/esp-1594.
Rights and permissions
About this article
Cite this article
Beltran-Royo, C., Vial, JP. & Alonso-Ayuso, A. Semi-Lagrangian relaxation applied to the uncapacitated facility location problem. Comput Optim Appl 51, 387–409 (2012). https://doi.org/10.1007/s10589-010-9338-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-010-9338-2