Improved semidefinite programming bounds for the maximum k k -colorable subgraph problem Mathijs Barkel, Renata Sotirov Abstract We study the maximum k k -colorable subgraph (M k k CS) problem, which consists in finding a largest k k -colorable induced subgraph in a given graph. We consider a Semidefinite Programming (SDP) relaxation for the M k k CS problem and regard its resulting upper bound as a graph parameter. We present several properties of this graph parameter, from which we obtain that the M k k CS problem is solvable in polynomial time for k k -perfect graphs. We further derive two novel families of valid inequalities to strengthen the SDP relaxation. The first family reduces to a family of inequalities for the Boolean quadric polytope when k = 1 k=1 , and the second family generalizes the family of rank inequalities for binary linear programming formulations of the stable set problem. We efficiently solve the strengthened SDP relaxation using a cutting-plane algorithm that is based on the Alternating Direction Method of Multipliers (ADMM). Extensive computational experiments show that the obtained upper bounds outperform the best upper bounds from the literature. To complement our SDP-based upper bounds, we propose an integer ADMM variant that uses an exact Binary Semidefinite Programming (BSDP) formulation of the M k k CS problem to produce high-quality feasible solutions. To the best of our knowledge, this is the first application of the ADMM to compute integer solutions to a BSDP problem. Keywords k k -colorable subgraph problem; graph coloring; k k -perfect graphs; cutting-plane methods; integer ADMM; semidefinite programming. Mathematics Subject Classification 05C15, 05C17, 90C22, 90C27, 90C35. Acknowledgments The authors thank Frank de Meijer for his tabu search code for the graph coloring problem, which is used to cluster the valid inequalities. The second author would also like to thank Renate van der Knaap for her tabu search algorithm for the M k CS problem. This work used the Dutch national e-infrastructure with the support of the SURF Cooperative using grant no. EINF-13681. 1 Introduction The maximum k -colorable subgraph (M k CS) problem is to find the largest induced subgraph in a given graph that can be colored in k colors such that no two adjacent vertices have the same color. Since a partial k -coloring of a graph is a set of pairwise disjoint stable sets in the graph, each one corresponding to a color, the solution for the M k CS problem corresponds to the largest possible number of colored vertices in a partial k -coloring. The M k CS problem is also known as the maximum k -partite induced subgraph problem, as well as the maximum bipartite subgraph problem for the case k=2 , while for k=1 it coincides with the stable set problem. The M k CS problem is known to be \mathcal{NP} -hard [ 36 ] . The M k CS problem arises in various practical applications, including channel assignment in spectrum-sharing networks [ 2 , 22 , 25 , 32 , 55 ] , very-large-scale integration design [ 15 , 41 ] , human genetic research [ 15 , 38 ] and job scheduling and register allocation [ 8 ] . The M k CS problem is also of interest due to its relation to several well-known combinatorial optimization problems. For instance, it is closely related to the graph coloring problem and the clique cover problem. Several works address the M k CS problem using integer programming, some of which exploit that the M k CS problem is invariant under color permutations and graph automorphisms. 7 introduce a Binary Linear Programming (BLP) formulation where color symmetry is handled through the selection of representatives of stable sets. They further propose a parallelized subgradient algorithm that uses a Lagrangian relaxation to decompose the M k CS problem into smaller weighted stable set problems. Lower and upper bounds are computed for instances with up to 500 vertices and 3 colors. 27 , 28 propose an alternative BLP formulation as the basis of a branch-cut-and-propagate algorithm that leverages both valid inequalities and domain propagation to handle color and graph symmetry. They solve instances with up to 1085 vertices and 25 colors to optimality. 51 derive two quadratic unconstrained binary optimization formulations for the M k CS problem that are solved using D-Wave’s quantum annealing device. The authors consider instances with up to 50 vertices and 5 colors. Another line of research focuses on Semidefinite Programming (SDP). 43 propose an eigenvalue bound for the M k CS problem called the generalized \vartheta -number of a graph \mathcal{G} (denoted by \vartheta_{k}(\mathcal{G}) ), which was later reformulated by 1 as the solution of a semidefinite program. This graph parameter coincides with the celebrated \vartheta -number by 39 for k=1 , and provides also a lower bound on the minimum number of colors needed for a valid k -multicoloring of the complement of the considered graph. 54 study \vartheta_{k}(\mathcal{G}) for highly symmetric graphs and provide closed-form solutions for several graph classes. 33 strengthen \vartheta_{k}(\mathcal{G}) by incorporating nonnegativity constraints, and consider several other SDP relaxations for the M k CS problem. Their strongest relaxation is derived via a vector-lifting approach, followed by a reduction in the size of the SDP relaxation that exploits the invariance of the M k CS problem under color permutations. This relaxation is further strengthened using inequalities from the Boolean quadric polytope (BQP). A weaker but more scalable relaxation is obtained through a matrix-lifting approach. The authors compare the strength of their relaxations from a theoretical point of view, and provide computational experiments on benchmark instances with up to 500 vertices. Several instances are solved to optimality, and the strongest upper bounds improve upon the upper bounds from [ 7 ] for all but two instances. Motivated by this success, we continue the line of research on SDP-based approaches for the M k CS problem. In particular, rather than using Interior Point Methods (IPMs), the classical approach for solving SDP problems, we consider the Alternating Direction Method of Multipliers (ADMM). This is a first-order method introduced in the 1970s to solve general convex optimization problems, see e.g., [ 4 ] . Compared to IPMs, the time and memory requirements of the ADMM scale better with the order of the matrix variables and the number of constraints. Indeed, the ADMM, and variants thereof, have been successfully applied to solve large-scale SDP relaxations of various combinatorial optimization problems, see e.g., [ 26 , 37 , 46 , 53 ] . 1.1 Main results and outline We start our study of the M k CS problem with a Binary Semidefinite Programming (BSDP) formulation proposed by 13 , from which we derive our basic SDP relaxation that coincides with the matrix-lifting relaxation from [ 33 ] . We consider the optimal value of the basic SDP relaxation, denoted by \theta_{k}(\mathcal{G}) , as a graph parameter. We derive several properties of this graph parameter, including that \theta_{k}(\mathcal{G}) is upper bounded by k\vartheta(G) for all k\geq 1 , and that the sequence \left(\theta_{k}(\mathcal{G})\right)_{k} is monotonically increasing in k . We also show that our graph parameter serves as a lower bound for the k -clique cover number of \mathcal{G} . 40 defined a k -perfect graph as a graph for which the number of vertices in a maximum k -colorable subgraph equals the k -clique cover number for each induced subgraph of \mathcal{G} . Therefore, these two graph parameters can be computed for k -perfect graphs in polynomial time up to fixed precision by solving our SDP relaxation for the M k CS problem. 40 posed an open question on the computability of these parameters for perfect graphs, and we provide an answer for k -perfect graphs where k>1 . The case k=1 is a well-known result by 20 . Moreover, we provide an answer to Lovász question for a class of perfect graphs known as totally perfect graphs. We also propose two novel families of valid inequalities to strengthen our SDP relaxation. Our first family of inequalities reduces to a family of inequalities for the BQP by 48 when k=1 . These new inequalities are not only relevant for our SDP relaxation for the M k CS problem, but potentially also for matrix-lifting relaxations of other packing or partitioning problems. Our second family of inequalities generalizes the family of rank inequalities for BLP formulations of the stable set problem by 45 . Given that there are exponentially many generalized BQP and rank inequalities, we also consider computationally tractable special cases of these inequalities that concern triangles, cliques and odd holes. We solve the strengthened SDP relaxation using a recently proposed extension of the ADMM, called the cutting-plane ADMM (CP-ADMM), which integrates the ADMM with Dykstra’s cyclic projection algorithm, see [ 10 , 12 , 11 ] . We improve the performance of the CP-ADMM by limiting the number of new cuts in which each variable may appear; a feature that was not yet used in existing CP-ADMM algorithms. Extensive computational experiments on benchmark instances show that the strengthened SDP relaxation can be solved efficiently, and that the upper bounds obtained outperform the best upper bounds from the literature. We present a novel integer ADMM variant, denoted by INT-ADMM, that is aimed at constructing feasible solutions for the BSDP formulation, thereby yielding valid lower bounds. Our INT-ADMM is based on the \ell_{p} -Box ADMM introduced by 56 . To the best of our knowledge, we are the first to apply the key idea of the \ell_{p} -Box ADMM to solve a BSDP problem. The INT-ADMM is not guaranteed to converge to an optimal or even a feasible solution, but our computational experiments show that our algorithm consistently leads to high-quality feasible solutions, often improving upon the best solutions in the literature. This success is partly due to an effective mechanism for escaping local optima. This paper is further structured as follows. In Section 2 , we formally introduce the M k CS problem, its BSDP formulation and our basic SDP relaxation. In Section 3 , we present our theoretical results on the graph parameter \theta_{k}(\mathcal{G}) . In Section 4 , we derive the valid inequalities. In Sections 5 and 6 , we present the CP-ADMM and INT-ADMM, respectively. In Section 7 , we report the results of our computational experiments, and finally, in Section 8 , we present our conclusions. 1.2 Notation We define [n]\mathrel{\mathop{:}}=\{1,\ldots,n\} , and denote by \mathbbm{1}_{\mathcal{S}}\in\{0,1\}^{n} the indicator vector of \mathcal{S}\subseteq[n] . We denote by 0_{n}\in\mathbb{R}^{n},e_{n}\in\mathbb{R}^{n},\mathbf{0}_{n}\in\mathbb{R}^{n\times n},J_{n}\in\mathbb{R}^{n\times n} and I_{n}\in\mathbb{R}^{n\times n} the all-zeros vector, all-ones vector, all-zeros matrix, all-ones matrix and identity matrix, respectively. We sometimes omit the subscripts of these matrices when their size is clear from the context or irrelevant. We regularly work with matrices of size (n+1)\times(n+1) , in which case the first row and column are indexed by 0 . The rank of a matrix X is denoted by {\text{rank}\left(X\right)} . The trace inner product of two matrices A,B\in \mathbb{R}^{m\times n} is given by \left\langle A,B\right\rangle\mathrel{\mathop{:}}={\text{tr}(}A^{\top}B)=\sum_{i=1}^{m}\sum_{j=1}^{n}A_{ij}B_{ij} . A real symmetric matrix X of size n\times n is denoted by X\in\mathbb{S}^{n} , and we denote by X\succeq\textbf{0} that the symmetric matrix X is positive semidefinite (PSD). The set of all PSD matrices of size n\times n is denoted by \mathbb{S}^{n}_{+}\mathrel{\mathop{:}}=\{X\in\mathbb{S}^{n}:X\succeq\textbf{0}\} . Similarly, X\preceq\textbf{0} indicates that matrix X is negative semidefinite (NSD), and we define \mathbb{S}^{n}_{-}\mathrel{\mathop{:}}=\{X\in\mathbb{S}^{n}:X\preceq\textbf{0}\} . We write X\geq\textbf{0} to denote that the matrix X is elementwise nonnegative. The operator \text{diag}:\mathbb{R}^{n\times n}\to\mathbb{R}^{n} maps a matrix to the vector containing its diagonal entries. Its adjoint operator \text{Diag}:\mathbb{R}^{n}\to\mathbb{R}^{n\times n} maps a vector to the diagonal matrix with that vector as diagonal. For any \mathcal{X}\subseteq\mathbb{R}^{n} and u,w\in\mathbb{R}^{n} , the w -weighted projection of u on \mathcal{X} is given by \mathcal{P}_{\mathcal{X}}^{w}(u)\mathrel{\mathop{:}}=\text{arg min}_{x\in\mathcal{X}}\left\{\sum_{i\in[n]}w_{i}(x_{i}-u_{i})^{2}\right\} . The (standard) projection of u on \mathcal{X} is given by \mathcal{P}_{\mathcal{X}}(u)\mathrel{\mathop{:}}=\mathcal{P}_{\mathcal{X}}^{e_{n}}(u)=\text{arg min}_{x\in\mathcal{X}}\left\lVert x-u\right\rVert^{2} . 2 A BSDP formulation and SDP relaxation for the M k CS problem Let \mathcal{G}=(\mathcal{V},\mathcal{E}) be a simple undirected graph with vertex set \mathcal{V}=[n] and edge set \mathcal{E} , and let k\in[n-1] be a given number of colors. A graph is said to be k -colorable if one can assign to each vertex one of the k colors such that no two adjacent vertices have the same color. The M k CS problem is to find an induced k -colorable subgraph of \mathcal{G} with maximum cardinality. Recall that the subgraph of \mathcal{G} induced by \mathcal{S}\subseteq\mathcal{V} is the graph \mathcal{G}[\mathcal{S}]=(\mathcal{S},\mathcal{E}[\mathcal{S}]) with vertex set \mathcal{S} and edge set \mathcal{E}[\mathcal{S}]\mathrel{\mathop{:}}=\{\{i,j\}\in\mathcal{E}:i,j\in\mathcal{S}\} . Let P\in\{0,1\}^{n\times k} be a binary matrix variable such that P_{ic}=1 if and only if vertex i\in[n] is assigned color c\in[k] . Then, the M k CS problem can be formulated as the following BLP problem: \displaystyle\begin{aligned} \alpha_{k}(\mathcal{G}):=\max\quad&\sum_{i\in[n]}\sum_{c\in[k]}P_{ic}\\ \text{s.t.}\quad&P_{ic}+P_{jc}\leq 1&\quad\forall\{i,j\}\in\mathcal{E},\;c\in[k]\,\\ &\sum_{c\in[k]}P_{ic}\leq 1&\quad\forall i\in[n]\,\\ &P_{ic}\in\{0,1\}&\quad\forall i\in[n],\;c\in[k].\end{aligned} (BLP k ) Next, we present a derivation from [ 13 ] of a BSDP formulation of the M k CS problem using a matrix-lifting approach. The key idea of this approach is to substitute the matrix variable P from ( BLPk ) by another matrix variable X such that X=PP^{\top} . This substitution can be performed as follows. First, using that P is binary, we have that X_{ii}=\sum_{c\in[k]}P_{ic}^{2}=\sum_{c\in[k]}P_{ic} for each i\in[n] , so we can rewrite the objective as \left\langle I_{n},X\right\rangle . Second, by again exploiting the binarity of P , we can replace the constraints P_{ic}+P_{jc}\leq 1 for \{i,j\}\in\mathcal{E} and c\in[k] , with the constraints X_{ij}=\sum_{c\in[k]}P_{ic}P_{jc}=0 for \{i,j\}\in\mathcal{E} . Finally, we consider the following set \mathcal{D}^{n}_{k} that captures the remaining constraints on P and the relation X=PP^{\top} : \mathcal{D}^{n}_{k}\mathrel{\mathop{:}}=\left\{X\in\mathbb{S}^{n}:X=PP^{\top},\,\sum_{c\in[k]}P_{ic}\leq 1\,\,\forall i\in[n],\,\,P\in\{0,1\}^{n\times k}\right\}. (1) Note that \mathcal{D}^{n}_{1} coincides with the set of extreme points of the BQP introduced in [ 48 ] . As implied by Proposition 2 of [ 35 ] and Corollary 2 of [ 13 ] , respectively, \mathcal{D}^{n}_{k} can be described independently of the variable P in either of the following two ways: \displaystyle\mathcal{D}^{n}_{k} \displaystyle=\left\{X\in\mathbb{S}^{n}:X\succeq\textbf{0},\,\,{\text{rank}\left(X\right)}\leq k,\,\,X\in\{0,1\}^{n\times n}\right\} (2) \displaystyle=\left\{X\in\mathbb{S}^{n}:\hat{X}=\begin{pmatrix}k&{\text{diag}\left(X\right)}^{\top}\\ {\text{diag}\left(X\right)}&X\end{pmatrix}\succeq\textbf{0},\,\,X\in\{0,1\}^{n\times n}\right\}. (3) Using the latter characterization, we obtain the following BSDP formulation of the M k CS problem: \displaystyle\begin{aligned} \alpha_{k}(\mathcal{G})=\max\quad&\left\langle I_{n},X\right\rangle\\ \text{s.t.}\quad&X_{ij}=0\qquad\forall\{i,j\}\in\mathcal{E}\\ &\hat{X}=\begin{pmatrix}k&{\text{diag}\left(X\right)}^{\top}\\ {\text{diag}\left(X\right)}&X\end{pmatrix}\succeq\textbf{0}\\ &X\in\{0,1\}^{n\times n}.\end{aligned} (BSDP k ) We denote the feasible set of ( BSDPk ) by \mathcal{F}_{\eqref{BSDP}} . The binary matrix variable X has the interpretation that a diagonal entry X_{ii}=1 if and only if vertex i\in[n] is assigned a color, and an off-diagonal entry X_{ij}=1 if and only if vertices i,j\in[n] with i\neq j are assigned the same color. The appearance of the constant k in the PSD constraint and the binarity of the matrix variable together ensure that {\text{rank}\left(X\right)}\leq k , or equivalently, that at most k colors are used. Note that ( BSDPk ) is free of color symmetry, whereas ( BLPk ) is not. For k=1 , i.e., the stable set problem, it is sufficient to impose integrality on the diagonal of X to ensure also integrality on the off-diagonal entries. This follows from the nonnegativity of the determinants of the 3\times 3 principle submatrices of \hat{X} , see e.g., Section 3.2 of [ 24 ] . This result does not hold in general for k>1 . For instance, consider the graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with \mathcal{V}=\{1,2,3\} and \mathcal{E}=\{\{2,3\}\} and let k=2 . Then X=\begin{pmatrix}1&1/2&0\\ 1/2&1&0\\ 0&0&0\end{pmatrix} does not satisfy integrality on all off-diagonal entries, while X does satisfy all other constraints of ( BSDPk ). By relaxing the integrality constraints on X in ( BSDPk ) and replacing them with the following bound constraints X\geq\textbf{0}_{n},\quad{\text{diag}\left(X\right)}\leq e_{n}, (4) we obtain our basic SDP relaxation: \displaystyle\begin{aligned} \theta_{k}(\mathcal{G})\mathrel{\mathop{:}}=\max\quad&\left\langle I_{n},X\right\rangle\\ \text{s.t.}\quad&X_{ij}=0\qquad\forall\{i,j\}\in\mathcal{E}\\ &\hat{X}=\begin{pmatrix}k&{\text{diag}\left(X\right)}^{\top}\\ {\text{diag}\left(X\right)}&X\end{pmatrix}\succeq\textbf{0}\\ &X\geq\textbf{0}_{n},\,\,{\text{diag}\left(X\right)}\leq e_{n}.\end{aligned} (SDP k ) We denote the feasible set of ( SDPk ) by \mathcal{F}_{\eqref{SDP}} . The SDP relaxation ( SDPk ) was first proposed in [ 33 ] , where \theta_{k}(\mathcal{G}) is denoted by \theta^{3}_{k}(\mathcal{G}) . It was proved in that paper that ( SDPk ) satisfies the Slater condition. Observe that ( SDPk ) is a Doubly Nonnegative relaxation, since it is an SDP relaxation over the set of nonnegative matrices. Moreover, note that the constraint {\text{diag}\left(X\right)}\leq e_{n} is sufficient to ensure that X\leq J_{n} . This follows from the nonnegativity of the determinants of the 2\times 2 principle submatrices of X . Furthermore, as shown in the following lemma, ( SDPk ) dominates the LP relaxation of ( BLPk ). Lemma 2.1 . For any graph \mathcal{G} and k\in[n-1] , we have that \theta_{k}(\mathcal{G})\leq LP_{k}(\mathcal{G}) , where LP_{k}(\mathcal{G}) denotes the optimal value of the LP relaxation of ( BLPk ). Proof. Let X\in\mathcal{F}_{\eqref{SDP}} . It is not difficult to show that the matrix P\in[0,1]^{n\times k} with P_{ic}=X_{ii}/{k} for i\in[n] and c\in[k] is feasible to the LP relaxation of ( BLPk ), and that its objective value \sum_{i\in[n]}\sum_{c\in[k]}P_{ic} equals \left\langle I_{n},X\right\rangle . In particular, for any \{i,j\}\in\mathcal{E} and c\in[k] , we have P_{ic}+P_{jc}=\frac{1}{k}(X_{ii}+X_{jj})\leq 1 , where the inequality follows from the constraint \left\langle aa^{\top},\hat{X}\right\rangle\geq 0 for a=\begin{pmatrix}1\\ -\mathbbm{1}_{\{i,j\}}\end{pmatrix} , which holds because \hat{X}\succeq\textbf{0} . ∎ 3 Graph parameter \theta_{k}(\mathcal{G}) We consider \theta_{k}(\mathcal{G}) as a graph parameter and derive several of its properties. Our main result is that \theta_{k}(\mathcal{G}) is sandwiched between \alpha_{k}(\mathcal{G}) and the k -clique cover number. Graphs for which these two values coincide for each induced subgraph are known as k -perfect graphs. Since \theta_{k}(\mathcal{G}) can be computed in polynomial time up to fixed precision, it follows that the M k CS problem is also polynomially solvable for k -perfect graphs. 43 introduced the generalized \vartheta -number of \mathcal{G} as an eigenvalue bound for \alpha_{k}(\mathcal{G}) , which can be computed as follows [ 1 ] : \displaystyle\begin{aligned} \vartheta_{k}(\mathcal{G})\mathrel{\mathop{:}}=\max\quad&\left\langle J_{n},Z\right\rangle\\ \text{s.t.}\quad&Z_{ij}=0\qquad\forall\{i,j\}\in\mathcal{E}\\ &\left\langle I_{n},Z\right\rangle=k\\ &Z\succeq\mathbf{0},\,I_{n}-Z\succeq\mathbf{0}.\end{aligned} ( \vartheta_{k} ) 33 strengthened \vartheta_{k}(\mathcal{G}) by adding nonnegativity constraints. The resulting graph parameter is denoted by \vartheta_{k}^{\prime}(\mathcal{G}) , and for k=1 it coincides with the Schrijver number [ 52 ] , which is denoted in the literature by \vartheta^{\prime}(\mathcal{G}) . It is known that \vartheta^{\prime}(\mathcal{G})=\theta_{1}(\mathcal{G}) [ 33 ] . It was conjectured in the same paper that \theta_{k}(\mathcal{G}) is at least as strong as \vartheta^{\prime}_{k}(\mathcal{G}) for all k\geq 1 . The authors of [ 54 ] proved that \theta_{k}(\mathcal{G}) and \vartheta^{\prime}_{k}(\mathcal{G}) coincide for any strongly regular graph with parameters (n,d,\lambda,\mu) and restricted eigenvalues r\geq 0 , s<-1 , provided that k<(n(r+1))/(r+n-d) . Similarly to the (generalized) \vartheta - and \vartheta^{\prime} -numbers, \theta_{k}(\mathcal{G}) can also be regarded as a graph parameter. Let us first relate \theta_{k}(\mathcal{G}) and \theta_{1}(\mathcal{G}) . Lemma 3.1 . For any undirected graph \mathcal{G} with n vertices, and an integer k\in[n-1] , \theta_{k}(\mathcal{G})\leq k\theta_{1}(\mathcal{G}). Proof. The result follows trivially for k=1 . Let k\geq 2 , and let X^{k} be an optimal solution to ( SDPk ). Let X^{1}:=\frac{1}{k}X^{k} , then X^{1} is feasible for (SDP 1 ). Therefore, \theta_{k}(\mathcal{G})=\left\langle I_{n},X^{k}\right\rangle=k\left\langle I_{n},\frac{1}{k}X^{k}\right\rangle=k\left\langle I_{n},X^{1}\right\rangle\leq k\theta_{1}(\mathcal{G}), where the inequality follows from the fact that X^{1} need not be an optimal solution to (SDP 1 ). ∎ Next, we relate \theta_{k}(\mathcal{G}) to the chromatic number of graph \mathcal{G} , denoted by \chi(\mathcal{G}) . Lemma 3.2 . Let \mathcal{G}=(\mathcal{V},\mathcal{E}) be a given graph and k\in\mathbb{N} such that k\geq\chi(\mathcal{G}) , then \theta_{k}(\mathcal{G})=|\mathcal{V}| . Proof. Since k\geq\chi(\mathcal{G}) , we have \alpha_{k}(\mathcal{G})=|\mathcal{V}| , and therefore |\mathcal{V}|\leq\theta_{k}(\mathcal{G}) . The fact that \theta_{k}(\mathcal{G})\leq|\mathcal{V}| trivially follows from the constraint {\text{diag}\left(X\right)}\leq e_{n} . ∎ We summarize the results of the previous lemmas below. Corollary 3.2.1 . For a given graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with n vertices and an integer k\in[n-1] , we have \theta_{k}(\mathcal{G})\leq\min\left\{k\vartheta^{\prime}(\mathcal{G}),|\mathcal{V}|\right\}, where \vartheta^{\prime}(\mathcal{G}) is the Schrijver number. It was shown in [ 54 ] that the sequence \left(\vartheta_{k}(\mathcal{G})\right)_{k} is increasing in k . We show below that \left(\theta_{k}(\mathcal{G})\right)_{k} is non-decreasing in k . Lemma 3.3 . For any graph \mathcal{G} and k\in\mathbb{N} , \theta_{k}(\mathcal{G})\leq\theta_{k+1}(\mathcal{G}). Proof. Let X^{k} be an optimal solution to ( SDPk ). It is not difficult to verify that X^{k} is also a feasible solution to the SDP relaxation (SDP_{k+1}) . Therefore, \theta_{k}(\mathcal{G})=\left\langle I_{n},X^{k}\right\rangle\leq\theta_{k+1}(\mathcal{G}) . ∎ The following summarizes the relationships among several graph parameters: \displaystyle\alpha_{k}(\mathcal{G})\leq\theta_{k}(\mathcal{G})\leq k\vartheta^{\prime}(\mathcal{G})\leq k\vartheta(\mathcal{G})\leq\chi_{k}(\overline{\mathcal{G}}), (5) where \overline{\mathcal{G}} denotes the complement graph of \mathcal{G} , and \chi_{k}(\overline{\mathcal{G}}) the minimum number of colors needed for a valid k -multicoloring of \overline{\mathcal{G}} . Recall that a valid k –multicoloring of a graph is an assignment of k distinct colors to each vertex in the graph such that two adjacent vertices are assigned disjoint sets of colors. Clearly, \chi_{1}(\mathcal{G})=\chi(\mathcal{G}). While the first three inequalities in ( 5 ) follow from the previous discussion, for the proof of the last inequality, see e.g., [ 54 ] . Note that the parameter \chi_{k}(\overline{\mathcal{G}}) can be larger than the number of vertices in \mathcal{G} , while \alpha_{k}(\mathcal{G}) and \theta_{k}(\mathcal{G}) are bounded above by n . Therefore, one may ask whether there is a more appropriate graph parameter than \chi_{k}(\overline{\mathcal{G}}) that serves as an upper bound on \theta_{k}(\mathcal{G}) , thereby forming a sandwich relation. We consider here the following parameter \displaystyle\Psi_{k}({\mathcal{G}}):=\min\left\{k\chi(\mathcal{G}-\mathcal{S})+|\mathcal{S}|\,:\,\mathcal{S}\subseteq\mathcal{V}\right\}, (6) that was studied by 19 , and 18 . Here, \mathcal{G}-\mathcal{S} denotes the subgraph of \mathcal{G} induced by \mathcal{V}\setminus\mathcal{S} . Clearly, \Psi_{k}({\mathcal{G}})\leq n for any k\geq 1 , and \Psi_{1}({\mathcal{G}})=\chi({\mathcal{G}}) . 44 also proposed replacing \chi_{k}(\overline{\mathcal{G}}) with \Psi_{k}(\overline{\mathcal{G}}) in the sandwich inequality \alpha_{k}(\mathcal{G})\leq\vartheta_{k}(\mathcal{G})\leq\chi_{k}(\overline{\mathcal{G}}) , but they were unable to prove that \vartheta_{k}({\mathcal{G}})\leq\Psi_{k}(\overline{\mathcal{G}}) . 47 introduced a spectral nonconvex graph parameter, which is sandwiched between \alpha_{k}(\mathcal{G}) and \Psi_{k}(\overline{\mathcal{G}}) and is difficult to compute. In the sequel, we show that \theta_{k}(\mathcal{G}) is bounded above by \Psi_{k}(\overline{\mathcal{G}}) , resulting in the desired sandwich relation. Let us first note that \Psi_{k}(\overline{\mathcal{G}})=\min\left\{k\chi(\overline{\mathcal{G}}-\mathcal{S})+|\mathcal{S}|\,:\,\mathcal{S}\subseteq\mathcal{V}\right\}=\min\left\{k\overline{\chi}({\mathcal{G}-\mathcal{S}})+|\mathcal{S}|\,:\,\mathcal{S}\subseteq\mathcal{V}\right\}, where \overline{\chi}(\mathcal{G}) denotes the clique cover number of \mathcal{G} . Here we exploit the fact that \overline{\chi}(\mathcal{H})=\chi(\overline{\mathcal{H}}) for any graph \mathcal{H} . Therefore, \Psi_{k}(\overline{\mathcal{G}}) may be seen as a generalization of the clique cover number. We therefore refer to the minimization problem above as the k -clique cover problem. First, we prove the following result. Proposition 3.4 . Let \mathcal{G}=(\mathcal{V},\mathcal{E}) be a graph with n vertices, and let \mathcal{S}\subseteq\mathcal{V} . Then, \theta_{k}(\mathcal{G})\leq\theta_{k}(\mathcal{G}-\mathcal{S})+|\mathcal{S}|, for any k\in[n-1] . Proof. If \mathcal{S}=\mathcal{V} , the inequality follows trivially. Let us therefore assume that \mathcal{S}\neq\mathcal{V} . Let X be an optimal solution to ( SDPk ), and let X_{\mathcal{S}} and X_{\mathcal{V}-\mathcal{S}} be the submatrices of X indexed by the vertices in the set \mathcal{S} and \mathcal{V}\setminus\mathcal{S} , respectively. It is not difficult to verify that X_{\mathcal{V}-\mathcal{S}} is feasible for the SDP relaxation ( SDPk ) induced by \mathcal{V}\setminus\mathcal{S} . Now, we consider the following two cases. Assume that k1 have been identified. 18 proved that comparability graphs are k -perfect for every integer k\geq 1 , and so are their complements, as shown by 19 . A graph that is k -perfect for every integer k\geq 1 is called a totally perfect graph. 40 showed that line graphs of bipartite graphs are totally perfect, and 3 proved that all balanced graphs are totally perfect. Our result resolves the problem of finding an efficient algorithm for computing \alpha_{k}(\mathcal{G}) and \Psi_{k}(\overline{\mathcal{G}}) for k -perfect graphs where k>1 . 20 showed that there is a polynomial time algorithm for computing these parameters for perfect graphs, thus for the case k=1 . To the best of our knowledge, no such result was previously known for k>1 . Theorem 3.6 . Let \mathcal{G} be a k -perfect graph and k\geq 1 . Then, \alpha_{k}(\mathcal{G}) and \Psi_{k}(\overline{\mathcal{G}}) can be computed in polynomial time up to fixed precision. 4 Valid inequalities In this section, we derive several families of valid inequalities that strengthen ( SDPk ). We first propose generalized BQP inequalities (Section 4.1 ), and then derive generalized rank inequalities (Section 4.2 ). We further consider computationally tractable special cases of our new valid inequalities that concern triangles (Section 4.1.1 ), cliques (Section 4.2.1 ) and odd holes (Section 4.2.2 ). 4.1 Generalized Boolean quadric polytope inequalities We first present valid inequalities that generalize the cut inequalities and clique inequalities of 48 for the BQP. Namely, we prove that the following inequalities are valid for the set \mathcal{D}^{n}_{k} , where k\in[n-1] : \displaystyle\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S}^{\prime}}X_{ij}\leq\sum_{i\in\mathcal{S}^{\prime}}X_{ii}+\sum_{i,j\in\mathcal{S}:i0 times in \mathcal{S} . Indeed, if some color were to be assigned to fewer than \sum_{i\in\mathcal{S}}X_{ii}-r_{k-1}(\mathcal{S}) vertices, then the total number of colored vertices in \mathcal{S} would be less than \sum_{i\in\mathcal{S}}X_{ii} , since the remaining k-1 colors can together cover at most r_{k-1}(\mathcal{S}) vertices. Thus, depending on the number of colored vertices in \mathcal{S} , if vertex \ell is colored, then \ell has the same color as at least \max\left\{\sum_{i\in\mathcal{S}}X_{ii}-r_{k-1}(\mathcal{S}),0\right\} of the vertices in \mathcal{S} . Therefore, we have \displaystyle\sum_{i\in\mathcal{S}}X_{i\ell} \displaystyle\geq\max\left\{\sum_{i\in\mathcal{S}}X_{ii}-r_{k-1}(\mathcal{S}),0\right\}X_{\ell\ell}\geq\left(\sum_{i\in\mathcal{S}}X_{ii}-r_{k-1}(\mathcal{S})\right)X_{\ell\ell} \displaystyle\geq\left(\sum_{i\in\mathcal{S}}X_{ii}-r_{k-1}(\mathcal{S})\right)-\left(r_{k}(\mathcal{S})-r_{k-1}(\mathcal{S})\right)\left(1-X_{\ell\ell}\right), where we used for the last inequality that \sum_{i\in\mathcal{S}}X_{ii}\leq r_{k}(\mathcal{S}) and that X_{\ell\ell}\in\{0,1\} . Rewriting the obtained inequality gives the desired result. ∎ Note that it is intractable to add all generalized rank inequalities ( 11 )-( 14 ) as cuts to strengthen ( SDPk ), since there are exponentially many such inequalities, and, moreover, computing the \kappa -rank of an arbitrary set \mathcal{S} is \mathcal{NP} -hard. Therefore, in the following sections we restrict attention to sets \mathcal{S} that are cliques and odd holes, as these sets admit explicit expressions for the \kappa -ranks. In our computational experiments, we further limit the size of the cliques and odd holes considered. 4.2.1 Generalized clique inequalities This section concerns the generalized rank inequalities ( 11 )-( 14 ) for subsets of \mathcal{V} that are cliques. Recall that a clique in \mathcal{G} is a set of vertices \mathcal{Q}\subseteq\mathcal{V} that induces a complete subgraph, i.e., every pair of vertices in \mathcal{Q} is adjacent in \mathcal{G} . For any clique \mathcal{Q}\subseteq\mathcal{V} , we have that r_{\kappa}(\mathcal{Q})=\min\{\kappa,|\mathcal{Q}|\} for each \kappa\in[k] . We first show that inequalities ( 11 ) and ( 12 ) for cliques are already implied by the constraints of ( SDPk ). Lemma 4.6 . Let X\in\mathcal{F}_{\eqref{SDP}} and let \mathcal{Q}\subseteq\mathcal{V} be a clique. Then \sum_{i\in\mathcal{Q}}X_{ii}\leq\min\{k,|\mathcal{Q}|\} and \sum_{i,j\in\mathcal{Q}:ik. (17) Note that inequalities ( 17 ) are also a special case of generalized BQP inequalities ( 8 ) (take \mathcal{S}=\mathcal{Q}\cup\mathcal{Q}^{\prime} and use Lemma 4.6 ). Moreover, observe that inequalities ( 16 ) are a special case of inequalities ( 17 ). Preliminary experiments confirmed that inequalities ( 17 ) result in stronger bounds than inequalities ( 16 ) alone. As implied by the following proposition, when using generalized clique inequalities ( 15 ) as cuts to strengthen ( SDPk ), it suffices to consider these inequalities for maximal cliques only. Proposition 4.7 . Let X\in\mathcal{F}_{\eqref{SDP}} satisfy inequality ( 15 ) for a clique \mathcal{Q}\subseteq\mathcal{V} and an external vertex \ell\in\mathcal{V}\setminus\mathcal{Q} . Then, for each h\in\mathcal{Q} , X also satisfies inequality ( 15 ) for the clique \mathcal{Q}\setminus\{h\} and the vertex \ell . Proof. Using that \sum_{i\in\mathcal{Q}}X_{i\ell}\leq X_{\ell\ell} and X_{h\ell}\geq 0 , we find that \sum_{i\in\mathcal{Q}\setminus\{h\}}X_{i\ell}=\sum_{i\in\mathcal{Q}}X_{i\ell}-X_{h\ell}\leq X_{\ell\ell}-X_{h\ell}\leq X_{\ell\ell} , which is exactly inequality ( 15 ) for \mathcal{Q}\setminus\{h\} and \ell . ∎ Furthermore, once inequalities ( 15 ) have been added to ( SDPk ), it is sufficient to consider inequalities ( 17 ) for pairs of maximal cliques, as implied by the next proposition. Proposition 4.8 . Let X\in\mathcal{F}_{\eqref{SDP}} satisfy inequality ( 17 ) for disjoint cliques \mathcal{Q},\mathcal{Q}^{\prime}\subseteq\mathcal{V} . Suppose that X satisfies inequality ( 15 ) for the clique \mathcal{Q} and a vertex h\in\mathcal{Q}^{\prime} . Then, X also satisfies inequality ( 17 ) for the cliques \mathcal{Q} and \mathcal{Q}^{\prime}\setminus\{h\} . Proof. Using that \sum_{i\in\mathcal{Q}}X_{ii}+\sum_{j\in\mathcal{Q}^{\prime}}X_{jj}\leq\sum_{i\in\mathcal{Q}}\sum_{j\in\mathcal{Q}^{\prime}}X_{ij}+k and \sum_{i\in\mathcal{Q}}X_{ih}\leq X_{hh} , we find \sum_{i\in\mathcal{Q}}X_{ii} +\sum_{j\in\mathcal{Q}^{\prime}\setminus\{h\}}X_{jj}=\sum_{i\in\mathcal{Q}}X_{ii}+\sum_{j\in\mathcal{Q}^{\prime}}X_{jj}-X_{hh}\leq\sum_{i\in\mathcal{Q}}\sum_{j\in\mathcal{Q}^{\prime}}X_{ij}+k-X_{hh}=\sum_{i\in\mathcal{Q}}\sum_{j\in\mathcal{Q}^{\prime}\setminus\{h\}}X_{ij}+\sum_{i\in\mathcal{Q}}X_{ih}+k-X_{hh}=\sum_{i\in\mathcal{Q}}\sum_{j\in\mathcal{Q}^{\prime}\setminus\{h\}}X_{ij}+k+\left(\sum_{i\in\mathcal{Q}}X_{ih}-X_{hh}\right)\leq\sum_{i\in\mathcal{Q}}\sum_{j\in\mathcal{Q}^{\prime}\setminus\{h\}}X_{ij}+k , which is exactly inequality ( 17 ) for \mathcal{Q} and \mathcal{Q}^{\prime}\setminus\{h\} . ∎ Note that this proposition also applies when interchanging the roles of \mathcal{Q} and \mathcal{Q}^{\prime} . 4.2.2 Generalized odd-hole inequalities We now consider the generalized rank inequalities ( 11 )-( 14 ) for subsets of \mathcal{V} that are odd holes. We first recall some definitions. A cycle in \mathcal{G} is a set of vertices \mathcal{C}=\{v_{1},v_{2},\ldots,v_{|\mathcal{C}|}\}\subseteq\mathcal{V} with |\mathcal{C}|\geq 3 such that \{v_{i},v_{i+1}\}\in\mathcal{E} for all i\in[|\mathcal{C}|-1] and \{v_{|\mathcal{C}|},v_{1}\}\in\mathcal{E} . Additional edges in a cycle that connect nonconsecutive vertices are called chords. A chordless cycle is called a hole. A cycle or hole is called odd (respectively even) if its cardinality is odd (respectively even). Odd holes of cardinality 3 are also cliques, so we only consider here odd holes of cardinality at least 5 . Observe that for any odd hole \mathcal{C}\subseteq\mathcal{V} , the maximum number of vertices that can be colored in \mathcal{G}[\mathcal{C}] with \kappa\in[k] colors equals r_{\kappa}(\mathcal{C})=\min\left\{\frac{|\mathcal{C}|-1}{2}\kappa,|\mathcal{C}|\right\}=\begin{cases}\frac{|\mathcal{C}|-1}{2}&\text{if $\kappa=1$}\\ |\mathcal{C}|-1&\text{if $\kappa=2$}\\ |\mathcal{C}|&\text{otherwise}.\end{cases} In preliminary experiments, we considered the strength of ( SDPk ) when adding inequalities ( 11 )-( 14 ) for odd holes. Among these inequalities, the ones of type ( 13 ) led to the largest improvements in the SDP bounds. Motivated by this, we focus on these inequalities here. In the following, we will refer to them as generalized odd-hole inequalities , and they read as follows: \displaystyle\sum_{i\in\mathcal{C}}X_{i\ell}\leq\frac{|\mathcal{C}|-1}{2}X_{\ell\ell} \displaystyle\forall\text{ odd hole }\mathcal{C}\subseteq\mathcal{V},\ell\in\mathcal{V}\setminus\mathcal{C}. (18) These inequalities were first proposed by 50 for SDP relaxations for the stable set problem. Let us briefly consider even holes. For any even hole \mathcal{C}\subseteq\mathcal{V} we have that r_{1}(\mathcal{C})=\frac{|\mathcal{C}|}{2} and r_{\kappa}(\mathcal{C})=|\mathcal{C}| for all \kappa\geq 2 . Therefore, for any even hole \mathcal{C} we can replace the factor \frac{|\mathcal{C}|-1}{2} in inequalities ( 18 ) by \frac{|\mathcal{C}|}{2} to obtain valid inequalities. However, as proven in the next proposition, such inequalities are already implied by triangle inequalities ( 9 ). Proposition 4.9 . Let X\in\mathcal{F}_{\eqref{SDP}} satisfy all triangle inequalities ( 9 ). Let \mathcal{C}\subseteq\mathcal{V} , |\mathcal{C}|\geq 4 be an even hole and let \ell\in\mathcal{V}\setminus\mathcal{C} be an external vertex. Then X satisfies \sum_{i\in\mathcal{C}}X_{i\ell}\leq\frac{|\mathcal{C}|}{2}X_{\ell\ell} . Proof. Without loss of generality, we can label the vertices of \mathcal{C} as 1,2,\ldots,|\mathcal{C}| so that \{i,i+1\}\in\mathcal{E} for each odd i\in\{1,\ldots,|\mathcal{C}|-1\} . Therefore, for each such i , we can combine the triangle inequality ( 9 ) for triplet \{i,i+1,\ell\} with the constraint X_{i,i+1}=0 to obtain that X_{i\ell}+X_{i+1,\ell}\leq X_{\ell\ell} . Summing all \frac{|\mathcal{C}|}{2} such inequalities, we obtain \sum_{i\in\mathcal{C}}X_{i\ell}\leq\frac{|\mathcal{C}|}{2}X_{\ell\ell} . ∎ In a similar vein, note that inequalities ( 18 ) also hold for odd cycles containing chords, as such cycles \mathcal{C} satisfy r_{1}(\mathcal{C})\leq\frac{|\mathcal{C}|-1}{2} . However, we do not need to consider such inequalities to strengthen ( SDPk ), as implied by the following proposition. Proposition 4.10 . Let X\in\mathcal{F}_{\eqref{BSDP}} , let \mathcal{C}\subseteq\mathcal{V} be an odd cycle with |\mathcal{C}|\geq 5 that contains at least one chord, and let \ell\in\mathcal{V}\setminus\mathcal{C} be an external vertex. Then, the valid inequality \sum_{i\in\mathcal{C}}X_{i\ell}\leq\frac{|\mathcal{C}|-1}{2}X_{\ell\ell} can be expressed as the sum of an odd-hole inequality of the form ( 18 ) and a number of triangle inequalities ( 9 ). Proof. Without loss of generality, we can label the vertices of \mathcal{C} as 1,2,\dots,|\mathcal{C}| so that \{i,i+1\}\in\mathcal{E} for each i\in\mathcal{C} (where we use the convention that addition is taken modulo |\mathcal{C}| when dealing with cycles) and that \{1,p\}\in\mathcal{E} for some even p\in\{4,\ldots,|\mathcal{C}|-1\} . Note that \mathcal{C}^{\prime}=\{p,\ldots,|\mathcal{C}|,1\} is an odd cycle, so \sum_{i\in\{p,\ldots,|\mathcal{C}|,1\}}X_{i\ell}\leq\frac{|\mathcal{C}|-p+1}{2}X_{\ell\ell} . Moreover, for each even i\in\{2,\ldots,p-2\} we can combine the triangle inequality ( 9 ) for triplet \{i,i+1,\ell\} with the constraint X_{i,i+1}=0 to obtain that X_{i\ell}+X_{i+1,\ell}\leq X_{\ell\ell} . Summing all \frac{p-2}{2} such inequalities and the inequality for the odd cycle \mathcal{C}^{\prime} , we obtain \sum_{i\in\mathcal{C}}X_{i\ell}\leq\frac{|\mathcal{C}|-1}{2}X_{\ell\ell} . If \mathcal{C}^{\prime} is chordless, the proposition follows. Otherwise, the same decomposition can be applied recursively. ∎ 5 The cutting-plane ADMM This section describes the CP-ADMM that is used to compute valid upper bounds on \alpha_{k}(\mathcal{G}) . In Section 5.1 , we present the ADMM scheme for solving SDP relaxations of ( BSDPk ), and in Section 5.2 , we explain how this scheme is embedded into a cutting-plane framework. Whereas our implementation incorporates the valid inequalities derived in the previous section, our algorithm is described independently of the specific inequalities used, emphasizing that the CP-ADMM can handle any valid inequality of the form \left\langle A,X\right\rangle\leq b . 5.1 The ADMM scheme At a given iteration of the CP-ADMM, we consider a fixed index set \mathcal{I} of valid inequalities for ( BSDPk ), and apply the ADMM to solve \theta_{k}^{\mathcal{I}}(\mathcal{G})\mathrel{\mathop{:}}=\max\left\{\left\langle I_{n},X\right\rangle:X\in\mathcal{F}_{\eqref{SDP}},\left\langle A_{i},X\right\rangle\leq b_{i}\,\,\forall i\in\mathcal{I}\right\}. (SDP k - \mathcal{I} ) To apply the ADMM, we first reformulate ( SDPk- I ) by separating the affine constraints from the PSD constraint. To this end, let \hat{\mathcal{X}}_{\mathcal{I}}\mathrel{\mathop{:}}=\left\{\begin{pmatrix}k&{\text{diag}\left(X\right)}^{\top}\\ {\text{diag}\left(X\right)}&X\end{pmatrix}\in\mathbb{S}^{n+1}:X_{ij}=0\,\,\forall\{i,j\}\in\mathcal{E},\,\,\textbf{0}_{n}\leq X\leq J_{n},\,\,\left\langle A_{i},X\right\rangle\leq b_{i}\,\,\forall i\in\mathcal{I}\right\}, (19) and let \hat{I}\mathrel{\mathop{:}}=\begin{pmatrix}0&0_{n}^{\top}\\ 0_{n}&I_{n}\end{pmatrix} , from where it follows that \theta_{k}^{\mathcal{I}}(\mathcal{G})=\max\left\{\left\langle\hat{I},\hat{X}\right\rangle:\hat{X}=Y,\,\,\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}},\,\,Y\in\mathbb{S}_{+}^{n+1}\right\}. (20) Note that \hat{\mathcal{X}}_{\mathcal{I}} includes the redundant upper bound constraints X_{ij}\leq 1 for off-diagonal entries i,j\in[n] with i\neq j . Despite being redundant for ( SDPk- I ), these constraints do fasten the convergence of the ADMM, see e.g., [ 10 , 11 , 37 , 46 ] . Next, we consider the augmented Lagrangian function of ( 20 ) with respect to the coupling constraint \hat{X}=Y , which is defined as L_{\beta}(\hat{X},Y,\Lambda)\mathrel{\mathop{:}}=\left\langle\hat{I},\hat{X}\right\rangle-\left\langle\Lambda,\hat{X}-Y\right\rangle-\frac{\beta}{2}\left\lVert\hat{X}-Y\right\rVert^{2}, (21) where \Lambda\in\mathbb{S}^{n+1} is the dual variable associated to the coupling constraint \hat{X}=Y , and \beta>0 is a fixed penalty parameter (we specify our parameter values in Table 1 in Section 7 ). Starting from an initial triple (\hat{X}^{0},Y^{0},\Lambda^{0}) , and given some stepsize parameter \gamma , the ADMM iteratively updates the current triple (\hat{X}^{t},Y^{t},\Lambda^{t}) using the following update scheme: \displaystyle\hat{X}^{t+1}\mathrel{\mathop{:}}= \displaystyle\text{arg max}_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}L_{\beta}(\hat{X},Y^{t},\Lambda^{t}) (22) \displaystyle Y^{t+1}\mathrel{\mathop{:}}= \displaystyle\text{arg max}_{Y\in\mathbb{S}_{+}^{n+1}}L_{\beta}(\hat{X}^{t+1},Y,\Lambda^{t}) (23) \displaystyle\Lambda^{t+1}\mathrel{\mathop{:}}= \displaystyle\Lambda^{t}+\gamma\cdot\beta(\hat{X}^{t+1}-Y^{t+1}). (24) When \gamma\in(0,\frac{1+\sqrt{5}}{2}) , the iterates (\hat{X}^{t},Y^{t}) converge with rate \mathcal{O}(1/t) to an optimal solution of ( 20 ), see [ 23 ] . The efficiency of the ADMM depends on the complexity of the subproblems ( 22 ) and ( 23 ). It can be shown that these problems reduce to the following projection problems, see [ 46 ] : \displaystyle\text{arg max}_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}L_{\beta}(\hat{X},Y^{t},\Lambda^{t})=\text{arg min}_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}\left\lVert\hat{X}-\left(Y^{t}+\frac{1}{\beta}\left(\hat{I}-\Lambda^{t}\right)\right)\right\rVert^{2}=\mathcal{P}_{\hat{\mathcal{X}}_{\mathcal{I}}}\left(Y^{t}+\frac{1}{\beta}\left(\hat{I}-\Lambda^{t}\right)\right) (25) \displaystyle\text{arg max}_{Y\in\mathbb{S}^{n+1}_{+}}L_{\beta}(\hat{X}^{t+1},Y,\Lambda^{t})=\text{arg min}_{Y\in\mathbb{S}^{n+1}_{+}}\left\lVert Y-\left(\hat{X}^{t+1}+\frac{1}{\beta}\Lambda^{t}\right)\right\rVert^{2}=\mathcal{P}_{\mathbb{S}^{n+1}_{+}}\left(\hat{X}^{t+1}+\frac{1}{\beta}\Lambda^{t}\right). (26) The projection of a symmetric matrix onto \mathbb{S}^{n+1}_{+} is obtained through a spectral decomposition. This decomposition is carried out in single precision instead of double precision to reduce its computational cost, see [ 53 ] . We next discuss the projection onto \hat{\mathcal{X}}_{\mathcal{I}} . Note that every matrix \hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}} is uniquely determined by the entries \hat{X}_{ij} with 1\leq i\leq j\leq n,\{i,j\}\not\in\mathcal{E} . Therefore, we can reduce the projection problem onto \hat{\mathcal{X}}_{\mathcal{I}} to a weighted projection problem (see Section 1.2 ) where we only consider the m\mathrel{\mathop{:}}=n+\binom{n}{2}-|\mathcal{E}| free entries. Concretely, given a matrix \hat{U}=\begin{pmatrix}u_{00}&u_{0}^{\top}\\ u_{0}&U\end{pmatrix}\in\mathbb{S}^{n+1} , its projection onto \hat{\mathcal{X}}_{\mathcal{I}} proceeds as follows: 1. To account for the zeroth row and column, replace the diagonal of U by \frac{1}{3}{\text{diag}\left(U\right)}+\frac{2}{3}u_{0} , and then construct the vector u\in\mathbb{R}^{m} that contains only the free entries of the newly obtained matrix. 2. Find u^{\prime}\mathrel{\mathop{:}}=\mathcal{P}^{w}_{\mathcal{X}^{vec}_{\mathcal{I}}}(u) , where weight vector w\in\{2,3\}^{m} assigns weight 2 to upper-triangular entries (accounting for the lower-triangular entries) and weight 3 to diagonal entries (accounting for the entries on the zeroth row and column), and \mathcal{X}^{vec}_{\mathcal{I}}\mathrel{\mathop{:}}=\left\{x\in\mathbb{R}^{m}:0_{m}\leq x\leq e_{m},\quad a_{i}^{\top}x\leq b_{i}\quad\forall i\in\mathcal{I}\right\}. (27) The vectors a_{i}\in\mathbb{R}^{m} are obtained from the matrices A_{i}\in\mathbb{S}^{n+1} . 3. Map the vector u^{\prime}\in\mathcal{X}^{vec}_{\mathcal{I}} to the corresponding matrix in \hat{\mathcal{X}}_{\mathcal{I}} . To find \mathcal{P}^{w}_{\mathcal{X}^{vec}_{\mathcal{I}}}(u) , we first rewrite \mathcal{X}^{vec}_{\mathcal{I}} as the intersection of simpler sets: \mathcal{X}^{vec}_{\mathcal{I}}=[0,1]^{m}\cap\left(\bigcap_{i\in\mathcal{I}}\mathcal{H}_{i}\right),\quad\text{where }\mathcal{H}_{i}=\left\{x\in\mathbb{R}^{m}:a_{i}^{\top}x\leq b_{i}\right\}\quad\forall i\in\mathcal{I}. (28) These sets are all easy to project onto. Indeed, the weighted projection onto the box is given by \mathcal{P}^{w}_{[0,1]^{m}}(x)=\mathcal{P}_{[0,1]^{m}}(x)=\left(\min\{\max\{x_{j},0\},1\}\right)_{j\in[m]}, (29) and for each valid inequality i\in\mathcal{I} , the weighted projection onto its corresponding halfspace is given by \mathcal{P}^{w}_{\mathcal{H}_{i}}(x)=x-\frac{\max\{a_{i}^{\top}x-b_{i},0\}}{a_{i}^{\top}{\text{Diag}\left(w\right)}^{-1}a_{i}}{\text{Diag}\left(w\right)}^{-1}a_{i}. (30) When \mathcal{I}=\emptyset , we have that \mathcal{X}^{vec}_{\mathcal{I}}=[0,1]^{m} , so the projection is straightforward. Otherwise, we apply Dykstra’s cyclic projection algorithm [ 5 ] , which is an iterative algorithm for projecting onto the intersection of convex sets. This algorithm was successfully used within the CP-ADMM algorithms from [ 10 , 12 , 11 ] . Importantly, these papers accelerate Dykstra’s algorithm by partitioning the valid inequalities into clusters of non-overlapping inequalities so that each iteration of Dykstra’s algorithm requires only one projection per cluster, rather than one projection per inequality. We follow this approach, and refer to the aforementioned papers for the details. 5.2 The cutting-plane framework We are now ready to present the full algorithm in which the ADMM is embedded in a cutting-plane framework, see Algorithm 1 . Algorithm 1 CP-ADMM 1: \mathcal{G}=(\mathcal{V},\mathcal{E}) , k , parameter values from Table 1 in Section 7 2: Initialization: set \hat{X}^{0}\leftarrow\begin{pmatrix}k&e_{n}^{\top}\\ e_{n}&I_{n}\end{pmatrix} , Y^{0}\leftarrow\begin{pmatrix}k&e_{n}^{\top}\\ e_{n}&I_{n}\end{pmatrix} , \Lambda^{0}\leftarrow\mathbf{0}_{n+1} , t\leftarrow 0 , \mathcal{I}\leftarrow\emptyset 3: while the outer stopping criteria are not met do \triangleright see Section 5.2.1 4: while the inner stopping criteria are not met do \triangleright see Section 5.2.1 5: \hat{X}^{t+1}\leftarrow\mathcal{P}_{\hat{\mathcal{X}}_{\mathcal{I}}}\left(Y^{t}+\frac{1}{\beta}\left(\hat{I}-\Lambda^{t}\right)\right) 6: Y^{t+1}\leftarrow\mathcal{P}_{\mathbb{S}^{n+1}_{+}}\left(\hat{X}^{t+1}+\frac{1}{\beta}\Lambda^{t}\right) 7: \Lambda^{t+1}\leftarrow\Lambda^{t}+\gamma\cdot\beta(\hat{X}^{t+1}-Y^{t+1}) 8: t\leftarrow t+1 9: end 10: UB\leftarrow\max_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}\left\langle\hat{I}-\mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t}),\hat{X}\right\rangle \triangleright see Section 5.2.2 11: Identify inequalities that are violated by \hat{X}^{t} and add a selection of those to \mathcal{I} \triangleright see Section 5.2.3 12: end 13: UB , \hat{X}^{t} At each iteration of the outer while-loop (further referred to as an outer iteration ), we apply the ADMM to approximately solve ( SDPk- I ) for a given set of valid inequalities \mathcal{I} . The ADMM is executed within the inner while-loop until its stopping criteria are met (see Section 5.2.1 ), yielding a final ADMM iterate (\hat{X}^{t},Y^{t},\Lambda^{t}) for the current set \mathcal{I} . Subsequently, we check whether \hat{X}^{t} violates any valid inequalities that are not yet included in \mathcal{I} . If so, a selection of those is added to \mathcal{I} (see Section 5.2.3 ), after which we apply the ADMM to solve the strengthened relaxation in the next outer iteration. This procedure is repeated until some stopping criterion for the outer while-loop is met (see Section 5.2.1 ). Along the way, we find stronger valid upper bounds on \alpha_{k}(\mathcal{G}) using a method that is described in Section 5.2.2 . The algorithm is initialized with \mathcal{I}=\emptyset , meaning that the first outer iteration amounts to solving ( SDPk ). This initial iteration is significantly simpler than the subsequent ones, as the projection onto \mathcal{X}^{vec}_{\emptyset} is a projection onto the box and does not require Dykstra’s cyclic projection algorithm. Therefore, initially the most time-consuming step is the projection onto \mathbb{S}^{n+1}_{+} , but once we start adding cuts, the bottleneck becomes Dykstra’s algorithm. In order to improve computational efficiency, we employ a warm-start strategy where each outer iteration is initialized with the final solution from the previous outer iteration. 5.2.1 Stopping criteria We terminate an inner while-loop when the primal and dual residual satisfy \max\left\{\frac{\left\lVert X^{t+1}-Y^{t+1}\right\rVert}{1+\left\lVert X^{t+1}\right\rVert},\beta\frac{\left\lVert X^{t+1}-X^{t}\right\rVert}{1+\left\lVert X^{t+1}\right\rVert}\right\}\leq\varepsilon_{\texttt{ADMM}}, see e.g., [ 46 ] , or when we reach a maximum of maxInnerIter iterations for the inner while-loop. In the final outer iteration, we decrease \varepsilon_{\texttt{ADMM}} (see also [ 11 ] ) and increase maxInnerIter to obtain a more accurate final valid upper bound. We terminate the outer while-loop (and thus the entire algorithm) when (i) the current valid upper bound rounded down to the nearest integer equals some known lower bound, (ii) the improvement of the current valid upper bound over the previous one is less than minImpr , (iii) there are fewer than minIneq violated inequalities, or (iv) a time limit timeLimitGlobal is reached. 5.2.2 Valid upper bounds We obtain valid upper bounds on \alpha_{k}(\mathcal{G}) from the ADMM’s output using a procedure proposed by 46 . The dual function of ( 20 ), with dual variable \Lambda\in\mathbb{S}^{n+1}_{-} , is given by d(\Lambda)\mathrel{\mathop{:}}=\max_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}},Y\in\mathbb{S}^{n+1}_{+}}\left\langle\hat{I},\hat{X}\right\rangle-\left\langle\Lambda,\hat{X}-Y\right\rangle=\max_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}\left\langle\hat{I}-\Lambda,\hat{X}\right\rangle. (31) It follows from weak duality that d(\Lambda)\geq\theta_{k}^{\mathcal{I}}(\mathcal{G}) for any \Lambda\in\mathbb{S}^{n+1}_{-} . In particular, this holds for \Lambda=\mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t}) , where \Lambda^{t} is any intermediate iterate of the dual variable in the ADMM. Note that d(\mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t})) can be computed in polynomial time as \max_{\hat{X}\in\hat{\mathcal{X}}_{\mathcal{I}}}\left\langle\hat{I}-\mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t}),\hat{X}\right\rangle is a linear program and \mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t}) can be found through a spectral decomposition of \Lambda^{t} . When \mathcal{I}=\emptyset , this linear program has a closed-form solution, namely the matrix \hat{X}=\begin{pmatrix}k&{\text{diag}\left(X\right)}^{\top}\\ {\text{diag}\left(X\right)}&X\end{pmatrix} with X given by X_{ij}=\begin{cases}0&\text{if }\{i,j\}\in\mathcal{E},\\ \mathbbm{1}_{\{C_{ii}+2C_{i0}>0\}}&\text{if }i=j,\\ \mathbbm{1}_{\{C_{ij}>0\}}&\text{otherwise,}\end{cases}\quad\forall i,j\in[n], (32) where C=\hat{I}-\mathcal{P}_{\mathbb{S}^{n+1}_{-}}(\Lambda^{t}) . 5.2.3 Cut separation and selection We consider the following classes of valid inequalities and corresponding separation procedures: • Generalized triangle inequalities ( 9 ) and ( 10 ): we enumerate all \binom{n}{3} triplets of vertices. • Generalized clique inequalities ( 15 ) and ( 17 ): to keep separation tractable, we initially restrict to maximal cliques up to size 5 and all cliques of size 6 , where our focus on maximal cliques is justified by Propositions 4.7 and 4.8 . We enumerate these cliques using a variant of the Bron-Kerbosch algorithm [ 6 ] with a time limit timeLimitCliques . For inequalities ( 15 ) we consider at most maxCliques cliques per outer iteration (where we randomly select a subset of the cliques if there are more than maxCliques options). Similarly, for inequalities ( 17 ) we consider at most maxCliquePairs pairs of cliques per outer iteration. Whenever we identify a violated inequality of the form ( 15 ) for a non-maximal clique \mathcal{Q} of size 6 and external vertex \ell , we greedily extend the clique to a larger clique to obtain a stronger cut. Namely, starting from \mathcal{Q} , we iteratively add the vertex i with the highest value of X_{i\ell} among the vertices that are adjacent to all vertices in the current clique, continuing until the clique is maximal. • Generalized odd-hole inequalities ( 18 ): to keep separation tractable, we restrict to 5 -holes. Recall from Propositions 4.9 and 4.10 that we do not need to consider even holes or cycles with chords. We use a time limit timeLimitHoles for enumerating the 5 -holes, and consider at most maxHoles 5-holes per outer iteration. At every outer iteration of the CP-ADMM, we add up to maxIneq of the most violated inequalities, where an inequality only counts as violated if its violation is at least minViol . Preliminary experiments showed that the generalized clique inequalities ( 15 ) are the most effective cuts among those considered. Therefore, we implemented a two-phase approach in which we first consider only inequalities ( 15 ). Once either the improvement of the current valid upper bound over the previous one is less than minImprPhase1 or there are fewer than minIneqPhase1 violated inequalities of type ( 15 ), we transition to a second phase where the remaining inequality types are also considered. Finally, we limit the maximum number of new cuts in which each variable may appear to maxCutsPerVar . This promotes cut diversity and makes it easier to partition the cuts into a small number of clusters of non-overlapping cuts, speeding up the algorithm considerably. To the best of our knowledge, we are the first to implement this feature in the context of the CP-ADMM. 6 The integer ADMM In this section, we present the INT-ADMM for computing feasible solutions to ( BSDPk ). Our algorithm is based on the \ell_{p} -Box ADMM from [ 56 ] . That algorithm is designed to find feasible solutions to arbitrary binary optimization programs, and was successfully used e.g., in [ 29 ] and [ 57 ] . The \ell_{p} -Box ADMM relies on the observation that, for any p>0 , \{0,1\}^{n}=[0,1]^{n}\cap\left\{x\in\mathbb{R}^{n}:\left\lVert x-\frac{1}{2}e\right\rVert_{p}^{p}=\frac{n}{2^{p}}\right\}. (33) That is, the set of binary vectors can be written as the intersection of the unit box with the \ell_{p} -sphere centered at \frac{1}{2}e with radius \frac{n^{1/p}}{2} . For p=2 , there exists a closed-form expression for projecting onto a sphere. Extending this idea to ( BSDPk ), we first split its constraints into three components, each admitting an efficient projection: we have a variable \hat{X} that satisfies the affine (including box) constraints, a variable Y that satisfies the PSD constraint, and in addition, a third variable Z that satisfies a sphere constraint. In more detail, given that we work in \mathbb{S}^{n+1} rather than \mathbb{R}^{n} , and also that entry (0,0) should be equal to k , we consider the \ell_{2} -sphere in \mathbb{S}^{n+1} centered at C\mathrel{\mathop{:}}=\frac{1}{2}J_{n+1}+\begin{pmatrix}k&0_{n}^{\top}\\ 0_{n}&\textbf{0}_{n}\end{pmatrix} with radius (n+1)/2 : \mathcal{Z}=\left\{Z\in\mathbb{S}^{n+1}:\left\lVert Z-C\right\rVert^{2}=\frac{(n+1)^{2}}{4}\right\}. (34) Note that \mathcal{Z} is a non-convex set, which impacts the convergence of the INT-ADMM, as explained in Section 6.1 . Then, letting \hat{\mathcal{X}}\mathrel{\mathop{:}}=\hat{\mathcal{X}}_{\emptyset} (see ( 19 )), we can rewrite ( BSDPk ) as follows: \alpha_{k}(\mathcal{G})=\max\left\{\left\langle\hat{I},\hat{X}\right\rangle:\hat{X}=Y,\hat{X}=Z,\hat{X}\in\hat{\mathcal{X}},Y\in\mathbb{S}_{+}^{n+1},Z\in\mathcal{Z}\right\}. (35) Next, we consider the augmented Lagrangian function of ( 35 ) with respect to the two coupling constraints \hat{X}=Y and \hat{X}=Z , which is given by L_{\beta_{Y},\beta_{Z}}(\hat{X},Y,Z,\Lambda,M)\mathrel{\mathop{:}}=\left\langle\hat{I},\hat{X}\right\rangle-\left\langle\Lambda,\hat{X}-Y\right\rangle-\left\langle M,\hat{X}-Z\right\rangle-\frac{\beta_{Y}}{2}\left\lVert\hat{X}-Y\right\rVert^{2}-\frac{\beta_{Z}}{2}\left\lVert\hat{X}-Z\right\rVert^{2}, (36) where \Lambda,M\in\mathbb{S}^{n+1} are the dual variables associated to the coupling constraints \hat{X}=Y and \hat{X}=Z , respectively, and \beta_{Y},\beta_{Z}>0 are fixed penalty parameters. We then obtain the following update rules: \displaystyle\hat{X}^{t+1} \displaystyle=\text{arg max}_{\hat{X}\in\hat{\mathcal{X}}}L_{\beta_{Y},\beta_{Z}}(\hat{X},Y^{t},Z^{t},\Lambda^{t},M^{t}) (37) \displaystyle Y^{t+1} \displaystyle=\text{arg max}_{Y\in\mathbb{S}^{n+1}_{+}}L_{\beta_{Y},\beta_{Z}}(\hat{X}^{t+1},Y,Z^{t},\Lambda^{t},M^{t}) (38) \displaystyle Z^{t+1} \displaystyle=\text{arg max}_{Z\in\mathcal{Z}}L_{\beta_{Y},\beta_{Z}}(\hat{X}^{t+1},Y^{t+1},Z,\Lambda^{t},M^{t}) (39) \displaystyle\Lambda^{t+1} \displaystyle=\Lambda^{t}+\beta_{Y}(\hat{X}^{t+1}-Y^{t+1}) (40) \displaystyle M^{t+1} \displaystyle=M^{t}+\beta_{Z}(\hat{X}^{t+1}-Z^{t+1}). (41) The maximization problems ( 37 )-( 39 ) can be rewritten as the following projection problems: \displaystyle\text{arg max}_{\hat{X}\in\hat{\mathcal{X}}}L_{\beta_{Y},\beta_{Z}}(\hat{X},Y^{t},Z^{t},\Lambda^{t},M^{t})=\mathcal{P}_{\mathcal{\hat{X}}}\left(\frac{1}{\beta_{Y}+\beta_{Z}}\left(\beta_{Y}Y^{t}+\beta_{Z}Z^{t}+\hat{I}-\Lambda^{t}-M^{t}\right)\right) (42) \displaystyle\text{arg max}_{Y\in\mathbb{S}^{n+1}_{+}}L_{\beta_{Y},\beta_{Z}}(\hat{X}^{t+1},Y,Z^{t},\Lambda^{t},M^{t})=\mathcal{P}_{\mathbb{S}^{n+1}_{+}}\left(\hat{X}^{t+1}+\frac{1}{\beta_{Y}}\Lambda^{t}\right) (43) \displaystyle\text{arg max}_{Z\in\mathcal{Z}}L_{\beta_{Y},\beta_{Z}}(\hat{X}^{t+1},Y^{t+1},Z,\Lambda^{t},M^{t})=\mathcal{P}_{\mathcal{Z}}\left(\hat{X}^{t+1}+\frac{1}{\beta_{Z}}M^{t}\right). (44) The projections onto \hat{\mathcal{X}} and \mathbb{S}^{n+1}_{+} were already discussed in Section 5.1 . The projection onto \mathcal{Z} admits the following closed-form expression: \mathcal{P}_{\mathcal{Z}}(Z)=\frac{n+1}{2}\frac{Z-C}{\left\lVert Z-C\right\rVert}+C. (45) 6.1 Achieving convergence and escaping local optima Given that \mathcal{Z} is non-convex, the INT-ADMM is not guaranteed to converge, and if it converges, the obtained solution is not necessarily optimal for ( 35 ). Preliminary experiments showed that the solution quality strongly depends on the choice of \beta_{Y} and \beta_{Z} . As proposed in [ 56 ] , we set \beta_{Y}=\beta_{Z}\mathrel{\mathop{:}}=\beta , and we gradually increase \beta over the course of the algorithm. We initialize \beta to \beta^{0} and then multiply by a factor \beta_{incr}>1 after every iteration. Therefore, the emphasis initially lies on obtaining a high objective value, while over time the focus shifts to enforcing feasibility. Using the parameter values specified in Table 2 in Section 7 , our algorithm consistently converged on all benchmark instances to a solution satisfying the following criterion: \max\left\{\frac{\left\lVert\hat{X}^{t}-Y^{t}\right\rVert}{1+\left\lVert\hat{X}^{t}\right\rVert},\frac{\left\lVert\hat{X}^{t}-Z^{t}\right\rVert}{1+\left\lVert\hat{X}^{t}\right\rVert}\right\}\leq\varepsilon_{\texttt{INT-ADMM}}. Upon meeting this criterion, the matrix \hat{X}^{t} (whose entries are close to integer) is rounded to a fully integer matrix, after which its feasibility is verified. Our algorithm also contains a novel mechanism for escaping local optima. Namely, whenever the above convergence criterion is satisfied, we save the feasible solution found, and then multiply \beta by a factor \beta_{decr}\in(0,1) (taking care that \beta does not drop below a minimum value \beta_{min}) , thereby shifting the emphasis back to the objective value. The INT-ADMM then continues for at least 10 more iterations until the convergence criterion is met again. This process is repeated until the algorithm has not improved the best solution so far for maxTriesWithoutImpr consecutive tries, or the current solution value matches a known upper bound. 6.2 Reducing runtime Finally, we discuss some additional features of the INT-ADMM that are aimed to reduce runtime. First, we initialize the INT-ADMM using the final solution \hat{X}^{*} obtained from the CP-ADMM. Specifically, we set \hat{X}^{0}=\mathcal{P}_{\hat{\mathcal{X}}}(\hat{X}^{*}) , Y^{0}=\mathcal{P}_{\mathbb{S}^{n+1}_{+}}(\hat{X}^{*}) , Z^{0}=\mathcal{P}_{\mathcal{Z}}(\hat{X}^{*}) , \Lambda^{0}=\beta_{Y}(\hat{X}^{0}-Y^{0}) and M^{0}=\beta_{Z}(\hat{X}^{0}-Z^{0}) . Furthermore, we experimented with additionally including in \mathcal{Z} some of the equality constraints that are already in \hat{\mathcal{X}} . Among the tested variants, only adding the constraint Z_{00}=k proved beneficial. The projection onto \mathcal{Z}^{\prime}\mathrel{\mathop{:}}=\{Z\in\mathcal{Z}:Z_{00}=k\} is given by \mathcal{P}_{\mathcal{Z}^{\prime}}(Z)=\frac{\sqrt{(n+1)^{2}-1}}{2}\frac{Z^{\prime}-C}{\left\lVert Z^{\prime}-C\right\rVert}+C-\begin{pmatrix}1/2&0_{n}^{\top}\\ 0_{n}&\textbf{0}_{n}\end{pmatrix},\quad\text{where }Z^{\prime}=Z+\begin{pmatrix}\frac{1}{2}+k-Z_{00}&0_{n}^{\top}\\ 0_{n}&\textbf{0}_{n}\end{pmatrix}. (46) Finally, observe that the Y - and Z -updates ( 43 ) and ( 44 ) are independent of each other and could therefore be carried out in parallel. In our implementation, however, these updates are performed sequentially. 7 Computational experiments This section presents the results of our computational experiments. In Section 7.1 , we describe our computational setup. In Section 7.2 , we compare the performance of our methods with methods from the literature, and we evaluate the importance of the mechanism to escape local optima in the INT-ADMM. In Sections 7.3 and 7.4 , we compare various configurations of the CP-ADMM, focusing, respectively, on the valid inequalities considered and on the effect of limiting the maximum number of new cuts per variable. Finally, in Section 7.5 , we use the upper bounds obtained with the CP-ADMM to derive lower bounds on the chromatic number of benchmark graphs. 7.1 Computational setup In Sections 7.2 – 7.4 , we consider 68 benchmark instances used in [ 7 ] and [ 27 ] . Specifically, we consider instances whose graphs originate from the Second DIMACS Implementation Challenge for the maximum clique problem [ 31 ] or from the COLOR02 symposium [ 30 ] . All graphs in our tables that end with the letter “c” are complements of the original DIMACS graphs. Many of these instances were also used in [ 33 ] . We only consider instances that were not solved to optimality in that paper, since our upper bounds, when rounded down to the nearest integer, are at least as strong as the bounds reported there on all benchmark instances. Our algorithms were implemented in MATLAB R2024b and the code is available upon request. The experiments were executed on a virtual machine with an AMD EPYC-Rome processor, 2.0 GHz with 64 GB of RAM, running Ubuntu 22.04.5 LTS, and using a single CPU thread. Linear programs were solved with Gurobi 13.00 using the parser CVX, version 2.2 [ 17 ] . Tables 1 and 2 report the parameter values used for the CP-ADMM and INT-ADMM, respectively. For \varepsilon_{\texttt{ADMM}} and maxInnerIter , we present in parentheses the alternative values used in the final outer iteration of the CP-ADMM. Table 1 : Parameter values for the CP-ADMM used in the computational experiments Parameter Value Parameter Value Parameter Value \beta 1.2 minIneq n/4 timeLimitGlobal 3600 s \gamma 1.617 minIneqPhase1 n timeLimitCliques 10 s \varepsilon_{\texttt{ADMM}} 10^{-4} ( \to 10^{-5} ) maxIneq 5n timeLimitHoles 10 s \varepsilon_{Dyk} 10^{-2} maxCutsPerVar 5 maxCliques 100{,}000 maxInnerIter 2000 ( \to 10{,}000 ) minImpr 0.025 maxCliquePairs 100{,}000 minViol 10^{-2} minImprPhase1 0.25 maxHoles 100{,}000 Table 2 : Parameter values for the INT-ADMM used in the computational experiments. Parameter Value Parameter Value Parameter Value \beta^{0} 0.05 \beta_{decr} 0.5 \varepsilon_{\texttt{INT-ADMM}} 10^{-3} \beta_{incr} 1.0001 \beta_{min} 0.001 maxTriesWithoutImpr 3 We also ran two heuristics from [ 33 ] on our machine. The first heuristic (HEUR1) reduces a M k CS instance with graph \mathcal{G} to a maximum stable set instance defined on the Cartesian product of the complete graph on k vertices and \mathcal{G} . The resulting instance is then solved using a stable set heuristic. The second heuristic (HEUR2) is a tabu search heuristic. The maximum of the two obtained lower bounds is used for the optimality check in the stopping criteria of the CP-ADMM (see Section 5.2.1 ). Even though the INT-ADMM often provides better lower bounds than the two heuristics, its higher computational cost makes it less suitable for use in the stopping criteria of the CP-ADMM. The upper bound obtained using the CP-ADMM is used for the optimality check in the INT-ADMM (see Section 6.1 ). 7.2 Comparison with methods from the literature In Tables 3 and 4 , we compare the performance of our methods with methods from the literature on the instances considered in [ 7 ] and [ 27 ] , respectively. In both tables, each row corresponds to an instance specified by the first four columns: the name of the graph, its number of vertices ( n ) and its density (given by \rho=|\mathcal{E}|/\binom{n}{2} ), and the number of colors ( k ). For the instances from [ 27 ] , Table 4 additionally reports the optimal values \alpha_{k}(\mathcal{G}) provided in that paper. No runtimes on individual instances are given there, but the authors report that their best method could prove optimality within about one hour per instance. The next part of each table contains upper bounds, with corresponding runtimes (in seconds) in parentheses. For the instances from [ 7 ] , we first report the best upper bound obtained in that work, where a time limit of 1800 seconds was used. Runtimes are omitted here because of differences in hardware. We further present the bound \theta_{k}(\mathcal{G}) as computed in [ 33 ] using the solver Mosek. We also present the strongest bound from that paper, namely the bound \theta^{1}_{k}(\mathcal{G}) that is strengthened using BQP cuts. The authors only report results on instances where the solver did not run out of memory; the other entries in the tables are left blank. The runtimes reported in that paper are included for reference, but should be interpreted with care as a different machine was used for that work (a computer with two processors Intel ® Xeon ® Gold 6126 CPU @ 2.60 GHz and 512 GB of RAM). The following columns present the bounds and runtimes of the standard ADMM without cuts (denoted by STD-ADMM) and the CP-ADMM, respectively. Recall that the valid upper bounds computed by the STD-ADMM approximate \theta_{k}(\mathcal{G}) . As will be motivated in the next section, the CP-ADMM is configured here to use generalized clique and odd-hole inequalities, but no generalized triangle inequalities. Bounds preceded by a “ \leq ”-sign indicate that a method was terminated early because the upper bound rounded down equaled a lower bound given by HEUR1 or HEUR2. Moreover, the CP-ADMM was not run on instances where the STD-ADMM already provided an optimal bound. The final part of each table concerns the methods for finding lower bounds. For the instances of [ 7 ] , we first report the best lower bound from that work. Columns HEUR1, HEUR2 and INT-ADMM report the lower bounds and runtimes of the respective methods. To evaluate the role of the mechanism to escape local optima in the INT-ADMM (see Section 6.1 ), the columns INT-ADMM - report the objective value of the first feasible solution obtained by the algorithm, together with the corresponding runtime. The best upper and lower bounds for each instance are depicted in bold. Furthermore, Table 5 reports for each instance the number of iterations required by each ADMM-based method. For the CP-ADMM, the table additionally specifies the number of outer iterations (in parentheses) and the number of added cuts. The results can be summarized as follows: • The upper bounds computed by the STD-ADMM approximate well the bounds \theta_{k}(\mathcal{G}) computed in [ 33 ] using Mosek, but the STD-ADMM typically requires much less runtime, and never ran out of memory. • The CP-ADMM produces the strongest upper bounds on almost all instances, often improving upon the best previously known bound by multiple integers. On the few instances where the CP-ADMM does not return the best bound, its bound after rounding down matches the best previously known integer bound. Furthermore, the CP-ADMM never ran out of memory and is often significantly faster than the IPM-based cutting plane algorithm of [ 33 ] for finding the strengthened \theta^{1}_{k}(\mathcal{G}) bound, which is, on most instances, the best previously known upper bound. There are also instances where the CP-ADMM does not improve upon the STD-ADMM, either because no violated inequalities are identified, or because the added inequalities do not lead to stronger bounds. Table 3 : Results on instances considered in [ 7 ] . Instance Upper bounds Lower bounds graph n \rho k UB [ 7 ] \theta_{k}(\mathcal{G}) \theta^{1}_{k}(\mathcal{G}) +cuts STD-ADMM CP-ADMM LB [ 7 ] HEUR1 HEUR2 INT-ADMM - INT-ADMM C125.9c 125 0.10 2 79.4 74.63 (29) 74.10 (1130) 74.64 (1) 70.46 (262) 61 61 ( < 1) 64 (2) 62 (6) 64 (40) 3 115.6 107.27 (25) 105.31 (1806) 107.28 (1) 102.29 (241) 81 83 ( < 1) 87 (2) 88 (1) 90 (55) keller4c 171 0.35 2 27.9 26.93 (62) 26.93 (1217) 26.94 (29) 24.69 (752) 20 18 ( < 1) 22 (4) 22 (6) 22 (70) 3 41.9 40.40 (68) 40.40 (1190) 40.40 (29) 36.93 (245) 30 31 ( < 1) 32 (4) 33 (5) 33 (77) gen200_p0.9_44c 200 0.10 2 88.0 88.00 (258) 87.99 (13570) 88.02 (5) 87.17 (161) 64 71 ( < 1) 82 (6) 77 (3) 82 (103) 3 132.0 131.94 (258) 131.66 (16242) 131.96 (9) 129.84 (154) 93 105 ( < 1) 113 (6) 112 (3) 116 (205) gen200_p0.9_55c 200 0.10 2 109.0 100.84 (338) 100.36 (14187) 100.85 (4) 98.73 (139) 69 83 ( < 1) 94 (6) 90 (3) 94 (99) 3 161.6 146.22 (312) 145.34 (10893) 146.24 (4) 142.13 (257) 99 112 ( < 1) 127 (6) 127 (4) 129 (179) san200_0.9_2c 200 0.10 2 117.0 106.61 (353) 106.03 (13590) 106.63 (3) 104.40 (37) 75 97 ( < 1) 99 (6) 99 (4) 101 (65) 3 184.0 152.84 (328) 151.16 (11889) 152.88 (3) 147.79 (366) 98 127 ( < 1) 131 (4) 137 (3) 138 (87) san200_0.7_2c 200 0.30 2 36.0 35.63 (220) 35.60 (12066) 35.63 (5) 34.93 (63) 31 28 ( < 1) 30 (5) 34 (3) 34 (3) 3 54.0 53.24 (190) 53.22 (5508) 53.24 (4) 51.58 (95) 43 41 ( < 1) 42 (5) 49 (3) 49 (69) brock200_4c 200 0.34 2 51.8 42.24 (115) 42.24 (1697) 42.25 (1) 40.97 (40) 27 30 ( < 1) 30 (5) 29 (13) 31 (137) 3 76.6 63.36 (117) 63.36 (1636) 63.37 (1) 61.40 (44) 40 42 ( < 1) 45 (5) 46 (16) 46 (106) brock200_2c 200 0.50 2 30.1 28.26 (60) 28.26 (1291) 28.26 (2) 27.64 (47) 19 19 ( < 1) 20 (4) 21 (22) 21 (114) 3 44.9 42.39 (61) 42.39 (1168) 42.39 (1) 41.29 (52) 28 28 ( < 1) 29 (4) 30 (27) 31 (142) c-fat200-5c 200 0.57 2 116.0 120.69 (35) 119.42 (7649) 120.73 (24) \leq 116.77 (81) 116 116 ( < 1) 115 (11) 114 (32) 116 (107) 3 172.0 181.03 (33) 175.24 (6955) 181.09 (11) \leq 172.88 (49) 172 172 ( < 1) 172 (11) 169 (4) 172 (5) C250.9c 250 0.10 2 134.5 111.63 (1952) 111.64 (5) 109.04 (94) 74 81 ( < 1) 85 (10) 80 (4) 86 (248) 3 201.6 167.15 (1861) 167.22 (3) 163.58 (42) 106 116 ( < 1) 122 (10) 114 (6) 125 (223) p_hat300-2c 300 0.51 2 62.1 52.96 (626) 52.97 (77) 52.79 (179) 42 43 ( < 1) 45 (11) 45 (6) 46 (207) 3 91.0 77.28 (718) 77.29 (48) 77.09 (186) 55 58 ( < 1) 61 (12) 62 (6) 62 (210) p_hat300-1c 300 0.76 2 20.9 20.04 (107) 20.04 (78) 20.04 (103) 14 14 ( < 1) 14 (11) 16 (32) 16 (196) 3 31.0 30.06 (109) 30.06 (78) 30.06 (103) 20 21 ( < 1) 21 (12) 23 (52) 24 (321) MANN-a27c 378 0.01 2 261.0 261.31 (85) 261.06 (51) 246 249 ( < 1) 250 (22) 191 (38) 240 (451) 3 378.0 378.12 (4) 378.12 (5) 368 370 ( < 1) 372 (16) 302 (7) 367 (486) san400-0-9-1c 400 0.10 2 199.0 173.11 (11) 170.83 (100) 132 147 ( < 1) 108 (26) 151 (12) 155 (442) 3 289.9 245.77 (15) 240.69 (352) 163 202 ( < 1) 159 (23) 201 (7) 205 (618) c-fat500-10c 500 0.63 2 252.0 252.19 (143) 252 252 ( < 1) 251 (85) 250 (292) 250 (839) 3 376.0 376.42 (143) 376 376 ( < 1) 376 (69) 376 (22) 376 (22) Table 4 : Results on instances considered in [ 27 ] . Instance Upper bounds Lower bounds graph n \rho k \alpha_{k}(\mathcal{G}) \theta_{k}(\mathcal{G}) \theta^{1}_{k}(\mathcal{G}) +cuts STD-ADMM CP-ADMM HEUR1 HEUR2 INT-ADMM - INT-ADMM queen6_6 36 0.46 6 32 35.84 ( < 1) 35.81 (3) 35.84 ( < 1) 33.60 (38) 30 ( < 1) 32 (1) 32 (4) 32 (9) myciel5 47 0.22 4 44 47.00 ( < 1) 47.00 (4) 47.00 ( < 1) 47.00 (1) 44 ( < 1) 44 (1) 44 (4) 44 (13) 5 46 47.00 ( < 1) 47.00 (7) 47.00 ( < 1) 47.00 ( < 1) 46 ( < 1) 46 (5) 44 (6) 46 (17) 1-Insertions_4 67 0.10 3 63 67.00 (1) 67.00 (34) 67.00 ( < 1) 67.00 (1) 63 ( < 1) 63 (2) 63 (5) 63 (19) 1-FullIns_4 93 0.14 3 87 92.59 (11) 91.33 (554) 92.60 (2) 89.83 (178) 87 ( < 1) 87 (2) 87 (1) 87 (21) myciel6 95 0.17 3 83 95.00 (4) 93.32 (366) 95.01 ( < 1) 89.59 (336) 83 ( < 1) 83 (2) 80 (6) 80 (28) 4-FullIns_3 114 0.08 3 106 107.40 (20) 107.25 (901) 107.41 ( < 1) 107.26 (45) 105 ( < 1) 106 (3) 106 (3) 106 (29) 5-FullIns_3 154 0.07 3 144 145.33 (89) 145.23 (3551) 145.35 (1) 145.22 (49) 144 ( < 1) 144 (5) 144 (1) 144 (46) c-fat200-1 200 0.08 10 180 184.67 (300) 184.65 (5485) 184.68 (9) 184.68 (10) 180 ( < 1) 180 (6) 180 (16) 180 (98) sanr200_0.9 200 0.90 4 16 17.91 (2) 17.91 (918) 17.91 (41) 17.91 (60) 16 ( < 1) 15 (5) 16 (26) 16 (108) san200_0.9_2 200 0.90 4 16 17.21 (3) 17.20 (2036) 17.21 (41) 17.21 (61) 16 ( < 1) 16 (5) 16 (19) 16 (106) gen200_p0.9_55 200 0.90 4 17 18.15 (4) 18.15 (1386) 18.15 (27) 18.15 (46) 16 ( < 1) 15 (5) 17 (18) 17 (99) 2-FullIns_4 212 0.07 3 202 207.65 (993) 207.69 (8) 206.50 (936) 201 ( < 1) 202 (6) 189 (2) 202 (106) DSJC250.9 250 0.90 4 18 19.72 (15) 19.73 (59) 19.73 (84) 17 ( < 1) 16 (8) 18 (34) 18 (157) 3-FullIns_4 405 0.04 5 402 405.03 (24) 404.29 (103) 402 ( < 1) 402 (21) 377 (8) 402 (248) 6 404 405.05 (6) 405.06 (90) 404 (1) 404 (22) 386 (5) 404 (280) DSJR500.1 500 0.03 8 459 459.81 (4) 459.55 (21) 445 (2) 438 (26) 403 (16) 458 (667) 9 477 477.82 (4) 477.54 (19) 466 (2) 459 (25) 441 (11) 477 (95) 10 489 489.84 (6) 489.55 (18) 480 (3) 477 (27) 474 (14) 489 (165) 11 496 496.81 (4) 496.55 (15) 489 (3) 493 (35) 492 (12) 496 (32) c-fat500-2 500 0.07 15 300 300.06 (3) 300 (3) 300 (55) 300 (32) 300 (32) 17 340 340.10 (3) 340 (5) 340 (45) 340 (46) 340 (46) 20 400 400.16 (3) 400 (7) 400 (56) 400 (33) 400 (33) 22 440 440.19 (4) 440 (10) 440 (51) 433 (76) 440 (98) 25 490 \leq 490.15 (35) 490 (13) 490 (47) 490 (85) 490 (85) c-fat500-10 500 0.37 10 40 \leq 40.09 (36) 40 ( < 1) 40 (48) 40 (163) 40 (163) 15 60 \leq 60.05 (36) 60 (1) 60 (50) 60 (159) 60 (159) 17 68 \leq 68.06 (36) 68 (2) 68 (50) 68 (151) 68 (151) 20 80 80.04 (34) 80 (3) 80 (58) 80 (136) 80 (136) 22 88 88.05 (32) 88 (3) 88 (60) 88 (151) 88 (151) 25 100 100.05 (28) 100 (5) 100 (56) 100 (133) 100 (133) 4-FullIns_4 690 0.03 5 684 686.59 (326) 686.38 (3167) 684 (2) 684 (50) 643 (84) 684 (970) 6 687 690.24 (329) 689.63 (2300) 687 (3) 687 (42) 625 (31) 687 (669) 7 689 690.23 (347) 690.23 (515) 689 (3) 689 (38) 659 (50) 689 (1056) 5-FullIns_4 1085 0.02 5 1076 1078.80 (853) 1078.52 (3600) 1076 (6) 1076 (113) 823 (190) 1076 (3011) 6 1079 1082.51 (891) 1082.64 (3278) 1079 (10) 1079 (96) 946 (165) 1079 (3312) 7 1082 1085.96 (881) 1085.52 (3491) 1082 (12) 1082 (90) 814 (109) 1082 (2869) 8 1084 1085.68 (917) 1085.68 (937) 1084 (17) 1084 (97) 971 (131) 1082 (2865) Table 5 : Additional results on the number of iterations and cuts. Instances considered in [ 7 ] Instances considered in [ 27 ] Instance STD-ADMM CP-ADMM INT-ADMM - INT-ADMM Instance STD-ADMM CP-ADMM INT-ADMM - INT-ADMM graph k #iterations #iterations #cuts #iterations #iterations graph k #iterations #iterations #cuts #iterations #iterations C125.9c 2 501 3008 (13) 3395 3266 22973 queen6_6 6 680 5569 (12) 627 13460 33684 3 548 2845 (15) 3411 750 31325 myciel5 4 34 34 (2) 51 12441 38842 keller4c 2 10000 12625 (9) 3608 1792 22029 5 28 28 (1) 0 17687 50207 3 10000 3583 (11) 4487 1522 24570 1-Insertions_4 3 54 75 (3) 410 5724 25286 gen200_p0.9_44c 2 1284 4779 (9) 4092 614 25324 1-FullIns_4 3 1916 5994 (11) 3928 516 19638 3 2581 2932 (10) 5017 624 50164 myciel6 3 99 6689 (13) 5608 5455 26107 gen200_p0.9_55c 2 1049 2258 (10) 3945 644 24090 4-FullIns_3 3 304 2946 (6) 898 2058 19497 3 1144 2552 (12) 4785 1000 43577 5-FullIns_3 3 487 2169 (6) 1058 347 17594 san200_0.9_2c 2 750 1492 (6) 3217 1007 15809 c-fat200-1 10 2439 2439 (1) 0 4060 24600 3 925 2800 (15) 5335 660 21110 sanr200_0.9 4 10000 10000 (1) 0 6342 26154 san200_0.7_2c 2 1235 2208 (6) 2185 602 602 san200_0.9_2 4 10000 10000 (1) 0 4586 25966 3 995 1957 (9) 4185 667 16397 gen200_p0.9_55 4 6659 6659 (1) 0 4317 24179 brock200_4c 2 137 622 (6) 2668 2940 32005 2-FullIns_4 3 1967 10987 (7) 5288 381 24844 3 118 521 (7) 3274 3722 24646 DSJC250.9 4 10000 10000 (1) 0 5908 27719 brock200_2c 2 469 1090 (5) 998 4989 26193 3-FullIns_4 5 2002 1400 (4) 1551 638 20615 3 304 883 (6) 1436 6205 32366 6 433 3903 (2) 178 371 23060 c-fat200-5c 2 7387 7970 (5) 3255 8075 27039 DSJR500.1 8 196 248 (3) 817 940 39031 3 3566 3298 (6) 4443 1122 1273 9 227 232 (3) 476 639 5464 C250.9c 2 1066 2142 (8) 3420 691 42300 10 301 266 (2) 258 784 9332 3 644 1309 (5) 3217 1069 38292 11 209 252 (2) 166 667 1811 p_hat300-2c 2 10000 10634 (2) 201 718 26862 c-fat500-2 15 153 1835 1835 3 6219 10478 (2) 175 797 26903 17 157 2508 2508 p_hat300-1c 2 10000 10000 (1) 0 4045 25305 20 177 1846 1846 3 10000 10000 (1) 0 6725 41314 22 207 4333 5608 MANN-a27c 2 8394 2875 (3) 559 3479 41660 25 2000 5033 5033 3 395 395 (1) 0 675 43893 c-fat500-10 10 2000 9396 9396 san400-0-9-1c 2 984 1551 (5) 4511 991 35926 15 2000 9057 9057 3 1323 2607 (12) 7296 597 49768 17 2000 8439 8439 c-fat500-10c 2 10000 17398 48553 20 1927 7912 7912 3 10000 1399 1399 22 1758 8754 8754 25 1542 7773 7773 4-FullIns_4 5 10000 10638 (5) 3899 2801 32419 6 10000 10566 (4) 3823 1025 21502 7 10000 10079 (2) 207 1627 33925 5-FullIns_4 5 10000 9933 (3) 1542 2449 39010 6 10000 10306 (3) 981 2076 42540 7 10000 10349 (3) 1371 1395 37081 8 10000 10000 (1) 0 1676 36490 • The INT-ADMM always returned a high-quality feasible solution. For the instances considered in [ 7 ] , the INT-ADMM improves upon the best previously known lower bound on 20 instances, matches the best known bound on 7 instances (with the solution being optimal in at least 3 cases), and is worse on only 3 instances. For the instances considered in [ 27 ] , the INT-ADMM finds an optimal solution for all instances except myciel6 with k=3 and 5-FullIns_4 with k=8 (where HEUR1 and HEUR2 both find an optimal solution), and DSJR500.1 with k=8 (where the INT-ADMM improves upon HEUR1 and HEUR2). • The mechanism to escape local optima in the INT-ADMM helps to find significantly improved solutions, but the mechanism is computationally costly as it requires a large number of iterations. 7.3 Comparing the effectiveness of valid inequalities In this section, we compare several configurations of the CP-ADMM that include inequalities ( 9 ), ( 10 ), ( 15 ), ( 17 ) and/or ( 18 ). For the results presented in this subsection only, each configuration was run with a time limit of 900 seconds. We restrict attention to 36 out of the 68 benchmark instances for which (i) at least one configuration yields a stronger bound than \theta_{k}(\mathcal{G}) , (ii) none of the configurations attains optimality, and (iii) the majority of the configurations terminate within the time limit. Figures 1 and 2 summarize the results using box and whisker plots. Each box extends from the first quartile to the third quartile of the data, with a solid line marking the median. Whiskers extend to the farthest data point lying within 1.5 times the inter-quartile range from the box. Outliers are shown by individual markers, and means are indicated by dashed lines. Figure 1 shows the effect of our valid inequalities on the obtained upper bounds. The plot on the left compares upper bounds obtained by configurations in which inequalities of a single type are added to ( SDPk ). The right plot focuses on the marginal benefit of various configurations that include generalized clique inequalities ( 15 ) on top of the configuration that only includes those inequalities. Figure 2 concerns the runtimes of each of the configurations. Figure 1 : Effect of valid inequalities on the obtained upper bounds. Figure 2 : Required runtime per configuration. When adding inequalities of a single type to ( SDPk ), the generalized clique inequalities ( 15 ) typically yield the best bounds by a considerable margin. On the other hand, generalized triangle inequalities ( 10 ) do not provide any improvement in bounds when tested on 11 instances for which k\leq 2 . Recall that those inequalities are redundant for k>2 . Conversely, triangle inequalities ( 9 ) do yield improved bounds. Better bounds are typically obtained by adding generalized clique inequalities ( 17 ) or generalized odd-hole inequalities ( 18 ), with their relative effectiveness varying across the instances. In particular, inequalities ( 18 ) are highly effective for the instance with graph myciel6, which does not contain any cliques of size 3 or larger (see the outlier on the top-right of the first plot). This instance is excluded from the second plot, as it would otherwise dominate the scale of the y-axis. In terms of computational cost, the CP-ADMM typically requires most runtime to solve the relaxations with generalized clique inequalities ( 15 ) and ( 17 ), followed by the relaxation with generalized odd-hole inequalities ( 18 ). Considering the marginal benefit of various configurations that include ( 15 ) on top of the configuration that only includes ( 15 ), we observe the following. The largest marginal benefits are obtained using generalized clique inequalities ( 17 ), but these bound improvements come at a significant computational cost. The generalized odd-hole inequalities ( 18 ) also provide significant marginal improvements for many instances, but at a lower computational cost. Despite being effective on their own, the generalized triangle inequalities ( 9 ) only lead to limited improvements on top of the other configurations that include inequalities ( 15 ). This observation is in line with the computational results of [ 50 ] , where the M k CS problem is considered for k=1 . Finally, we observe that considering more inequality types can sometimes lead to slightly weaker bounds. In these cases, the CP-ADMM is terminated before all violated inequalities are added to the relaxation, see Section 5.2.1 . 7.4 Limiting the number of new cuts per variable In this section, we report on the considerable benefit of limiting the maximum number of new cuts in which each variable may appear. Recall that in our default configuration of the CP-ADMM, maxCutsPerVar is set to 5 . On the 45 instances where the default configuration added at least one cut, we also ran a version of the algorithm without the maxCutsPerVar limit. On average, the default configuration requires only 50% the runtime, 73% the number of cuts and 42% the amount of time per inner iteration compared to the configuration without the limit. One explanation for the decrease in runtime is that the maxCutsPerVar limit makes it easier to partition the cuts into a small number of clusters of non-overlapping cuts, thereby reducing the runtime required for Dykstra’s cyclic projection algorithm. On instances where the configuration without the maxCutsPerVar limit reaches the time limit, the default configuration often yields stronger upper bounds, as it can perform more iterations in the same amount of time. 7.5 Lower bounds on the chromatic number 33 exploited upper bounds for the M k CS problem to compute lower bounds for the chromatic number \chi(\mathcal{G}) of a graph. In particular, they used the following relation \chi(\mathcal{G})\geq\max\left\{k:UB_{k}(\mathcal{G})