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

Given a simple graph $G=(V,E)$ and a set of colors $K=\{1,\ldots,|K|\}$, define a coloring $c:V\rightarrow K$ as a function which assigns to each vertex $v\in G$ a color $i\in K$. A coloring is said to be proper if $c(u)\not=c(v)$ for every $uv\in E$. An example of proper coloring is illustrated in Figure 1.

Given a coloring $c$, define $v$ to be a $b$-vertex if $v$ has at least one neighbor with each color in $K\setminus\{c(v)\}$, more precisely, $N(v)\cap\{u\in V\ |\ c(u)=i\}\not=\varnothing$ for every $i\in K\setminus\{c(v)\}$. A coloring is said to be a $b$-coloring if every color in $K$ has at least one associated $b$-vertex. Examples of $b$-colorings are illustrated in Figure 2. Alternatively, define color classes of $c$ as the parts of a partition of $V$ into independent sets $C_{i}=\{v\in V\ |\ c(v)=i\}$ for each $i\in K$. A vertex $v\in V$ with $c(v)=j$ is called a b-vertex for color $j$ if $v$ has a neighbor representing every other color class, i.e., $N(v)\cap C_{i}\neq\varnothing$ for all $i\in K\setminus\{j\}$. In this alternative definition, a $b$-coloring is a proper coloring such that every color class has a b-vertex.

The chromatic number of a graph $G$, ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}(G)$, is the minimum number of colors needed to properly color $G$. The $b$-chromatic number of a graph $G$, ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)$, is the maximum number of colors for which $G$ admits a $b$-coloring. The coloring problem consists in encountering a proper coloring of a graph minimizing the number of colors. The $b$-coloring problem consists in encountering a proper $b$-coloring of a graph maximizing the number of colors. The problem of finding ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)$ was shown to be NP-hard in \citeAIrvMan99, thus the $b$-coloring problem is NP-hard.

Although the $b$-coloring and the coloring problems appear to be closely related, they have several differences. First of all, they consider the objective functions in opposite directions and the difference between their optimal solution values can be arbitrarily large Kratochvíl \BOthers. (\APACyear2002). Furthermore, the $b$-coloring problem can be largely influenced by the girth (length of a shortest cycle) of the graph, what is not exactly the case for the coloring problem V. Campos \BOthers. (\APACyear2013). Besides, a property that is commonly exploited by constructive and enumerative methods for the coloring problem is the fact that one can have solutions with the number of colors ranging from the chromatic number to the cardinality of the vertex set. However, it is not true that one can construct a $b$-coloring with $k$ colors for every integer $k$ ranging from the chromatic number to the $b$-chromatic number Barth \BOthers. (\APACyear2007). Additionally, notice that a proper graph coloring which is not a $b$-coloring can be trivially improved by the removal of a color, namely, one that does not have a $b$-vertex. Therefore, when one is trying to minimize the number of colors, $b$-colorings appear naturally as otherwise the available coloring could be easily improved. On the other hand, when one is trying to maximize the number of colors, it is a challenging task to increase the number of colors while ensuring that $b$-vertices are generated for every new color. This suggests that the search for good quality solutions for the $b$-coloring problem should explore the structure of feasible solutions in a different manner.

CaLiMa15 presented a motivation for solving the $b$-coloring problem, namely, finding an upper bound for the $b$-algorithm which is a heuristic approach for the coloring problem. The $b$-algorithm works as follows, it begins with a greedy coloring and afterwards tries to reduce the number of used colors by changing the colors of certain vertices. In this context, a $b$-vertex represents a vertex that cannot have its color changed and thus forbids further improvements by the $b$-algorithm. Hence, the $b$-chromatic number represents the worst case of the $b$-algorithm.

