A matheuristic approach for the b-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic

DOI10.1016/J.EJOR.2021.02.049MaRDI QIDQ2239844zbMATH OpenOpenAlexFDO

Authors Rafael A. Melo, Michell F. Queiroz, Marcio C. Santos

Publication date 5 November 2021

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.09696

zbMATH Keywords

fix-and-optimizegraph \(b\)-coloringinteger programmingmatheuristicsmetaheuristics

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Integer programming (90C10) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Given a graph $G=(V,E)$, the $b$-coloring problem consists in attributing a color to every vertex in $V$ such that adjacent vertices receive different colors, every color has a $b$-vertex, and the number of colors is maximized. A $b$-vertex is a vertex adjacent to vertices colored with all used colors but its own. The $b$-coloring problem is known to be NP-Hard and its optimal solution determines the $b$-chromatic number of $G$, denoted $ch{i}_b(G)$. This paper presents an integer programming formulation and a very effective multi-greedy randomized heuristic which can be used in a multi-start metaheuristic. In addition, a matheuristic approach is proposed combining the multi-start multi-greedy randomized metaheuristic with a MIP (mixed integer programming) based local search procedure using the integer programming formulation. Computational experiments establish the proposed multi-start metaheuristic as very effective in generating high quality solutions, along with the matheuristic approach successfully improving several of those results. Moreover, the computational results show that the multi-start metaheuristic outperforms a state-of-the-art hybrid evolutionary metaheuristic for a subset of the large instances which were previously considered in the literature. An additional contribution of this work is the proposal of a benchmark instance set, which consists of newly generated instances as well as others available in the literature for classical graph problems, with the aim of standardizing computational comparisons of approaches for the $b$-coloring problem in future works.

Recommendations

• An integer programming approach to b-coloring
• A metaheuristic approach for the vertex coloring problem
• Hybrid evolutionary algorithm for the b-chromatic number
• New integer linear programming models for the vertex coloring problem
• A branch-and-price algorithm for the robust graph coloring problem

Cites work

• b-coloring graphs with girth at least 8
• \(b\)-coloring of tight graphs
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• A matheuristic for the driver scheduling problem with staff cars
• A memetic algorithm for graph coloring
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• A note on approximating the b-chromatic number
• A variable neighborhood search for graph coloring.
• An integer programming approach to b-coloring
• Bounds for the b-chromatic number of G-v
• Cliques, holes and the vertex coloring polytope
• Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization
• Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
• Effective matheuristics for the multi-item capacitated lot-sizing problem with remanufacturing
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• scientific article; zbMATH DE number 4187836 (Why is no real title available?)
• Hybrid evolutionary algorithm for the b-chromatic number
• On a parallel genetic-tabu search based algorithm for solving the graph colouring problem
• On approximating the b-chromatic number
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-continuity property of graphs
• Some bounds for the b-chromatic number of a graph
• The \(b\)-chromatic index of direct product of graphs
• The \(b\)-chromatic index of graphs
• The b-chromatic number and related topics -- a survey
• The b-chromatic number of a graph
• Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time
• Upper bounds on the b-chromatic number and results for restricted graph classes

Cited in

(7)

• A graph b-coloring framework for data clustering
• An integer programming approach to b-coloring
• MIP formulations for induced graph optimization problems: a tutorial
• Upper and lower bounds based on linear programming for the b-coloring problem
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• The connected Grundy coloring problem: formulations and a local-search enhanced biased random-key genetic algorithm
• Obtaining the Grundy chromatic number: how bad can my greedy heuristic coloring be?

Describes a project that uses

Uses Software

• DIMACS
• ils-mwis

This page was built for publication: A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2239844)