A column generation based algorithm for the robust graph coloring problem

详细信息    查看全文

• 作者：Birol Yü ; ceoğlu^a ; ¹ ; Gü ; venç ; Şahin^b ; ^{guvencs@sabanciuniv.edu} ; Stan P.M. van Hoesel^c
• 关键词：Robust graph coloring ; Representatives formulation ; Set-covering formulation ; Column generation ; Reduced cost fixing
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：340-352
• 全文大小：449 K
• 卷排序：217

文摘

Given an undirected simple graph GG, an integer kk, and a cost cijcij for each pair of non-adjacent vertices in GG, a robust coloring of GG is the assignment of kk colors to vertices such that adjacent vertices get different colors and the total penalty of the pairs of vertices having the same color is minimum. The problem has applications in fields such as timetabling and scheduling. We present a new formulation for the problem, which extends an existing formulation for the graph coloring problem. We also discuss a column generation based solution method. We report computational study on the performance of alternative formulations and the column generation method.