Let $N(v)=\{u\in V\ |\ uv\in E\}$ be the open neighborhood (or simply neighborhood) of $v$ in $G$, $N[v]=N(v)\cup\{v\}$ be the closed neighborhood of $v$ in $G$, $\bar{N}(v)=V\setminus N[v]$ be the anti-neighborhood of $v$ in $G$, and $\bar{N}[v]=\bar{N}(v)\cup\{v\}$ be the closed anti-neighborhood of $v$ in $G$. Define $N_{c}(v)=\{i\in K\ |\ c(u)=i\textrm{ for some }u\in N(v)\}$ to be the set of colors adjacent to $v$, which we denote the color neighborhood of $v$. Also, let $N_{c}[v]=N_{c}(v)\ \cup\ \{c(v)\}$ be the color closed neighborhood, and $\bar{N}_{c}(v)=K\setminus N_{c}[v]$ be the color anti-neighborhood of $v$. Denote the degree of $v$ by $d(v)$, which is the size of its neighborhood $|N(v)|$. Considering $\Delta(G)$ to be the maximum degree of a graph, we write $\Delta$ whenever $G$ is clear from the context. The neighborhood of a $b$-vertex can contain at most $\Delta$ colors. Define the color degree of $v$ by $d_{c}(v)$, which is the size of its color neighborhood $|N_{c}(v)|$. Consider a sorting of the vertices $V=\{v_{1},v_{2},\ldots,v_{n}\}$ such that $d(v_{1})\geq d(v_{2})\geq...\geq d(v_{n})$. The invariant $m(G)=max\{i\ |\ i-1\leq d(v_{i})\}$ provides an upper bound for the $b$-chromatic number of $G$. Let $V_{m}\subseteq V$ be the subset of vertices with degree at least $m(G)-1$, i.e. for each $v\in V_{m}$, $d(v)\geq m(G)-1$. Denote $K_{m}\subseteq K$ as the set of colors that were attributed to some vertex in $V_{m}$ in a given coloring $c$, i.e. $k\in K_{m}$ if there is a vertex $v\in V_{m}$ such that $c(v)=k$.

The concept of $b$-coloring appeared in different applications. \citeAGacEglLebEmp08,GacEglLebEmp09 applied $b$-coloring to improve postal mail sorting systems, which are based on efficient optical recognition of the addresses on envelopes. The authors presented a new approach for address block localization, which is a very important step on the recognition of the addresses. Their approach uses $b$-coloring to train a classifier in the identification of the address block, and according to the authors a rate of 98% good locations on a set of 750 envelope images was obtained. \citeAElgDesHacDusKhe06 proposed a new clustering approach based on $b$-coloring of graphs. The presented cluster validation algorithm evaluates the quality of clusters based on the $b$-vertex property. The authors take on this clustering technique to detect a new typology of hospital stays in the French healthcare system.

Several authors studied properties of $b$-coloring for special classes of graphs. \citeAKraTuzVoi02 have shown that deciding the $b$-chromatic number is NP-Complete even for bipartite graphs. A graph $G$ is $m$-tight if it has exactly $m(G)$ vertices with degree exactly equal to $m(G)-1$. In this regard, \citeAHavSalSam12 proved that deciding if ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)=m(G)$ is NP-Complete for tight chordal graphs, while showing that the $b$-chromatic number of a split graph can be obtained in polynomial time.

Primal bound results were introduced by \citeAIrvMan99. We can assume that the chromatic number ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}(G)$ is a lower bound, as every $b$-coloring is also a proper coloring. The upper bound is $\Delta+1$, on account of the additional color being the color of a $b$-vertex itself. This upper bound can be narrowed, since for a $b$-coloring we need a sufficient amount of vertices of high degree. Naturally, for a $b$-coloring with $k$ colors, at least $k$ vertices with $k-1$ minimum degree are necessary. As a consequence, $m(G)$ is a reduced upper bound for the problem. A variety of bounds on the $b$-chromatic number were also presented in \citeAAlkKoh11, BalRaj13, KouMah02.

