A Column Generation-Based Lower Bound for the Minimum Sum Coloring Problem

Mehdi Mrad

doi:10.1109/ACCESS.2020.2973122

A Column Generation-Based Lower Bound for the Minimum Sum Coloring Problem

2020-01-01

2

OA

AI

Jouhaina Chaouachi Siala

A

Anis Gharbi

DOI：10.1109/ACCESS.2020.2973122

Original

Save

View PDF

Abstract

En 中文

The objective of this paper is to derive a tight and efficient lower bound for the minimum sum coloring problem. This NP-hard problem is a variant of the classical graph coloring problem where the objective is to minimize the sum of the colors. A column generation approach is proposed to solve the linear relaxation of a set partition-based formulation. Various enhancements are proposed in order to efficiently obtain attractive columns while avoiding as much as possible the exact solution of the huge number of the NP-hard pricing problems. Experimental results conducted on 42 hard benchmark instances show an average reduction of 89.73 & x0025; of the gap between the best known lower and upper bounds, including 14 new optimality results.

Keywords:

Chromatic sum

graph coloring

column generation

lower bound

A Column Generation-Based Lower Bound for the Minimum Sum Coloring Problem

Abstract

AI Summary

Journal

Organization