Abstract
In this paper, we address the optimization problem arising in some practical applications in which we want to maximize the minimum difference between the labels of adjacent elements. For example, in the context of location models, the elements can represent sensitive facilities or chemicals and their labels locations, and the objective is to locate (label) them in a way that avoids placing some of them too close together (since it can be risky). This optimization problem is referred to as the antibandwidth maximization problem (AMP) and, modeled in terms of graphs, consists of labeling the vertices with different integers or labels such that the minimum difference between the labels of adjacent vertices is maximized. This optimization problem is the dual of the well-known bandwidth problem and it is also known as the separation problem or directly as the dual bandwidth problem. In this paper, we first review the previous methods for the AMP and then propose a heuristic algorithm based on the variable neighborhood search methodology to obtain high quality solutions. One of our neighborhoods implements ejection chains which have been successfully applied in the context of tabu search. Our extensive experimentation with 236 previously reported instances shows that the proposed procedure outperforms existing methods in terms of solution quality.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in GRASP: An experimental investigation. J. Heuristics 8, 343–373 (2002)
Bansal, R., Srivastava, K.: Memetic algorithm for the antibandwidth maximization problem. J. Heuristics 17, 39–60 (2011)
Burkard, R.E., Donnani, H., Lin, Y., Rote, G.: The obnoxious center problem on a tree. SIAM J. Discret. Math. 14(4), 498–590 (2001)
Cappanera, P.: A survey on obnoxious facility location problems. Technical Report TR-99-11, Dipartimento di Informatica, Università di Pisa (1999)
Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. J. ACM Comput. Surv. 34(3), 313–356 (2002)
Dobrev, S., Královic, R., Pardubská, D., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of Hamming graphs. Electron. Notes Discret. Math. 34, 295–300 (2009)
Duarte, A., Martí, R., Resende, M.G.C., Silva, R.M.A.: GRASP with path relinking heuristics for the antibandwidth problem. Networks 58(3), 171–189 (2011)
Duarte, A., Escudero, L.F., Martí, R., Mladenovic, N., Pantrigo, J.J., Sánchez-Oro, J.: Variable neighborhood search for the vertex separation problem. Comput. Oper. Res. 39(12), 3247–3255 (2012)
Glover, F., Laguna, M.: Tabu Search. Kluwer, Norwell (1997)
Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68, 1497–1514 (1980)
Hansen, P., Mladenovic, N., Brimberg, J., Moreno-Pérez, J.A.: Variable neighborhood search. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, 2nd edn, pp. 61–86. Springer, Heidelberg (2010)
Harwell-Boeing: http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/ (2011)
Leung, J.Y.-T., Vornberger, O., Witthoff, J.D.: On some variants of the bandwidth minimization problem. SIAM J. Comput. 13, 650–667 (1984)
Martí, R., Duarte, A., Laguna, M.: Advanced scatter search for the max-cut problem. INFORMS J. Comput. 21(1), 26–38 (2009)
Miller, Z., Pritikin, D.: On the separation number of a graph. Networks 19, 651–666 (1989)
Pantrigo, J.J., Martí, R., Duarte, A., Pardo, E.G.: Scatter search for the cutwidth minimization problem. Ann. Oper. Res. 199(1), 285–304 (2012)
Piñana, E., Plana, I., Campos, V., Martí, R.: GRASP and path relinking for the matrix bandwidth minimization. Eur. J. Oper. Res. 153, 200–210 (2004)
Raspaud, A., Schröder, H., Sykora, O., Török, L., Vrt’o, I.: Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discret. Math. 309, 3541–3552 (2009)
Rego, C.: Node ejection chains for the vehicle routing problem: sequential and parallel algorithms. Parallel Comput. 27(3), 201–222 (2001)
Resende, M., Martí, R., Gallego, M., Duarte, A.: GRASP and path relinking for the max-min diversity problem. Comput. Oper. Res. 37, 498–508 (2010)
Rodriguez-Tello, E., Jin-Kao, H., Torres-Jimenez, J.: An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput. Oper. Res. 35(10), 3331–3346 (2008)
Török, L., Vrt’o, I.: Antibandwidth of 3-dimensional meshes. Electron. Notes Discret. Math. 28, 161–167 (2007)
Yixun, L., Jinjiang, Y.: The dual bandwidth problem for graphs. J. Zhengzhou Univ. 35, 1–5 (2003)
Wang, X., Wu, X., Dumitrescu, S.: On explicit formulas for bandwidth and antibandwidth of hypercubes. Discret. Appl. Math. 157(8), 1947–1952 (2009)
Acknowledgements
This research has been partially supported by the Ministerio de Ciencia e Innovación of Spain within the OPTSICOM project (http://www.optsicom.es/) with grant codes TIN2008-05854, TIN2009-07516, TIN2012-35632, and P08-TIC-4173.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Tables 6, 7 and 8 report the comparison of the state-of-the-art methods over the set of instances with unknown optimum. We consider a time limit of 150 s per instance. Each table shows for each instance the best known value, Best val., the tightest upper bound (Yixun and Jinjiang 2003), UB, the relative deviation (in percentage) between the best known value and the upper bound, Dev, and finally the heuristic method (or methods) achieving these results.
Rights and permissions
About this article
Cite this article
Lozano, M., Duarte, A., Gortázar, F. et al. Variable neighborhood search with ejection chains for the antibandwidth problem. J Heuristics 18, 919–938 (2012). https://doi.org/10.1007/s10732-012-9213-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-012-9213-7