Regular graphs belong to a special class of graphs such that $m(G)=\Delta+1$, one of the main reasons why they attract significant study. \citeAKraTuzVoi02 have shown that for every $d$-regular graph with at least $d^{4}$ vertices ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)=\Delta+1$, establishing that there is only a limited number of $d$-regular graphs for which ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)<\Delta+1$. Later, \citeACabJak11 proved that for every $d$-regular graph with at least $2d^{3}$ vertices ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)=\Delta+1$. A detailed review of the literature related to the $b$-chromatic number can be found in \citeAJakPet18.

The $b$-coloring problem for more general graphs was considered in several works. \citeACorValVer05 introduced an approximation approach for the $b$-chromatic number. They have shown that the $b$-chromatic number cannot be approximated within a factor of $120/133-\epsilon$ for any constant $\epsilon>0$, unless P = NP. \citeAGalKat13 settled negatively the question about the existence of a constant-factor approximation algorithm for the $b$-chromatic number, proving that for graphs with $n$ vertices, there is no $\epsilon>0$, for which the problem can be approximated within a factor $n^{1/4-\epsilon}$, unless P = NP.

Despite the fact that the $b$-coloring problem has received a lot of attention from the graph theory community, just a few authors considered optimization approaches such as metaheuristics or integer programming. To the best of our knowledge, \citeAFisPetMerCre15 were the first authors to propose a metaheuristic algorithm for the $b$-coloring problem. They proposed an hybrid evolutionary algorithm and tested its performance on a set of small instances composed of $d$-regular graphs. For the tested $d$-regular instances, the metaheuristic obtained the optimal solutions, which were attested using a brute force method. Encouraged by those results, the authors also considered larger benchmark instances from the second DIMACS implementation challenge Johnson \BBA Trick (\APACyear1996). As far as our knowledge goes, the only metaheuristic for the $b$-coloring problem is the one presented in \citeAFisPetMerCre15, contrasting with the classical graph coloring problem, as the latter has a diversity of heuristic methods proposed in the literature Avanthay \BOthers. (\APACyear2003); Blöchliger \BBA Zufferey (\APACyear2008); de Werra (\APACyear1990); Lü \BBA Hao (\APACyear2010); Mabrouk \BOthers. (\APACyear2009).

KocPet15 introduced an integer linear programming formulation for the $b$-chromatic index ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}^{\prime}(G)$, the edge version of the problem. The authors also provide bounds and general results for a diversity of direct products of graphs regarding the $b$-chromatic index. \citeAKocMar18 proposed an integer programming approach for the decision version of the $b$-coloring problem, which consists in determining whether a graph $G$ admits a $b$-coloring with a given number of colors. The authors also performed a polyhedral study of the proposed formulation, presented valid inequalities and implemented a branch-and-cut algorithm. Computational experiments were performed testing whether ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{b}(G)=m(G)$ for the input graphs.

The main contributions of this paper are an integer programming formulation for the $b$-coloring problem, a very effective multi-start multi-greedy randomized metaheuristic which attempts to explore the problem structure in the search for good quality solutions, and a matheuristic approach obtained by combining the proposed multi-start metaheuristic with a fix-and-optimize local search based on the introduced integer programming formulation. To the best of our knowledge, this paper presents the first matheuristic for the $b$-coloring problem, and the first integer programming formulation which can be directly applied to its optimization version. Furthermore, we present a benchmark set consisting of newly created instances as well as available ones for coloring and maximum clique problems. The computational experiments show that the newly proposed approaches are very effective, reaching and proving optimality for several of the tested instances. Furthermore, the approaches are able to outperform a state-of-the-art metaheuristic Fister \BOthers. (\APACyear2015) for the $b$-coloring problem when taking into consideration all nine large instances considered by those authors.

The remainder of the paper is organized as follows. Section 2 introduces an integer programming formulation for the $b$-coloring problem. Section 3 describes the multi-greedy randomized heuristic. Section 4 presents the multi-start multi-greedy randomized metaheuristic, the MIP (mixed-integer programming) based fix-and-optimize local search procedure using the proposed integer programming formulation, and the matheuristic approach which is obtained by combining the first two. Section 5 summarizes the computational experiments. Final considerations are discussed in Section 6.

