×

A comparison of integer programming models for the partial directed weighted improper coloring problem. (English) Zbl 1410.05077

Summary: 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 \(\frac{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 weighted improper coloring problem (\((\theta, k)\)-PDWICP) is to determine the order of the largest induced subgraph \(G^\prime\) of \(G\) such that \(G^\prime\) 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 clearly show that the latter is much more effective than branch-and-cut-based methods.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C22 Signed and weighted graphs
05C15 Coloring of graphs and hypergraphs

Software:

DIP; DipPy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Araujo, J.; Bermond, J. C.; Giroire, F.; Havet, F.; Mazauric, D.; Modrzejewski, R., Weighted improper colouring, (Proceedings of the 22nd international conference on Combinatorial Algorithms. Proceedings of the 22nd international conference on Combinatorial Algorithms, IWOCA’11 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 1-18 · Zbl 1314.05058
[2] Archetti, C.; Bianchessi, N.; Hertz, A.; Colombet, A.; Gagnon, F., Directed weighted improper coloring for cellular channel allocation, Discrete Appl. Math., 182, 46-60 (2015) · Zbl 1306.05049
[3] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.; Vance, P. H., Branch-and-Price: column generation for solving huge integer programs, Oper. Res., 46, 3, 316-329 (1998) · Zbl 0979.90092
[4] Brélaz, D., New methods to color the vertices of a graph, Commun. ACM, 22, 4, 251-256 (1979) · Zbl 0394.05022
[5] Computational infrastructure for operations research..; Computational infrastructure for operations research..
[6] Galati, M.; Ralphs, T., DIP: a framework for decomposition in integer programming, Tech. Rep. (2015), COR@L Laboratory, Lehigh University
[7] Hertz, A.; Montagné, R.; Gagnon, F., Constructive algorithms for the partial directed weighted improper coloring problem, J. Graph Algorithms Appl., 20, 2, 159-188 (2016) · Zbl 1331.05208
[8] Joncour, C.; Michel, S.; Sadykov, R.; Sverdlov, D.; Vanderbeck, F., Column generation based primal heuristics, Electron. Notes Discrete Math., 36 (2010) · Zbl 1237.90263
[9] Kaparis, K.; Letchford, A. N., Separation algorithms for 0-1 knapsack polytopes, Math. Program., 124, 1-2, 69-91 (2010) · Zbl 1198.90297
[10] Leighton, F. T., A graph coloring algorithm for large scheduling problems, J. Res. Natl. Bur. Stand., 84, 6, 489-506 (1979) · Zbl 0437.68021
[11] Lovász, L., On decomposition of graphs, Stud. Sci. Math. Hung., 1, 238-273 (1966) · Zbl 0151.33401
[12] Lovász, L., On the shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021
[13] Mehrotra, A.; Trick, M. A., A column generation approach for graph coloring, INFORMS J. Comput., 8, 4, 344-354 (1996) · Zbl 0884.90144
[14] Narasimhan, G., The maximum k-colorable subgraph problem (1989), University of Wisconsin: University of Wisconsin Madison, (Ph.D. dissertation)
[15] O’Sullivan, M.; Lim, Q.; Walker, C.; Dunning, I.; Mitchell, S., Dippy: a simplified interface for advanced mixed-integer programming, Tech. Rep. (2012), University of Auckland, School of Engineering
[16] Rebennack, S., Stable set problem: branch & cut algorithms, (Encyclopedia of Optimization (2009), Springer), 3676-3688
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.