Group for Research in Decision Analysis

# Integer programming models for the partial directed weighted improper coloring problem

## Alain Hertz, Romain Montagné, and François Gagnon

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