Title: The Robust Weighted Vertex Coloring Problem with Uncertain Data
Speaker: Ram Dahal, PhD candidate, Optimization Research Group
Location and time: B543, Wednesday Oct 28, 12:00pm – 12:50pm.
The vertex coloring problem (VCP) is a classical problem of assigning a color to each vertex of a graph such that no two adjacent vertices have the same color. In the weighted version of classical VCP, the vertices of the graph are assigned a positive weight and the objective is to minimize the sum of the costs of the colors from a feasible coloring. The cost of a color equals the maximum vertex weight among all vertices assigned to the color. WVCP is strongly NP-hard since it generalize the classical VCP. WVCP has several applications in scheduling, timetabling, register allocation, train platforming. In addition, the problem captures the essence of scheduling data transmissions in a time division multiple access (TDMA) wireless network. In our work we consider a much more difficult setting for WVCP called robust WVCP (RWVCP). In the robust problem, the vertex weights are uncertain and only known to lie between given lower and upper bounds. Any particular assignment of values to the uncertain parameters in the allowed ranges is called a scenario. The goal is to find a solution robust to the uncertainty that is, a solution X for which the difference between the cost of X under the worst possible scenario and the cost of the optimal solution for that scenario is minimized. RWVCP is completely open at present. In this talk, we investigate the strength of linear and integer programming techniques in solving robust WVCP. In our apporach, we use Benders decomposition to generate the scenarios of interest but our master problem is a linear program with an exponential number of variables
and it is solved by column generation.