We study two Integer Linear Programming (ILP) formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. The first ILP formulation has a polynomial number of variables while the second one has an exponential number of variables and is tackled via column generation. Computational tests show that the linear programming relaxation of the second formulation provides tight lower bounds which allow us to solve to proven optimality some hard instances of the literature.

ILP Models and Column Generation for the Minimum Sum Coloring Problem

Furini, Fabio;Malaguti, Enrico;
2018

Abstract

We study two Integer Linear Programming (ILP) formulations for the Minimum Sum Coloring Problem (MSCP). The problem is an extension of the classical Vertex Coloring Problem in which each color is represented by a positive natural number. The MSCP asks to minimize the sum of the cardinality of subsets of vertices receiving the same color, weighted by the index of the color, while ensuring that vertices linked by an edge receive different colors. The first ILP formulation has a polynomial number of variables while the second one has an exponential number of variables and is tackled via column generation. Computational tests show that the linear programming relaxation of the second formulation provides tight lower bounds which allow us to solve to proven optimality some hard instances of the literature.
2018
Furini, Fabio; Malaguti, Enrico; Martin, Sébastien; Ternier, Ian-Christopher
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/657085
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact