Solving the List Coloring Problem through a branch-and-price algorithm

Mauro Lucci, Graciela Nasini and Daniel Severín

European Journal of Operational Research, 2024, vol. 315, issue 3, 899-912

Abstract: In this work, we present a branch-and-price algorithm to solve the weighted version of the List Coloring Problem, based on a vertex cover formulation by stable sets. This problem is interesting for its applications and also for the many other problems that it generalizes, including the well-known Graph Coloring Problem. With the introduction of the concept of indistinguishable colors, some theoretical results are presented which are later incorporated into the algorithm. We propose two branching strategies based on others for the Graph Coloring Problem, the first is an adaptation of the one used by Mehrotra and Trick in their pioneering branch-and-price algorithm and the other is inspired by the one used by Méndez-Díaz and Zabala in their branch-and-cut algorithm. The rich structure of this problem makes both branching strategies robust. Extensive computation experimentation on a wide variety of instances shows the effectiveness of this approach and evidences the different behaviors that the algorithm can have according to the structure of each type of instance.

Keywords: Combinatorial optimization; Integer programming; Weighted list coloring; Branch and price (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724000742
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:315:y:2024:i:3:p:899-912

DOI: 10.1016/j.ejor.2024.01.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().