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 θ
-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/θ
, 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 θ
and an integer k
, the Partial Directed Weigthed Improper Coloring Problem ((θ,k)
-PDWICP) is to
determine the order of the largest induced subgraph G′
of G
such that G′
admits a θ
-improper k
-coloring. The (θ,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 NP
-hard problem to optimality. A polynomial-time computable upper bound inspired by the Lovász ϑ(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