Back

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.

, 23 pages

Research Axis

Research application

Publication

, , and
Discrete Applied Mathematics, 261, 229–245, 2019 BibTeX reference