In this paper, constraint and integer programming techniques are applied to solving bandwidth coloring problems, in the sense of proving optimality or finding better feasible solutions for benchmark instances from the literature. The Bandwidth Coloring Problem (BCP) is a generalization of the classic vertex coloring problem (VCP), where, given a graph, its vertices must be colored such that not only adjacent ones do not share the same color, but also their colors must be separated by a minimum given value. BCP is further generalized to the Bandwidth Multicoloring Problem (BMCP), where each vertex can receive more than one different color, also subject to separation constraints. BMCP is used to model the Minimum Span Channel Assignment Problem (MS-CAP), which arises in the planning of telecommunication networks. Research on algorithmic strategies to solve these problems focus mainly on heuristic approaches and the performance of such methods is tested on artificial and real scenarios benchmarks, such as GEOM, Philadelphia and Helsinki sets. We achieve optimal solutions or provide better upper bounds for these well-known instances, We also compare the effects of multicoloring demands on the performance of each exact solution approach, based on empirical analysis.
Keywords: Bandwidth coloring, channel assignment, integer and constraint programming, graph theory
@article{RO_2021__55_S1_S1949_0,
author = {Dias, Bruno and de Freitas, Rosiane and Maculan, Nelson and Michelon, Philippe},
title = {Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problem},
journal = {RAIRO. Operations Research},
pages = {S1949--S1967},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020065},
mrnumber = {4223096},
zbl = {1472.90070},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020065/}
}
TY - JOUR AU - Dias, Bruno AU - de Freitas, Rosiane AU - Maculan, Nelson AU - Michelon, Philippe TI - Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problem JO - RAIRO. Operations Research PY - 2021 SP - S1949 EP - S1967 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020065/ DO - 10.1051/ro/2020065 LA - en ID - RO_2021__55_S1_S1949_0 ER -
%0 Journal Article %A Dias, Bruno %A de Freitas, Rosiane %A Maculan, Nelson %A Michelon, Philippe %T Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problem %J RAIRO. Operations Research %D 2021 %P S1949-S1967 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020065/ %R 10.1051/ro/2020065 %G en %F RO_2021__55_S1_S1949_0
Dias, Bruno; de Freitas, Rosiane; Maculan, Nelson; Michelon, Philippe. Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problem. RAIRO. Operations Research, Tome 55 (2021), pp. S1949-S1967. doi: 10.1051/ro/2020065
[1] , , and , A survey on the channel assignment problem in wireless networks. Wireless Commun. Mobile Comput. 11 (2011) 583–609. | DOI
[2] , An efficient heuristic algorithm for channel assignment problem in cellular radio networks. IEEE Trans. Veh. Technol. 50 (2001) 1528–1539. | DOI
[3] , On the use of some known methods for -coloring of graphs. Ann. Oper. Res. 41 (1999) 343–358. | Zbl | DOI
[4] , , and , Distance geometry approach for special graph coloring problems. Preprint arXiv:1606.04978 (2016).
[5] , , and , On distance graph coloring problems. Int. Trans. Oper. Res. (2019). DOI: . | DOI | MR | Zbl
[6] , Theoretical models and algorithms for optimizing channel assignment in wireless mobile networks. Master’s thesis, Universidade Federal do Amazonas, Brazil (2014). In Portuguese.
[7] , , and , Solving the bandwidth coloring problem applying constraint and integer programming techniques. Optim. Online (e-print) (2016). Available at http://www.optimization-online.org/DB_HTML/2016/06/5514.html.
[8] and , Tabu search for graph coloring, -coloring and set -colorings, edited by , , and . In: Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization. Springer, New York, NY (1999) 77–92. | MR | Zbl
[9] and , A survey of local search methods for graph coloring. Comput. Oper. Res. 33 (2006) 2547–2562. | MR | Zbl | DOI
[10] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, New York, NY (1979). | MR | Zbl
[11] and , Application of mathematical programming to the fixed channel assignment problem in mobile radio networks. IEE Proc. Commun. 144 (1997) 257–264. | DOI
[12] , , and , Graph coloring approach with new upper bounds for the chromatic number: team building application. RAIRO:OR 52 (2018) 807–818. | MR | Zbl | Numdam | DOI
[13] , Frequency assignment: theory and applications. Proc. IEEE 25 (1980) 1497–1514. | DOI
[14] , Reducibility among combinatorial problems, edited by and . In: Complexity of Computer Computations. Plenum Press, New York, NY (1972) 85–103. | MR | Zbl | DOI
[15] and , Solving the fixed channel assignment problem in cellular communications using an adaptive local search, edited by and . In: Vol. 3616 of 5th International Conference for the Practice and Theory of Automated Timetabling (PATAT 2004). Lecture Notes in Computer Science. Springer, Heidelberg (2005).
[16] , and , A memetic algorithm for channel assignment in wireless fdma systems. Comput. Oper. Res. 34 (2007) 1842–1856. | Zbl | DOI
[17] , Frequency assignment: models and algorithms. Ph.D. thesis, Universiteit Maastricht (1999).
[18] and , Multistart iterated tabu search for bandwidth coloring problem. Comput. Oper. Res. 40 (2013) 1401–1409. | MR | Zbl | DOI
[19] , Polyhedral studies for minimum-span graph labelling with integer distance constraints. Int. Trans. Oper. Res. 14 (2007) 105–121. | MR | Zbl | DOI
[20] and , An evolutionary approach for bandwidth multicoloring problems. Eur. J. Oper. Res. 189 (2008) 638–651. | MR | Zbl | DOI
[21] and , A survey on vertex coloring problems. Int. Trans. Oper. Res. 17 (2010) 1–34. | MR | Zbl | DOI
[22] and , A branch-and-price approach for graph multi-coloring, edited by , , and . In: Vol. 37 of Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series. Springer, New York, NY (2007) 15–29. | Zbl
[23] and , A Branch-and-Cut algorithm for graph coloring. Dis. Appl. Math. 154 (2006) 826–847. | MR | Zbl | DOI
[24] and , Coloring graphs with a general heuristic search engine. In: Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations. Ithaca, NY (2002) 92–99.
[25] , Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing. (1979) 480–489.
[26] , , and . COLOR02/03/04: Graph coloring and its generalizations. In: Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations. Ithaca, NY (2002).
[27] and , Three tabu search methods for the MI-FAP applied to 802.11 networks. RAIRO:OR 42 (2008) 501–514. | MR | Zbl | Numdam | DOI
[28] , and , Consistency checking within local search applied to the frequency assignment with polarization problem. RAIRO:OR 37 (2003) 311–323. | MR | Zbl | Numdam | DOI
Cité par Sources :
