Artículo
Méndez-Díaz, I.; Zabala, P. "Solving a multicoloring problem with overlaps using integer programming" (2010) Discrete Applied Mathematics. 158(4):349-354
Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances. © 2009 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | Solving a multicoloring problem with overlaps using integer programming |
| Autor: | Méndez-Díaz, I.; Zabala, P. |
| Filiación: | Departamento de Computación, FCEyN - Universidad de Buenos Aires, Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina |
| Palabras clave: | Branch-and-Cut; Graph multicoloring; Integer programming; Branch-and-cut; Branch-and-cut algorithms; Graph multicoloring; Integer programming formulations; Multicoloring; Polytopes; Random instance; Valid inequality; Dynamic programming; Heuristic methods; Integer programming |
| Año: | 2010 |
| Volumen: | 158 |
| Número: | 4 |
| Página de inicio: | 349 |
| Página de fin: | 354 |
| DOI: | http://dx.doi.org/10.1016/j.dam.2009.05.007 |
| Título revista: | Discrete Applied Mathematics |
| Título revista abreviado: | Discrete Appl Math |
| ISSN: | 0166218X |
| CODEN: | DAMAD |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v158_n4_p349_MendezDiaz.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n4_p349_MendezDiaz |
Referencias:
- Aardal, K., van Hoesel, S., Koster, A., Mannino, C., Sassano, A., Models and solution techniques for frequency assignment problems (2003) 4OR, 1 (4), pp. 261-317
- Billionnet, A., Using integer programming to solve the train-platforming problem (2003) Transportation Science, 37 (2), pp. 213-222
- Halldórsson, M., Kortsarz, G., (2004) Lecture Notes in Computer Science, 315, pp. 25-41
- Hansen, P., Labbé, M., Schindl, D., Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results (2005), Tech. Rep. No. G-2005-76, Montreal, Canada: GERAD; Jensen, T., Toft, B., (1995) Graph Coloring Problems, , Wiley-Interscience, New York
- Johnson, D.S., Mehrotra, A., Trick, M.A., Special issue on computational methods for graph coloring and its generalizations (2008) Discrete Applied Mathematics, 156
- Lee, J., Margot, F., On a binary-encoded ILP coloring formulation (2007) INFORMS Journal on Computing, 19 (3), pp. 406-415
- Méndez-Díaz, I., Zabala, P., A Branch-and-Cut algorithm for graph coloring (2006) Discrete Applied Mathematics, 154 (5), pp. 826-847
- Mehrotra, A., Trick, M., A column generation approach for Graph Coloring (1996) INFORMS Journal on Computing, 8, pp. 344-354
- Mehrotra, A., Trick, M., A branch and price approach for graph multicoloring (2007) Springer Operations Research/Computer Science Interfaces Series, 37, pp. 15-30. , Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies
- Narayan, L., Channel assignment and graph multicoloring (2002) Wiley Series On Parallel And Distributed Computing, pp. 71-94. , Handbook of Wireless Networks and Mobile Computing
Citas:
---------- APA ----------
Méndez-Díaz, I. & Zabala, P. (2010) . Solving a multicoloring problem with overlaps using integer programming. Discrete Applied Mathematics, 158(4), 349-354.http://dx.doi.org/10.1016/j.dam.2009.05.007
---------- CHICAGO ----------
Méndez-Díaz, I., Zabala, P. "Solving a multicoloring problem with overlaps using integer programming" . Discrete Applied Mathematics 158, no. 4 (2010) : 349-354.http://dx.doi.org/10.1016/j.dam.2009.05.007
---------- MLA ----------
Méndez-Díaz, I., Zabala, P. "Solving a multicoloring problem with overlaps using integer programming" . Discrete Applied Mathematics, vol. 158, no. 4, 2010, pp. 349-354.http://dx.doi.org/10.1016/j.dam.2009.05.007
---------- VANCOUVER ----------
Méndez-Díaz, I., Zabala, P. Solving a multicoloring problem with overlaps using integer programming. Discrete Appl Math. 2010;158(4):349-354.http://dx.doi.org/10.1016/j.dam.2009.05.007
