G-2016-112
Integer programming models for the partial directed weighted improper coloring problem
, , and BibTeX reference
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.
Published November 2016 , 23 pages