Group for Research in Decision Analysis

G-2016-112

Integer programming models for the partial directed weighted improper coloring problem

, , and

Given a complete directed graph \(G\) with weights on the vertices and on the arcs, a \(\theta\)-improper \(k\)-coloring of \(G\) is an assignment of at most \(k\) different colors to the vertices of \(G\) such that the weight of every vertex \(v\) is greater, by a given factor \({1}/{\theta}\), than the sum of the weights on the arcs \((u,v)\) entering \(v\), with the tail \(u\) of the same color as \(v\). For a given real number \(\theta\) and an integer \(k\), the Partial Directed Weigthed Improper Coloring Problem (\((\theta,k)\)-PDWICP) is to determine the order of the largest induced subgraph \(G'\) of \(G\) such that \(G'\) admits a \(\theta\)-improper \(k\)-coloring. The \((\theta,k)\)-PDWICP appears as a natural model when solving channel assignment problems that aim to maximize the number of simultaneously communicating mobiles in a wireless network. In this paper, we compare integer programming approaches to solve this \(\mathcal{NP}\)-hard problem to optimality. A polynomial-time computable upper bound inspired by the Lovász \(\vartheta(G)\) function, and valid inequalities based on the knapsack and set-packing problems are embedded in a branch-and-bound procedure. Comparisons with a branch-and-price scheme are reported.

, 23 pages