A Column Generation-Based Lower Bound for the Minimum Sum Coloring Problem
| Autor: | Anis Gharbi, Mehdi Mrad, Olfa Harrabi, Jouhaina Chaouachi Siala |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
column generation General Computer Science Chromatic sum 0211 other engineering and technologies General Engineering 0102 computer and information sciences 02 engineering and technology Partition of a set 01 natural sciences Upper and lower bounds Reduction (complexity) Combinatorics Exact solutions in general relativity 010201 computation theory & mathematics Benchmark (computing) graph coloring General Materials Science Column generation Relaxation (approximation) Graph coloring lcsh:Electrical engineering. Electronics. Nuclear engineering lower bound lcsh:TK1-9971 Mathematics |
| Zdroj: | IEEE Access, Vol 8, Pp 57891-57904 (2020) |
| ISSN: | 2169-3536 |
| Popis: | 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% of the gap between the best known lower and upper bounds, including 14 new optimality results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|