Groupe d’études et de recherche en analyse des décisions

G-2016-112

Integer programming models for the partial directed weighted improper coloring problem

, et

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

, 23 pages