  


Solving the bandwidth coloring problem applying constraint and integer programming techniques
Bruno Dias(bruno.diasicomp.ufam.edu.br) Abstract: In this paper, constraint and integer programming formulations are applied to solve Bandwidth Coloring Problem (BCP) and Bandwidth Multicoloring Problem (BMCP). The problems are modeled using distance geometry (DG) approaches, which are then used to construct the constraint programming formulation. The integer programming formulation is based on a previous formulation for the related Minimum Span Frequency Assignment Problem (MSFAP), which is modified in order to reduce its size and computation time. The two exact approaches are implemented with available solvers and applied to wellknown sets of instances from the literature, GEOM and Philadelphialike problems. Using these models, some heuristic solutions from previous works are proven to be optimal, a new upper bound for an instance is given and all optimal solutions for the Philadelphialike problems are presented. A discussion is also made on the performance of constraint and integer programming for each considered coloring problem, and the best approach is suggested for each one of them.In this paper, constraint and integer programming formulations are applied to solve Bandwidth Coloring Problem (BCP) and Bandwidth Multicoloring Problem (BMCP). The problems are modeled using distance geometry (DG) approaches, which are then used to construct the constraint programming formulation. The integer programming formulation is based on a previous formulation for the related Minimum Span Frequency Assignment Problem (MSFAP), which is modified in order to reduce its size and computation time. The two exact approaches are implemented with available solvers and applied to wellknown sets of instances from the literature, GEOM and Philadelphialike problems. Using these models, some heuristic solutions from previous works are proven to be optimal, a new upper bound for an instance is given and all optimal solutions for the Philadelphialike problems are presented. A discussion is also made on the performance of constraint and integer programming for each considered coloring problem, and the best approach is suggested for each one of them. Keywords: bandwidth coloring, channel assignment, distance coloring, graph theory, integer and constraint programming, multicoloring Category 1: Integer Programming Category 2: Optimization Software and Modeling Systems Category 3: Applications  OR and Management Sciences (Telecommunications ) Citation: Institute of Computing  Federal University of Amazonas  Av. Rodrigo Octávio, 6200, Coroado, Campus Universitário, 69077000 Bl. IComp, Setor Norte Manaus  Amazonas  Brazil  Download: [PDF] Entry Submitted: 06/27/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  