Solving a multicoloring problem with overlaps using integer programming

被引：4

作者：

Mendez-Diaz, Isabel ^{[1
]}

Zabala, Paula ^{[1
]}

机构：

[1] Univ Buenos Aires, Consejo Nacl Invest Cient & Tecn, Dept Computac, FCEyN, RA-1053 Buenos Aires, DF, Argentina

来源：

DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 04期

关键词：

Graph multicoloring; Integer programming; Branch-and-Cut;

D O I：

10.1016/j.dam.2009.05.007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：349 / 354

页数：6

共 11 条

[1] Models and solution techniques for frequency assignment problems
Aardal, Karen I.
van Hoesel, Stan P. M.
Koster, Arie M. C. A.
Mannino, Carlo
Sassano, Antonio
[J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (04): : 261 - 317
[2] Using integer programming to solve the train-platforming problem
Billionnet, A
[J]. TRANSPORTATION SCIENCE, 2003, 37 (02) : 213 - 222
[3] Halldórsson MM, 2004, LECT NOTES COMPUT SC, V3153, P25
[4] HANSEN P, 2005, G200576 GERAD
[5] Jensen T., 1995, Graph Coloring Problems, P115
[6] JOHNSON DS, 2008, DISCRETE APPL MATH, P156
[7] On a binary-encoded ILP Coloring formulation
Lee, Jon
Margot, Francois
[J]. INFORMS JOURNAL ON COMPUTING, 2007, 19 (03) : 406 - 415
[8] Mehrotra A., 1996, INFORMS Journal on Computing, V8, P344, DOI 10.1287/ijoc.8.4.344
[9] Mehrotra A, 2007, OPER RES COMPUT SCI, V37, P15
[10] A Branch-and-Cut algorithm for Graph Coloring
Méndez-Díaz, I
Zabala, P
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) : 826 - 847

← 1 2 →