An initial coloring is obtained using procedure INITIAL-COLORING, which is detailed in Algorithm 2. In addition to the graph $G$, the algorithm also takes as input a parameter $\alpha$ related to the size of restricted candidate lists. The structures $c$, $N_{c}$, $K_{c}$, and $K_{b}$ will be returned at the end of its execution. We remark that, for ease of explanation, the pseudo-code which will be presented assumes the graph is connected. An easy way to overcome this fact will be given once the algorithm is described. The following structures are used by the algorithm:

• •

  $K^{\prime}$: initial set of available colors;

• •

  $Q$: stores the set of vertices which had already been colored;

• •

  $\Upsilon_{v}$: keeps the vertices in $N(v)$ which have no attributed color;

• •

  $K_{m}$: set of colors in $K_{c}$ that were attributed to some vertex $v\in V$ with degree at least $m(G)-1$.

INITIAL-COLORING uses the following auxiliary method:

• •

  HEURISTIC-COLOR-VERTEX: described in Algorithm 3, the procedure takes as inputs the graph $G$, vertices $v$ and $u$, as well as structures $N_{c}$, $K^{\prime}$, $K_{m}$. The method returns a color to be attributed to vertex $u$. Firstly, structure $LC$ is initialized as empty (line 3), and will store the set of candidate colors for coloring $u$. The algorithm then checks if $u$ has degree greater than or equal to $m(G)-1$ (line 3) and tries initially to build $LC$ with the set of colors $k\in K^{\prime}$ not belonging to the color neighborhood of neither $v$ nor $u$, and have not been assigned to a vertex with degree greater than or equal to $m(G)-1$, i.e., $k\not\in N_{c}(v)$, $k\not\in N_{c}(u)$ and $k\not\in K_{m}$ (line 3). The purpose behind this coloring idea is to diversify the colors assigned to both neighborhoods of $u$ and $v$, while trying to give different colors to vertices with high enough degrees to become $b$-vertices, in an attempt to increase the probability of finding $b$-vertices that represent the greater amount of color classes. If $LC$ is still empty (line 3), the algorithm tries to include in $LC$ colors $k\in K^{\prime}$ not belonging to the color neighborhood of neither $v$ nor $u$, i.e., $k\not\in N_{c}(v)$ and $k\not\in N_{c}(u)$ (line 3). If no such color exists, i.e., $LC$ remains with no elements in line 3, $LC$ is built in line 3 with colors $k\in K^{\prime}$ not belonging to the color neighborhood of $u$, i.e., $k\not\in N_{c}(u)$. This guarantees at least one color in $LC$ since the algorithm initially works with $\Delta+1$ available colors and $d(u)\leq\Delta$. The color in $LC$ with lowest index is returned in line 3.

Algorithm 2 first initializes the used structures as follows. For each vertex $v\in V$, the color neighborhood of $v$ is initialized as empty and $c(v)$ is set to 0, which implies that no color is assigned to $v$ (line 2). The sets $K_{c}$, $K_{m}$ and $K_{b}$ are initialized as empty (line 2). Next, the algorithm sets $v_{\Delta}$ as the maximum degree vertex in $G$ in line 2, where ties are broken arbitrarily. The set $K^{\prime}$ is initialized with $\Delta+1$ colors in line 2, followed by the coloring of $v_{\Delta}$ with color 1 in line 2. The structures $N_{c}$, $K_{c}$ and $K_{m}$ are updated in line 2. The neighborhood of vertices in $Q$ are yet to be explored, and the set is initialized with $v_{\Delta}$ in line 2. The algorithm then performs a series of iterations to assign colors to the vertices in $G$ while the set $Q$ is not empty in lines 2-2. Elements from a restricted candidate list (RCL) containing the best elements in $Q$ are randomly chosen along the construction of the solution. Given the vertices in $Q$ the greedy choice criterion for RCL${}_{Q}(\alpha)$ is:

• •

  maximization of the vertex degree: $p_{1}=\max_{v\in Q}d(v)$.

