### G-2016-112

# 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.

Published **November 2016**
,
23 pages