Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph G representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of G minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results. © 2011 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
Autor:Delle Donne, D.; Marenco, J.
Filiación:Computer Science Department, FCEN, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Sciences Institute, National University of General Sarmiento, J.M. Gutiérrez y J. Verdi, Malvinas Argentinas, (1613) Buenos Aires, Argentina
Palabras clave:Adjacent colors; Frequency assignment; Integer programming; Adjacent channels; Adjacent colors; Branch-and-cut algorithms; Computational results; Frequency assignments; Frequency channels; Integer programming models; Interference graphs; Potential interferences; Valid inequality; Vertex coloring; Vertex coloring problems; Wireless communication network; Algorithms; Antennas; Cochannel interference; Combinatorial optimization; Computer programming; Graph theory; Wireless networks; Wireless telecommunication systems; Integer programming
Año:2011
Volumen:8
Número:4
Página de inicio:540
Página de fin:554
DOI: http://dx.doi.org/10.1016/j.disopt.2011.05.003
Título revista:Discrete Optimization
Título revista abreviado:Discrete Optim.
ISSN:15725286
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15725286_v8_n4_p540_DelleDonne.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v8_n4_p540_DelleDonne

Referencias:

  • Eisenbltter, A., (2001) Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds, , Ph.D. Thesis, Technische Universitt Berlin
  • Eisenbltter, A., Assigning frequencies in GSM networks (2003) Operations Research Proceedings, 2002, pp. 33-40
  • Grötschel, M., (2000) Frequency Assignment in Mobile Phone Systems, 1974 VOL., pp. 81-86. , LNCS
  • Luna, F., Alba, E., Nebro, A., Pedraza, S., (2007) Evolutionary Algorithms for Real-World Instances of the Automatic Frequency Planning Problem in GSM Networks, 4446 VOL., pp. 108-120. , Lecture Notes in Computer Science
  • Aardal, K., Van Hoesel, S., Koster, A., Mannino, C., Sassano, A., Models and solution techniques for frequency assignment problems (2007) Annals of Operation Research, 153, pp. 79-129
  • Eisenbltter, A., The Semidefinite Relaxation of the k-Partition Polytope is Strong (2002) Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 273-290
  • Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discrete Applied Mathematics, 154 (5), pp. 826-847
  • Mendez-Diaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Applied Mathematics, 156 (2), pp. 159-179. , DOI 10.1016/j.dam.2006.07.010, PII S0166218X0700100X, Computational Methods for Graph Coloring and it's Generalization
  • R. Borndörfer, The Orientation Model for Frequency Assignment Problems (1998) ZIB-Berlin TR 98-01
  • Campêlo, M., Corrêa, R., Frota, Y., Cliques, holes and the vertex coloring polytope (2004) Information Processing Letters, 89 (4), pp. 159-164
  • Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS Journal on Computing, 8 (4), pp. 344-354
  • Hemazro, T.D., Jaumard, B., Marcotte, O., A column generation and branch-and-cut algorithm for the channel assignment problem (2008) Computers and Operations Research, 35 (4), pp. 1204-1226. , DOI 10.1016/j.cor.2006.07.012, PII S0305054806001596
  • Jaumard, B., Marcotte, O., Meyer, C., Vovor, T., Comparison of column generation models for channel assignment in cellular networks (2001) Discrete Applied Mathematics, 112 (1-3), pp. 217-240. , DOI 10.1016/S0166-218X(00)00317-6, PII S0166218X00003176
  • Delle Donne, D., (2009) A Branch-and-cut Algorithm for A Frequency Assignment Problem in Celular Phones Networks, , Graduate Thesis, University of Buenos Aires
  • Delle Donne, D., Marenco, J., (2010) Facets of the Minimum-adjacency Vertex Coloring Polytope, Technical Report, , http://www.optimization-online.org/DB_HTML/2010/10/2750.html, National University of General Sarmiento
  • Eisenbltter, A., Koster, A., (2009) FAPWeb A Frequency Assignment Website, , http://fap.zib.de
  • Jnger, M., Thienel, S., The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization (2000) Software Practice & Experience, 30 (11), pp. 1325-1352
  • (2009) IBM ILOG, User's Manual for CPLEX

Citas:

---------- APA ----------
Delle Donne, D. & Marenco, J. (2011) . A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem. Discrete Optimization, 8(4), 540-554.
http://dx.doi.org/10.1016/j.disopt.2011.05.003
---------- CHICAGO ----------
Delle Donne, D., Marenco, J. "A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem" . Discrete Optimization 8, no. 4 (2011) : 540-554.
http://dx.doi.org/10.1016/j.disopt.2011.05.003
---------- MLA ----------
Delle Donne, D., Marenco, J. "A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem" . Discrete Optimization, vol. 8, no. 4, 2011, pp. 540-554.
http://dx.doi.org/10.1016/j.disopt.2011.05.003
---------- VANCOUVER ----------
Delle Donne, D., Marenco, J. A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem. Discrete Optim. 2011;8(4):540-554.
http://dx.doi.org/10.1016/j.disopt.2011.05.003