RCL${}_{Q}(\alpha)$ is defined as a subset of $Q$ containing all candidates whose evaluation for the greedy criterion lies in an interval of values defined by a parameter $\alpha\in[0.0,1.0]$. Define $\underline{p_{1}}=\min_{v\in Q}d(v)$, thus this interval is given by $[p_{1}-\alpha(p_{1}-\underline{p_{1}}),p_{1}]$. RCL${}_{Q}(\alpha)$ is created in line 2. A vertex $v$ is randomly selected from RCL${}_{Q}(\alpha)$ in line 2. Set $\Upsilon_{v}$ is built in line 2 with the vertices in $N(v)$ that have no assigned color. Similar to RCL${}_{Q}(\alpha)$, elements from a restricted candidate list containing the best elements in $\Upsilon_{v}$ are randomly chosen along the construction of the solution. Given the vertices in $\Upsilon_{v}$, the greedy choice criterion for RCL${}_{\Upsilon_{v}}(\alpha)$ is:

• •

  maximization of the vertex degree: $p_{2}=\max_{v\in\Upsilon_{v}}d(v)$.

RCL${}_{\Upsilon_{v}}(\alpha)$ is defined for $\Upsilon_{v}$ as RCL${}_{Q}(\alpha)$ was defined for $Q$. RCL${}_{\Upsilon_{v}}(\alpha)$ is created in line 2. A vertex $u$ is randomly selected from RCL${}_{\Upsilon_{v}}(\alpha)$ in line 2 and receives a color determined by procedure HEURISTIC-COLOR-VERTEX in line 2. The structures $N_{c}$, $K_{c}$ and $K_{m}$ are updated in line 2. The neighborhood of $u$ is yet to be explored, so the vertex is inserted into $Q$ in line 2. Vertex $u$ is then removed from $\Upsilon_{v}$ in line 2 and a new iteration resumes, until set $\Upsilon_{v}$ becomes empty. Vertex $v$ is then withdrawn from $Q$ in line 2. After all vertices have been colored, i.e., $Q$ is empty, the algorithm updates the list $K_{b}$ of colors having $b$-vertices in line 2. The structures $c$, $N_{c}$, $K_{c}$ and $K_{b}$ are then returned in line 2. Note that, for ease of explanation, the described pseudo-code assumes the graph is connected. However, in the case of a disconnected graph, this can be overcome by simply inserting into $Q$ the uncolored vertex of highest degree (if there is at least one uncolored vertex) as a last step in the loop of lines 2-2 whenever $Q$ becomes empty.

A feasible $b$-coloring is obtained using procedure FIND-B-COLORING, which is detailed in Algorithm 4. In addition to the graph $G$ and RCL size parameters $\alpha$ and $\beta$, the algorithm also takes as inputs the sets $N_{c}$, $K_{b}$, $K_{c}$, and the coloring $c$. Remark that the inputs $c$ and $K_{c}$ will be updated by the algorithm and will be returned at the end of its execution. The following structure is used:

• •

  $\bar{K}_{b}$: set of colors that do not have $b$-vertices.

FIND-B-COLORING, which is a modification of the $b$-algorithm mentioned in the introduction, consists in iteratively eliminating colors from the graph by recoloring vertices colored with colors in $\bar{K}_{b}$. The set $\bar{K}_{b}$ is initialized with every color in $K_{c}\setminus K_{b}$ in line 4. The algorithm then performs a series of iterations while $\bar{K}_{b}$ is not empty (lines 4-4). Elements from a restricted candidate list containing the best elements in $\bar{K}_{b}$ are randomly chosen along the construction of the solution. Given the colors in $\bar{K}_{b}$ the greedy choice criterion for RCL${}_{\bar{K}_{b}}(\beta)$ is:

• •

  maximization of the color index: $p_{3}=\max_{r\in\bar{K}_{b}}r$;

