G-2016-112
Integer programming models for the partial directed weighted improper coloring problem
, et référence BibTeX
Étant donné un graphe \(G\)
complet, orienté, avec des poids sur les sommets et les arcs,
une \(k\)
-coloration \(\theta\)
-impropre de \(G\)
est une affectation d'au plus \(k\)
couleurs
aux sommets de \(G\)
de telle sorte que le poids de chaque sommet \(v\)
soit au moins
aussi grand, par un facteur \(\frac{1}{\theta}\)
, que la somme des poids sur les arcs
\((u,v)\)
qui entrent en \(v\)
, avec la couleur de \(u\)
égale à celle de \(v\)
. Pour un nombre réel \(\theta\)
et un entier \(k\)
, le problème de la coloration partielle d'un
graphe orienté pondéré (\((\theta,k)\)
-PDWICP) est de déterminer la taille du plus grand
sous-graphe induit \(G'\)
de \(G\)
tel que \(G'\)
admet une \(k\)
-coloration \(\theta\)
-
impropre. Le \((\theta,k)\)
-PDWICP est un modèle naturel lorsqu'on résout des problèmes
d'affectation de fréquences, et que l'objectif est de maximiser le nombre d'utilisateurs qui
communiquent simultanément dans un réseau sans fil. Dans cet article, nous comparons
des approches de programmation linéaire en nombres entiers pour résoudre ce problème
NP-dur. Une borne supérieure, calculable en temps polynomial, et inspirée de la fonction
de Lovász \(\vartheta(G)\)
, ainsi que des inégalités valides basées sur le problème du sac
à dos et celui du "set packing", sont combinées dans une procédure de type branch-and-
bound. Des comparaisons sont faites avec une approche branch-and-price.
Paru en novembre 2016 , 23 pages