A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.

A branch-and-price algorithm for the Minimum Sum Coloring Problem / Delle Donne, D.; Furini, F.; Malaguti, E.; Wolfler Calvo, R.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 303(2021), pp. 39-56. [10.1016/j.dam.2020.08.031]

### A branch-and-price algorithm for the Minimum Sum Coloring Problem

#### Abstract

A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the colors assigned to the vertices. We propose the first branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. We present extensive computational experiments, on synthetic and benchmark DIMACS graphs from the literature, to compare the performance of our newly developed branch-and-price algorithm against three compact IP formulations. On synthetic graphs, our algorithm outperforms the compact formulations in terms of: (i) number of solved instances, (ii) running times and (iii) exit gaps obtained when optimality is not achieved. For the DIMACS instances, our algorithm is competitive with the best compact formulation and provides very strong dual bounds.
##### Scheda breve Scheda completa
File allegati a questo prodotto
File
DelleDonne_A-Branch-and-Price_2021.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Dimensione 667.68 kB
DelleDonne_preprint_A-Branch-and-Price_2021.pdf

accesso aperto

Note: https://doi.org/10.1016/j.dam.2020.08.031
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/1571754`