Abstract
Given an optimization problem, combining knowledge from both (i) structural or algorithmic known results and (ii) new solving techniques, helps gain insight and knowledge on the aforementioned problem by tightening the gap between lower and upper bounds on the sought optimal value. Additionally, this gain may be further improved by iterating (i) and (ii) until a fixed point is reached.
In this paper, we illustrate the above through the classical Cyclic Bandwidth problem, an optimization problem which takes as input an undirected graph \(G=(V,E)\) with \(|V|=n\), and asks for a labeling \(\varphi \) of V in which every vertex v takes a unique value \(\varphi (v)\in [1;n]\), in such a way that \(B_c(G,\varphi )=\max \{\min _{uv\in E(G)}\{|\varphi (u)-\varphi (v)|,n-|\varphi (u)-\varphi (v)|\}\}\), called the cyclic bandwidth of G, is minimized.
Using the classic benchmark from the Harwell-Boeing sparse matrix collection introduced in [16], we show how to combine (i) previous results from the Cyclic Bandwidth literature, and (ii) new solving techniques, which we first present, and then implement, starting from the best results obtained in step (i). We show that this process allows us to determine the optimal cyclic bandwidth value for half of the instances of our benchmark, and improves the best known bounds for a large number of the remaining instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
A global constraint provides some abstractions to improve expressiveness, but also are treated more efficiently by the solver using some dedicated algorithms.
References
Apt, K.R., Monfroy, É.: Constraint programming viewed as rule-based programming. Theory Pract. Log. Program. 1(6), 713–750 (2001)
Chinn, P.Z., Chvátalová, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - a survey. J. Graph Theor. 6(3), 223–254 (1982)
Chung, F.R.: Labelings of graphs. Sel. Top. Graph Theor. 3, 151–168 (1988)
Déprés, H., Fertin, G., Monfroy, E.: Improved lower bounds for the cyclic bandwidth problem. In: Paszynski, M., Kranzlmüller, D., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) ICCS 2021. LNCS, vol. 12742, pp. 555–569. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77961-0_45
Harary, F., Manvel, B.: On the number of cycles in a graph. Matematickỳ časopis 21(1), 55–63 (1971)
Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. 12(1), 131–135 (1964)
van Hoeve, W.J.: The all different constraint: a survey. CoRR cs.PL/0105015 (2001). https://arxiv.org/abs/cs/0105015
Hromkovič, J., Müller, V., Sýkora, O., Vrťo, I.: On embedding interconnection networks into rings of processors. In: Etiemble, D., Syre, J.-C. (eds.) PARLE 1992. LNCS, vol. 605, pp. 51–62. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55599-4_80
Lam, P.C.B., Shiu, W.C., Chan, W.H.: Characterization of graphs with equal bandwidth and cyclic bandwidth. Discret. Math. 242(1–3), 283–289 (2002)
Lecoutre, C.: Optimization of simple tabular reduction for table constraints. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 128–143. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85958-1_9
Leung, J.Y., Vornberger, O., Witthoff, J.D.: On some variants of the bandwidth minimization problem. SIAM J. Comput. 13(3), 650–667 (1984)
Lin, Y.: A level structure approach on the bandwidth problem for special graphs. Ann. N. Y. Acad. Sci. 576(1), 344–357 (1989)
Lin, Y.: The cyclic bandwidth problem. Syst. Sci. Math. Sci. 7 (1994)
Lin, Y.: Minimum bandwidth problem for embedding graphs in cycles. Networks 29(3), 135–140 (1997)
Martí, R., Campos, V., Piñana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Eur. J. Oper. Res. 186, 513–528 (2008)
Martí, R., Laguna, M., Glover, F., Campos, V.: Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. 135, 450–459 (2001)
Mladenovic, N., Urosevic, D., Pérez-Brito, D., García-González, C.: Variable neighbourhood search for bandwidth reduction. Eur. J. Oper. Res. 200(1), 14–27 (2010)
Pop, P., Matei, O., Comes, C.A.: Reducing the bandwidth of a sparse matrix with a genetic algorithm. Optimization 63(12), 1851–1876 (2014)
Ren, J., Hao, J., Rodriguez-Tello, E.: An iterated three-phase search approach for solving the cyclic bandwidth problem. IEEE Access 7, 98436–98452 (2019)
Ren, J., Hao, J.K., Rodriguez-Tello, E., Li, L., He, K.: A new iterated local search algorithm for the cyclic bandwidth problem. Knowl.-Based Syst. 203, 106136 (2020)
Rodriguez-Tello, E., Hao, J.K., Torres-Jimenez, J.: An improved simulated annealing algorithm for bandwidth minimization. Eur. J. Oper. Res. 185(3), 1319–1335 (2008)
Rodriguez-Tello, E., Romero-Monsivais, H., Ramírez-Torres, G., Lardeux, F.: Tabu search for the cyclic bandwidth problem. Comput. Oper. Res. 57, 17–32 (2015)
Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2. Elsevier (2006)
XCSP3 Team: PyCSP\(^{3}\) v2.2 (2023). https://www.pycsp.org/
Zhou, S.: Bounding the bandwidths for graphs. Theoret. Comput. Sci. 249(2), 357–368 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fertin, G., Monfroy, E., Vasconcellos-Gaete, C. (2024). Best of Both Worlds: Solving the Cyclic Bandwidth Problem by Combining Pre-existing Knowledge and Constraint Programming Techniques. In: Franco, L., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds) Computational Science – ICCS 2024. ICCS 2024. Lecture Notes in Computer Science, vol 14836. Springer, Cham. https://doi.org/10.1007/978-3-031-63775-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-63775-9_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-63774-2
Online ISBN: 978-3-031-63775-9
eBook Packages: Computer ScienceComputer Science (R0)