skip to main content
Idioma:

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

Lucci, Mauro ; Nasini, Graciela ; Severín, Daniel

European journal of operational research, 2024-06, Vol.315 (3), p.899-912 [Periódico revisado por pares]

Elsevier B.V

Texto completo disponível

Citações Citado por
  • Título:
    Solving the List Coloring Problem through a branch-and-price algorithm
  • Autor: Lucci, Mauro ; Nasini, Graciela ; Severín, Daniel
  • Assuntos: Branch and price ; Combinatorial optimization ; Integer programming ; Weighted list coloring
  • É parte de: European journal of operational research, 2024-06, Vol.315 (3), p.899-912
  • Descrição: 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. •Branch-and-price algorithm for weighted list coloring problem; exact resolution.•List coloring problem generalizes many graph coloring and set covering problems.•List coloring solves graph vertex coloring, mu-coloring, precoloring extension.•Indistinguishable colors cut symmetric solutions in the ILP formulation.•Experimentation with branching strategies on random and benchmark instances.
  • Editor: Elsevier B.V
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.