-

 

 

 




Optimization Online





 

Solving the bandwidth coloring problem applying constraint and integer programming techniques

Bruno Dias(bruno.dias***at***icomp.ufam.edu.br)
Rosiane de Freitas(rosiane***at***icomp.ufam.edu.br)
Nelson Maculan(maculan***at***cos.ufrj.br)
Philippe Michelon(philippe.michelon***at***univ-avignon.fr )

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 (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.

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, 69077-000 Bl. IComp, Setor Norte Manaus - Amazonas - Brazil ---

Download: [PDF]

Entry Submitted: 06/27/2016
Entry Accepted: 06/28/2016
Entry Last Modified: 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
Mathematical Optimization Society