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 (MS-FAP), which is modified in order to reduce its size and computation time. The two exact approaches are implemented with available solvers and applied to well-known sets of instances from the literature, GEOM and Philadelphia-like 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 Philadelphia-like 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 (MS-FAP), which is modified in order to reduce its size and computation time. The two exact approaches are implemented with available solvers and applied to well-known sets of instances from the literature, GEOM and Philadelphia-like 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 Philadelphia-like 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.
Citation
Institute of Computing - Federal University of Amazonas --- Av. Rodrigo Octávio, 6200, Coroado, Campus Universitário, 69077-000 Bl. IComp, Setor Norte Manaus - Amazonas - Brazil ---
Article
View Solving the bandwidth coloring problem applying constraint and integer programming techniques