Criterion $p_{3}$ aims to remove colors with higher index since after the execution of Algorithm 2, colors with smaller index are presumably closer to have a $b$-vertex. RCL${}_{\bar{K}_{b}}(\beta)$ is defined as a subset of $\bar{K}_{b}$ containing its $\beta$ best candidates. RCL${}_{\bar{K}_{b}}(\beta)$ is created in line 4. A color $r$ is randomly selected from RCL${}_{\bar{K}_{b}}(\beta)$ in line 4. For each vertex $v\in V$ colored with $r$, i.e., $c(v)=r$, a new color is assigned to $v$ (lines 4-4). Note that any color in $\bar{N}_{c}(v)$ is avaiable to color $v$. Elements from a restricted candidate list containing the best elements in $\bar{N}_{c}(v)$ are randomly chosen along the construction of the solution. Before explaining the greedy criterion, let $\zeta_{rv}$ be the number of vertices adjacent to $v$ such that color $r\in\bar{N}_{c}(v)$ is also not in their color neighborhood. Additionally, let $M_{uv}\subseteq\bar{N}_{c}(v)$ be the set of colors not adjacent to neither $u$ nor $v$. Define $M_{uv}^{*}=\operatorname*{argmin}_{M_{uv}:u\in N(v)}|M_{uv}|$ as the minimum cardinality set among all $M_{uv}$ for $u\in N(v)$. Note that $M_{uv}^{*}$ is the set of colors not adjacent to the vertex with the minimum number of missing colors in its color neighborhood. Given the colors in $\bar{N}_{c}(v)$ the greedy choice criteria for RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ are:

• •

  maximization of vertices with a new color added to their color neighborhood: $p_{4}=\max_{r\in\bar{N}_{c}(v)}\zeta_{rv}$;

• •

  minimization of the color index considering the colors in $M_{uv}^{*}$: $p_{5}=\min_{r\in M_{uv}^{*}}r$.

Criterion $p_{4}$ intends to increase the color neighborhood of as many vertices as possible, whereas $p_{5}$ aims to predict the vertex which is the closest to become a $b$-vertex. Given $p_{4}$, RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ is defined as a subset of $\bar{N}_{c}(v)$ containing all candidates whose evalutation of the greedy criterion lie in an interval of values defined by a parameter $\alpha\in[0.0,1.0]$. Define $\underline{p_{4}}=\min_{r\in\bar{N}_{c}(v)}\zeta_{rv}$, thus this interval is given by $[p_{4}-\alpha(p_{4}-\underline{p_{4}}),p_{4}]$. As for $p_{5}$, RCL${}_{\bar{N}_{c}(v)}$ is defined as a subset of ${\bar{N}_{c}(v)}$ containing its $\beta$ best candidates.

RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ is created in line 4. Any of the greedy functions $p_{4}$ or $p_{5}$ can be chosen for the construction of RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ and they are selected at random with 50% chance each. Note that, as stated previously on the definition of $p_{4}$ and $p_{5}$, the selection of the one to be used will define if RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ uses $\alpha$ or $\beta$. Vertex $v$ receives a color randomly selected from RCL${}_{\bar{N}_{c}(v)}(\alpha,\beta)$ in line 4. Color neighborhood of vertices in $N(v)$ are then updated in line 4. After all vertices previously colored with $r$ have been assigned a new color, $r$ is removed from set $K_{c}$ in line 4.

The algorithm then certifies if colors in $\bar{K}_{b}$ now have a $b$-vertex in lines 4-4. Colors that now have a $b$-vertex are removed from $\bar{K}_{b}$ in line 4. Lastly, $r$ is removed from $\bar{K}_{b}$ in line 4. The algorithm terminates when $\bar{K}_{b}=\varnothing$ which implies $K_{b}=K_{c}$, so the resulting $b$-coloring $c$ and the set of used colors $K_{c}$ are returned in line 4.

The pseudo-code of the multi-start multi-greedy randomized metaheuristic is described in Algorithm 5. In addition to the graph $G$ and two parameters regarding the sizes of restricted candidate lists (RCL), namely $\alpha$ and $\beta$, the algorithm also takes as input $it_{max}$, which represents the maximum number of iterations that the multi-greedy randomized heuristic will be executed.

