{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T23:44:29Z","timestamp":1749599069109,"version":"3.37.3"},"reference-count":28,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["1391367"],"award-info":[{"award-number":["1391367"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004916","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado do Amazonas","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004916","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"name":"M\u00e9liuz"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,6,17]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1051\/ro\/2020065","type":"journal-article","created":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T08:48:45Z","timestamp":1592556525000},"page":"S1949-S1967","source":"Crossref","is-referenced-by-count":3,"special_numbering":"Supplement","title":["Integer and constraint programming approaches for providing optimality to the bandwidth multicoloring problem"],"prefix":"10.1051","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0517-7895","authenticated-orcid":false,"given":"Bruno","family":"Dias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7608-2052","authenticated-orcid":false,"given":"Rosiane","family":"de Freitas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3897-3356","authenticated-orcid":false,"given":"Nelson","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Michelon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1002\/wcm.898","volume":"11","author":"Audhya","year":"2011","journal-title":"Wireless Commun. Mobile Comput"},{"key":"R2","doi-asserted-by":"crossref","first-page":"1528","DOI":"10.1109\/25.966583","volume":"50","author":"Chakraborty","year":"2001","journal-title":"IEEE Trans. Veh. Technol"},{"key":"R3","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02023000","volume":"41","author":"Costa","year":"1999","journal-title":"Ann. Oper. Res"},{"unstructured":"de Freitas R., Dias B., Maculan N. and Szwarcfiter J., Distance geometry approach for special graph coloring problems. Preprint arXiv:1606.04978 (2016).","key":"R4"},{"doi-asserted-by":"crossref","unstructured":"de Freitas R., Dias B., Maculan N. and Szwarcfiter J., On distance graph coloring problems. Int. Trans. Oper. Res. (2019). DOI: 10.1111\/itor.12626.","key":"R5","DOI":"10.1111\/itor.12626"},{"unstructured":"Dias B., Theoretical models and algorithms for optimizing channel assignment in wireless mobile networks. Master\u2019s thesis, Universidade Federal do Amazonas, Brazil (2014). In Portuguese.","key":"R6"},{"unstructured":"Dias B., de Freitas R., Maculan N. and Michelon P., 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.","key":"R7"},{"unstructured":"Dorne R. and Hao J., Tabu search for graph coloring, T-coloring and set T-colorings, edited by Voss S., Martello S., Osman I.H. and Roucairol C.. In: Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization. Springer, New York, NY (1999) 77\u201392.","key":"R8"},{"key":"R9","doi-asserted-by":"crossref","first-page":"2547","DOI":"10.1016\/j.cor.2005.07.028","volume":"33","author":"Galinier","year":"2006","journal-title":"Comput. Oper. Res"},{"unstructured":"Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, New York, NY (1979).","key":"R10"},{"key":"R11","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1049\/ip-com:19971249","volume":"144","author":"Giortzis","year":"1997","journal-title":"IEE Proc. Commun"},{"key":"R12","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1051\/ro\/2016069","volume":"52","author":"Gueham","year":"2018","journal-title":"RAIRO:OR"},{"key":"R13","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"25","author":"Hale","year":"1980","journal-title":"Proc. IEEE"},{"doi-asserted-by":"crossref","unstructured":"Karp R., Reducibility among combinatorial problems, edited by Miller R.E. and Thatcher J.W.. In: Complexity of Computer Computations. Plenum Press, New York, NY (1972) 85\u2013103.","key":"R14","DOI":"10.1007\/978-1-4684-2001-2_9"},{"unstructured":"Kendall G. and Mohamad M., Solving the fixed channel assignment problem in cellular communications using an adaptive local search, edited by Burke E. and Trick M.. 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).","key":"R15"},{"key":"R16","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1016\/j.cor.2005.05.038","volume":"34","author":"Kim","year":"2007","journal-title":"Comput. Oper. Res"},{"unstructured":"Koster A., Frequency assignment: models and algorithms. Ph.D. thesis, Universiteit Maastricht (1999).","key":"R17"},{"key":"R18","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1016\/j.cor.2012.09.003","volume":"40","author":"Lai","year":"2013","journal-title":"Comput. Oper. Res"},{"key":"R19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1111\/j.1475-3995.2007.00577.x","volume":"14","author":"Mak","year":"2007","journal-title":"Int. Trans. Oper. Res"},{"key":"R20","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1016\/j.ejor.2006.09.095","volume":"189","author":"Malaguti","year":"2008","journal-title":"Eur. J. Oper. Res"},{"key":"R21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"Malaguti","year":"2010","journal-title":"Int. Trans. Oper. Res"},{"unstructured":"Mehrotra A. and Trick M., A branch-and-price approach for graph multi-coloring, edited by Baker E.K., Joseph A., Mehrotra A. and Trick M.. 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\u201329.","key":"R22"},{"key":"R23","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"M\u00e9ndez-D\u00edaz","year":"2006","journal-title":"Dis. Appl. Math"},{"unstructured":"Phan V. and Skiena S., Coloring graphs with a general heuristic search engine. In: Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations. Ithaca, NY (2002) 92\u201399.","key":"R24"},{"unstructured":"Saxe J.B., Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing. (1979) 480\u2013489.","key":"R25"},{"unstructured":"Trick M., Mehrotra A., and Johnson D.. COLOR02\/03\/04: Graph coloring and its generalizations. In: Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations. Ithaca, NY (2002).","key":"R26"},{"key":"R27","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1051\/ro:2008026","volume":"42","author":"Varone","year":"2008","journal-title":"RAIRO:OR"},{"key":"R28","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1051\/ro:2004004","volume":"37","author":"Vasquez","year":"2003","journal-title":"RAIRO:OR"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020065\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T10:05:14Z","timestamp":1614679514000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":28,"alternative-id":["ro190001"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2020065","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021]]}}}