Optimization Online


A Branch-and-Price Algorithm for the Minimum Sum Coloring Problem

Diego Delle Donne(diegodd***at***gmail.com)
Fabio Furini(fabio.furini***at***iasi.cnr.it)
Enrico Malaguti (enrico.malaguti***at***unibo.it)
Wolfler Calvo Roberto (wolfler***at***lipn.univ-paris13.fr)

Abstract: A proper coloring of a given graph is an assignment of colors (integer numbers) to its vertices such that two adjacent vertices receives di different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for fi nding a proper coloring while minimizing the sum of the colors assigned to the vertices. This paper presents the rst 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. Extensive computational experiments, on synthetic and benchmark graphs from the literature, show that the new algorithm outperforms a natural compact IP formulations in terms of: (i) number of solved instances, (ii) running times and (iii) dual gaps obtained when optimality is not achieved. The new exact method is able to solve to optimality 8 out of the 17 (yet unclosed) hard DIMACS instances tested in this work.


Category 1: Combinatorial Optimization

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 01/29/2020
Entry Accepted: 01/29/2020
Entry Last Modified: 01/29/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society