Procedure MULTISTART-B-COL will save in $c^{*}$ the best obtained coloring. The set of used colors in $c^{*}$, $K_{c}^{*}$, is initialized as empty (Algorithm 5, line 5). The coloring generated at iteration $i\leq it_{max}$ is represented by $c_{i}$ and the corresponding set of used colors as $K_{c_{i}}$. $|K_{c_{i}}|$ represents the solution value, which is the number of used colors in coloring $c_{i}$. The loop in lines 5–5 performs iterations $i=1,\ldots,\mathit{it}_{\mathit{max}}$. The construction phase starts by invoking procedure RANDOMIZED-CONSTRUCTIVE to build the solution $c_{i}$ in line 5. In case an improving solution is obtained, the algorithm updates $c^{*}$ and $K_{c}^{*}$ in lines 5-5. If the solution value of $c^{*}$ matches the upper bound $m(G)$ the execution of RANDOMIZED-CONSTRUCTIVE is terminated by returning $c^{*}$ in line 5, as the solution is proven to be optimal. Otherwise, a new iteration begins until the maximum number of iterations $it_{max}$ is exceeded. The solution with the highest number of used colors, i.e., the best solution $c^{*}$ encountered by the multi-start phase, is returned in line 5.

Given an available feasible solution, the MIP-based fix-and-optimize local search procedure consists in generating a subproblem obtained from the original $b$-coloring problem by fixing certain decision variables at the values they assume in the available feasible solution which is also offered as a warm start for the used MIP solver. With fewer variables remaining to be optimized, it is expected that the resulting subproblem is more tractable by a standard MIP solver than the original problem. In this work, the input feasible solution consists of the best solution generated by MULTISTART-B-COL. The MIP-based fix-and-optimize local search is described in Algorithm 6. In addition to the graph $G$ and an initial feasible solution, represented by $c$ and $K_{c}$, the algorithm also takes as input the maximum time allowed for solving the obtained MIP formulation given by MAXTIME. In our framework, the initial feasible solution offered to MIP-LS will be the currently best known solution returned by MULTISTART-B-COL.

The set of representative $b$-vertices $V^{b}\subseteq V$ and the set of vertices $V^{0}\subseteq V$ that cannot be representatives in an improving solution are initialized as empty in line 6 of Algorithm 6. Set $V^{b}$ is built according to the input solution in the foreach loop of lines 6-6. Following Observations 1 and 2, set $V^{0}$ is built from the input solution in the foreach loop of lines 6-6 with all vertices which are not $b$-vertices in coloring $c$ and have degree strictly smaller than its number of colors $|K_{c}|$. Line 6 solves a mixed integer program defined by the formulation presented in Section 2, in which all variables in $V^{b}$ are fixed to one (i.e., all corresponding vertices are selected to be representatives in the solution) and all vertices in $V^{0}$ are fixed to zero. Additionally, coloring $c$ is provided as a warm start, i.e., as an initial feasible solution. Fixing is achieved by adding the following additional constraints to the formulation

The best solution obtained by the resulting MIP restricted to a maximum time limit MAXTIME is returned in line 6. Note that the input coloring $c$ is always feasible for this MIP subproblem.

Combinations of metaheuristics with exact algorithms from mathematical programming approaches such as mixed integer programming (MIP), called matheuristics, have received considerable attention over the last few years. It has been acknowledged by the optimization research community that combining effort from exact and metaheuristic approaches could achieve better solutions when compared with pure classic methods Raidl \BBA Puchinger (\APACyear2008); Dumitrescu \BBA Stützle (\APACyear2009). Matheuristics frequently benefit from metaheuristics as the main method to compute good quality solutions, with the exact approach used to enhance these solutions by solving subproblems. Motivated by recently successful results by matheuristics Doi \BOthers. (\APACyear2018); Cunha \BOthers. (\APACyear2019); Perumal \BOthers. (\APACyear2019); Melo \BOthers. (\APACyear2021), we combine the multi-start metaheuristic MULTISTART-B-COL that appears in Algorithm 5 with the MIP-based fix-and-optimize local search procedure presented in Algorithm 6, which produces the matheuristic MSBCOL⁺:

The new set of instances was constructed using the graph generator ggen Morgenstern (\APACyear\bibnodate) and includes bipartite, geometric and random graphs. Small instances were created with the following parameters: (a) $\{50,60,70,80\}$ vertices; (b) edge probability for random and bipartite graphs and the euclidean distance for geometric graphs lie in $\{0.2,0.4,0.6,0.8\}$. Five instances were generated for each combination of number of vertices and edge probability (or euclidean distance for the geometric graphs), therefore instances with those same characteristics, but different seeds, are organized into instance groups. Each instance group is identified by $C\_n\_p$, where $C$ represents the class of the graph: random ($R$), bipartite ($B$), and geometric ($G$); $n$ gives the number of vertices and $p$ denotes the edge probability for random and bipartite graphs, and the euclidean distance for geometric graphs. More challenging large bipartite and random instances were also created in a similar fashion but with the number of vertices in $\{500,600,700,800\}$. We remark that all results reported for this set of instances represent average values over the corresponding instance group.

We also use the graphs presented in the benchmark instances from the Second DIMACS Implementation Challenge as they are largely used in the literature, especially for coloring and maximum clique problems Avanthay \BOthers. (\APACyear2003); Lü \BBA Hao (\APACyear2010); Moalic \BBA Gondran (\APACyear2018); Nogueira \BOthers. (\APACyear2018); San Segundo \BOthers. (\APACyear2019). The instances are identified by their original filename and can be obtained in the DIMACS Implementation Challenges website Trick \BOthers. (\APACyear2015). We denote the instances for coloring problems as graph coloring instances and those for maximum clique problems as maximum clique instances. The complete benchmark instances along with detailed results for each instance are available in \citeAMelQueSan20 at Mendeley Data.

In this subsection we present the tested approaches and the preliminary experiments carried out to determine the parameters of the proposed techniques. The following approaches were considered in the computational experiments:

• (a)

  MSBCOL: run exclusively MULTISTART-B-COL in parallel using all cores of the target machine;

• (b)

  MSBCOL⁺: run the matheuristic, using the best solution encountered by the metaheuristic MSBCOL as a warm start for the MIP-based fix-and-optimize local search procedure;

• (c)

  MSBCOL^∗: run the complete integer programming formulation presented in Section 2, using the best solution encountered by the metaheuristic MSBCOL as a warm start. Following Observations 1 and 2, variables corresponding to vertices with degree less than or equal to this best solution value are fixed to zero, as long as they are not $b$-vertices in the warm start solution;

• (d)

  IP: Run the integer programming formulation presented in Section 2 without any initial solution or fixings of variables.

The used test strategy was adopted to evaluate the behavior of the newly proposed methods according with the class and size of the benchmark instances. Furthermore, we wanted to verify the effectiveness of the MIP-based fix-and-optimize local search when compared with the complete formulation.

Define $p(G)$ to be the density of $G$, calculated as $p(G)=\frac{2\times|E|}{|V|\times(|V|-1)}$, and let the maximum number of iterations for MULTISTART-B-COL, $it_{max}$, be computed as $it_{max}=100+\left\lfloor\frac{1000}{\sqrt{|V|}\times\sqrt{p(G)}}\right\rceil$. This formula for $it_{max}$ can be interpreted as follows. The minimum number of iterations that the algorithm executes is given by the first part of the formula, which is the constant 100. The variable number of iterations given by $\left\lfloor\frac{1000}{\sqrt{|V|}\times\sqrt{p(G)}}\right\rceil$ is inversely proportional to the size and density of the graph, as iterations become more time consuming on larger and denser graphs. Such choice was made as an attempt to allow a reasonable number of iterations in order to avoid poor performance of the algorithm. The experiments to tune the parameter values are reported in the following. We randomly selected a small subset containing approximately 5.0% of the instances with varying characteristics for parameter tuning. The following values were tested for each parameter: