1 Introduction

The maximum edge-weighted clique problem (MEWCP) is a well known combinatorial optimisation problem which consists of finding a maximum weight clique with no more than b nodes in a node- and edge-weighted complete graph. The weight of a clique is defined as the sum of the weights of all its nodes and edges. More formally, the MEWCP is defined as follows. Given a complete undirected graph \(G = (N,E)\) with node set N, edge set E, an integer number \(b \le |N|-1\), weights \(w_i \in \mathbb {R}\) associated with each node \(i \in N\) and weights \(c_e\in \mathbb {R}\) associated with each edge \(e \in E\), the MEWCP consists of finding a sub-clique \(C=(U,F)\) of G such that the sum of the weights of nodes in U and edges in F is maximised and \(|U| \le b\). It can be formulated as follows:

$$\begin{aligned} \max&\sum \limits _{i \in N}w_i x_i + \sum \limits _{e\in E} c_ey_e&\end{aligned}$$
(1a)
$$\begin{aligned} s.t.&\sum \limits _{i \in N} x_i \le b&\end{aligned}$$
(1b)
$$\begin{aligned}&y_{ij} \le x_i&\text { for } (i,j) \in E\end{aligned}$$
(1c)
$$\begin{aligned}&y_{ij} \le x_j&\text { for } (i,j) \in E\end{aligned}$$
(1d)
$$\begin{aligned}&x_i + x_j \le y_{ij} + 1&\text { for } (i,j) \in E\end{aligned}$$
(1e)
$$\begin{aligned}&x_i \in \{0,1\}&\text { for } i \in N\end{aligned}$$
(1f)
$$\begin{aligned}&y_e \in \{0,1\}&\text { for } e \in E \end{aligned}$$
(1g)

Note that due to the McCormick inequalities [12] (1c)–(1e) and the constraint (1f), the variables \(y_e, e\in E\) can be assumed to be continuous between 0 and 1.

The MEWCP has many applications, especially in certain facility location problems, see [3, 10, 17, 18]. Other important applications of the MEWCP that arise in molecular biology are given in Hunting [6]. The MEWCP is a generalization of the well studied maximum clique problem, which is known to be NP-hard, see [20] for a review of solution approaches for the maximum clique problem. On the other hand, the above formulation of the MEWCP can also be seen as a particular case of the quadratic knapsack problem for which plenty of exact and heuristic methods exist, see [2, 5, 16].

Numerous solution methods have been proposed in the literature for the MEWCP. We refer the reader to Wu and Hao [20] for a recent review of exact and heuristic solution methods for the MEWCP. The most successful algorithms proposed in the literature for the MEWCP use a branch-and-cut framework. The availability of strong valid inequalities is key to the success of these algorithms. Ideally, one would like to use cutting planes that are facet defining and computationally ‘easy’ to generate. Several families of facet defining inequalities are proposed in the literature for this purpose, see for example [7–9, 11, 13, 14, 19].

In this paper, we first consider a family of cutting planes that have recently been developed by Djeumou Fomeni et al. [4] for the general mixed 0–1 polynomial programs, and which can be separated efficiently in polynomial time. Then we prove that under certain conditions, one of the inequalities in this family defines a facet for the MEWCP. This result may contribute to the development of more efficient algorithms for the MEWCP that use cutting planes.

The rest of this paper is organised as follows. In Sect. 2, we review the relevant literature, and in Sect. 3 we provide the proof that the (s, t) inequalities define facets of the MEWCP.

2 Literature review

We refer the reader to [1, 3, 7–9, 11, 13, 14, 19] for more details on other existing facet defining inequalities and solution methods for the MEWCP. For the sake of brevity, we restrict our literature review to the paper of Djeumou Fomeni et al. [4] in which they presented the cutting planes that are discussed in this paper.

2.1 The family of (s, t) inequalities for 0–1 quadratic programs

Given a linear inequality \(\alpha ^Tx \le { \beta }\), with \(\alpha \in \mathbb {Q}^n\), \({ \beta } \in \mathbb {Q}\) let us define the corresponding quadratic knapsack polytope as

$$\begin{aligned} { \mathcal {Q}:=conv\left\{ (x,y) \in \{0,1\}^{n+\left( {\begin{array}{c}n\\ 2\end{array}}\right) }:\, \alpha ^Tx \le { \beta }, y_{ij} = x_ix_j \text { for } (i,j)\in E \right\} } \end{aligned}$$

For any \(S \subset N\) and any \(\alpha \in \mathbb {Q}^n\), we will let \(\alpha (S)\) denote \(\sum _{i \in S} \alpha _i\), \(S^+\) denote \(\{ i \in S: \alpha _i > 0 \}\) and \(S^-\) denote \(\{ i \in S: \alpha _i < 0 \}\).

The method for generating inequalities presented in [4] is based on the following idea. First, we construct a cubic valid inequality, by which we mean a non-linear inequality that involves products of up to three x variables, but no y variables. Then, we weaken the cubic inequality, in order to make it valid for \(\mathcal {Q}\). For example, we can take the inequality \(\alpha ^T x \le \beta \), and two binary variables, say \(x_s\) and \(x_t\), and form the following three cubic inequalities:

$$\begin{aligned} ({ \beta } - \alpha ^Tx) x_s x_t\ge & {} 0 \end{aligned}$$
(2)
$$\begin{aligned} ({ \beta } - \alpha ^Tx) x_s (1-x_t)\ge & {} 0 \end{aligned}$$
(3)
$$\begin{aligned} ({ \beta } - \alpha ^Tx) (1-x_s) (1-x_t)\ge & {} 0. \end{aligned}$$
(4)

Since quadratic terms of the form \(x_ix_j\) can be replaced with \(y_{ij}\), and linear and constant terms can be left unchanged, the only real issue is how to deal with cubic terms, of the form \(x_ix_jx_k\). The following lemma addresses this issue:

Lemma 1

Let \(x_i\), \(x_j\) and \(x_k\) be three variables, all constrained to lie in the interval [0, 1]. Let \(y_{ij} = x_ix_j\), and similarly for \(y_{ik}\) and \(y_{jk}\). Then we have the following lower bounds on \(x_ix_jx_k\):

$$\begin{aligned} x_i x_j x_k \ge \max \left\{ 0, \; y_{ij} + y_{ik} - x_i, \; y_{ij} + y_{jk} - x_j, \; y_{ik} + y_{jk} - x_k \right\} , \end{aligned}$$
(5)

and the following upper bounds:

$$\begin{aligned} x_i x_j x_k \le \min \left\{ y_{ij}, \; y_{ik}, \; y_{jk}, \; 1 - x_i - x_j - x_k + y_{ij} + y_{ik} + y_{jk} \right\} . \end{aligned}$$
(6)

It is shown in [4] that (5) and (6) provide the best possible under- and over-estimators of the product term \(x_ix_jx_k\).

The following theorem characterises the cutting planes that can be derived by weakening the cubic inequalities (2), (3) and (4), respectively. It turns out that they give rise to three huge (exponentially-large) families of valid inequalities for \(\mathcal {Q}\).

Theorem 1

For any pair \(\{s,t\} \subset N\), let S, T and W be disjoint subsets of \(N {\setminus } \{s,t\}\) and let R denote \(N {\setminus } (\{s,t\} \cup S \cup T \cup W)\).

  1. 1.

    Then the following (s, t) inequalities are valid for \(\mathcal {Q}\):

    $$\begin{aligned}&\sum _{i \in S \cup W} \alpha _i y_{is} \, + \, \sum _{i \in T \cup W} \alpha _i y_{it} \, - \, \sum _{i \in W} \alpha _i x_i \, \le \, -\alpha (W^-) \, + \, \alpha (S^+ \cup W^-) x_s \qquad \nonumber \\&\quad +\, \, \alpha (T^+ \cup W^-) x_t \, + \, \left( { \beta } - \alpha (\{s,t\} \cup S^+ \cup T^+ \cup W^- \cup R^-) \right) y_{st}. \end{aligned}$$
    (7)
  2. 2.

    The following mixed (s, t) inequalities are valid for \(\mathcal {Q}\):

    $$\begin{aligned}&\sum _{i \in W} \alpha _i x_i \!+ \!\sum _{i \in T \cup R} \alpha _i y_{is} \! - \! \sum _{i \in T \cup W} \alpha _i y_{it} \le \alpha (W^+) \!+\! \left( { \beta } - \alpha (\{s\} \cup S^- \cup W^+) \right) x_s\nonumber \\&\quad -\, \, \alpha (W^+ \cup T^-) x_t \, + \, \left( \alpha (\{s\} \cup S^- \cup T^- \cup W^+ \cup R^+) - { \beta } \right) y_{st}. \end{aligned}$$
    (8)
  3. 3.

    The following reverse (s, t) inequalities are valid for \(\mathcal {Q}\):

    $$\begin{aligned}&\sum _{i \in S \cup T \cup R} \alpha _i x_i \! -\! \sum _{i \in T \!\cup \! R} \alpha _i y_{is} \!-\! \sum _{i \in S \cup R} \alpha _i y_{it} \le { \beta } \!-\! \alpha (W^-) + \left( \alpha (S^+ \cup W^-) - { \beta } \right) x_s\nonumber \\&\qquad + \, \left( \alpha (T^+ \cup W^-) - { \beta } \right) x_t \, + \, \left( { \beta } - \alpha (S^+ \cup T^+ \cup W^- \cup R^-) \right) y_{st}. \end{aligned}$$
    (9)

These inequalities can be strengthened further, see [4] for details. Our contribution in this paper consists of proving that under certain conditions, the (s, t) inequalities (7) are facet defining. We also remark that the particular case of the mixed (s, t) inequalities obtained when \(S = T = R = \emptyset \) and \(\alpha = (1,\ldots ,1)\) was previously given in [7] and proved to be facet defining for the MEWCP.

2.2 Separation of the (s, t) inequalities in \(\mathcal{O}(n^3)\) time

Since the inequalities presented in Theorem 1 are exponential in number, we need separation algorithms. For a given family of inequalities, the separation algorithm takes a fractional point \((x^*,y^*)\), solution of the LP relaxation, as input, and outputs a violated inequality in that family, if one exists.

It turns out that the separation problems for the (s, t) inequalities (7), mixed (s, t) inequalities (8) and reverse (s, t) inequalities (9) can each be solved exactly in \(\mathcal{O}(n^3)\) time [4]. Indeed, there are \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) choices for the pair \(\{s,t\}\). Now assume that s and t are fixed. The (s, t) inequality can be rewritten as:

$$\begin{aligned}&\sum _{i \in S^+} \alpha _i (y_{is} + y_{st} - x_s) + \sum _{i \in T^+} \alpha _i (y_{it} + y_{st} - x_t) + \sum _{i \in W^+} \alpha _i (y_{is} + y_{it} - x_i)\\&\quad + \sum _{i \in S^-} \alpha _i y_{is} + \sum _{i \in T^-} \alpha _i y_{it} + \sum _{i \in W^-} \alpha _i (1 - x_i - x_s - x_t + y_{is} + y_{it} + y_{st})\\&\quad + \sum _{i \in R^-} \alpha _i y_{st} \le ({ \beta } - \alpha _s - \alpha _t) y_{st}. \end{aligned}$$

Observe that, in this form, the right-hand side is a constant for the given \(\alpha \), \(\beta \), s and t. Then, to find a most-violated (s, t) inequality, if any exists, it suffices to maximise the left-hand side. This can be done using the following algorithm. Consider each node \(i \in N {\setminus } \{s,t\}\) in turn. If \(\alpha _i > 0\), place i in one of the sets S, T, W or R, according to which of the following four quantities is largest: \(y^*_{is}+ y^*_{st} - x^*_s\), \(y^*_{it}+ y^*_{st} - x^*_t\), \(y^*_{is} + y^*_{it} - x^*_i\) and zero. (Ties can be broken arbitrarily.) If \(\alpha _i < 0\), place i in S, T, W or R according to which of the following four quantities is smallest: \(y^*_{is}\), \(y^*_{it}\), \(1 - x^*_i - x^*_s - x^*_t + y^*_{is} + y^*_{it} + y^*_{st}\) and \(y^*_{st}\). (Again, ties can be broken arbitrarily.) If \(\alpha _i = 0\), then i can be placed in an arbitrary set, since it has no effect on the violation. Note that, for any i, only a constant number of comparisons is needed. Therefore the algorithm runs in \(\mathcal{O}(n)\) time for the given \(\alpha \), \(\beta \), s and t.

3 Facet proof

In this Section, we provide the proof that under certain conditions, the family of (s, t) inequalities (7) are facet defining for the MEWCP. We can note from the cardinality constraint (1b) that the coefficients \(\alpha _i, i = 1,\ldots ,n\), are all positive and equal to 1, i.e. \(S = S^+, T = T^+, W = W^+, R = R^+\) and for each of these sets, the sum of coefficients \(\alpha \) is simply equal to its cardinality (for example \(\alpha (S) = |S|\)). For these reasons, the (s, t) inequality for the MEWCP can be written as follows:

$$\begin{aligned} \sum _{i \in S \cup W} y_{is} \, + \, \sum _{i \in T \cup W} y_{it} \, - \, \sum _{i \in W} x_i \, \le \, \, (|S|) x_s + \, (|T|) x_t \, + \left( b - 2 - |S|-|T| \right) y_{st}.\qquad \end{aligned}$$
(10)

For the rest of this paper, the set \(\mathcal {Q}\) corresponds to

$$\begin{aligned} {\mathcal {Q}:=conv\left\{ (x,y) \in \{0,1\}^{n+\left( {\begin{array}{c}n\\ 2\end{array}}\right) }:\, \sum _{i=1}^n x_i \le b, y_{ij} = x_ix_j \text { for } (i,j)\in E \right\} } \end{aligned}$$

Theorem 2

Let s, t , S, T and W be defined as in Sect. 2. If S and T are non empty, \(|S| \le b-2\), \( |T| \le b - 2\), \(W = \emptyset \) and \(|S\cup T| \ge b-1\), then the (s, t) inequalities (10) define facets of \(\mathcal {Q}\).

Note that with the settings of Theorem 2, the supporting graph of the (s, t) inequalities (10) is a double star tree as follows.

Proof

Under the hypothesis that \(W = \emptyset \), the (s, t) inequalities (10) becomes

$$\begin{aligned} \sum _{i \in S} y_{is} \, + \, \sum _{i \in T} y_{it} \le (|S|) x_s + \, (|T|) x_t \, + \left( b - 2 - |S|-|T| \right) y_{st}. \end{aligned}$$
(11)

Let \(F= \left\{ (x,y)\in \mathcal {Q}:\, (11)\text { holds with equality}\right\} \), and \(a(x,y) \le a_0\) i.e. let

$$\begin{aligned} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n + a_{12} y_{12} + a_{13} y_{13} + \cdots a_{n-1,n} y_{n-1,n} \le a_0 \end{aligned}$$

be an inequality valid for \(\mathcal {Q}\) such that every point \((x,y)\in F\) satisfies \(a(x,y)=a_0\). We will use some integer points in \(\mathcal {Q}\) that satisfy (11) to equality i.e integer points in F to find the coefficients a and \(a_0\) uniquely up to scalar multiplication.

Let \(e_i\) be \(i^{th}\) unit vector of size n, \(e_{ij}\) the \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \)-vector with all components equal to zero except the \((i,j)-th\) component which is equal to 1.

  1. 1.

    The vector \((x,y)=(0,0) \in F\); this implies that \(a_0=0\).

  2. 2.

    \((e_i,0) \in F\) for \(i\ne s,t\); this implies that \(a_i = 0\) for all \(i \ne s,t\). Note that the nodes s and t can be isolated in the set N without ambiguity since \(|S| \le b-2\) and \( |T| \le b - 2\).

  3. 3.

    \((e_i +e_j, e_{ij}) \in F\) for all \(i,j \ne s,t\) and \(i\ne j\); it follows that \(a_{ij}=0\) for all \(i,j \ne s,t\) and \(i\ne j\).

  4. 4.

    We now prove that \(a_{it} = 0\) for any node \(i\in N{\setminus }\left( T\cup \{s,t\}\right) \). Let \(i\in N{\setminus }\left( T\cup \{s,t\}\right) \), we define:

    • \(C^s_{it}\) to be a star tree with node set \(T\cup \{i,t\}\) (it is possible to have such a star tree since \(T \ne \emptyset \)) such that all the edges are incident to t. Since \(C^s_{it} \in F\), it follows that

      $$\begin{aligned} a_t + \sum \limits _{k \in T} a_{kt} + a_{it} =0 \qquad (i) \end{aligned}$$

    • \(C^i_{t}\) to be a star tree with node set \(T\cup \{t\}\) such that all the edges are incident to t this is the same as the star tree \(C^s_{it}\) without the edge (i, t). Since \(C^i_{t} \in F\), it follows that

      $$\begin{aligned} a_t + \sum \limits _{k \in T} a_{kt} = 0\qquad (ii) \end{aligned}$$

      Subtracting (ii) from (i) yields \(a_{it} = 0\) for \(i\in N{\setminus }\left( T\cup \{s,t\}\right) \).

  5. 5.

    Similarly to the above point, \(a_{js}= 0\) for \(j\in N{\setminus }\left( S\cup \{s,t\}\right) \), also using the fact that \(S \ne \emptyset \).

  6. 6.

    For \(i,j\in S\cup T\), we want to show that: a) \(a_{is} = a_{js}\) when \(i,j \in S\), b) \(a_{it} = a_{jt}\) when \(i,j \in T\), and c) \(a_{is} = a_{jt}\) when \(i \in S\) and \(j \in T\). Let \(i,j\in S\cup T\) with \(i\ne j\) and let \(A\subseteq S\cup T{\setminus } \{i,j\}\) such that \(|A| = b - 3\), (since \(|S\cup T| \ge b-1\)). Let \(C^j_{ist}\) be a double star tree with node set \(A\cup \{i,s,t\}\) obtained by linking all the nodes in \(A\cap S\) to s, all the nodes in \(A\cap T\) to t and connecting the node s to the node t.

    • Since \(C^j_{i,s,t} \in F\), it follows that

      $$\begin{aligned} a_s + a_t + \sum \limits _{k\in A\cap S} a_{ks} + \sum \limits _{k\in A\cap T} a_{kt} + a_{is} + a_{it} + a_{st} =0 \qquad (iii). \end{aligned}$$

    • Since \(C^i_{j,s,t} \in F\), it follows that

      $$\begin{aligned} a_s + a_t + \sum \limits _{k\in A\cap S} a_{ks} + \sum \limits _{k\in A\cap T} a_{kt} + a_{js} + a_{jt} + a_{st} =0 \qquad (iv). \end{aligned}$$

    Subtracting (iii) from (iv) yields \(a_{is} + a_{it} = a_{js} + a_{jt}\). So, using steps 4 and 5 we have the following:

    1. (a)

      If \(i,j \in S\) then \(a_{is} = a_{js}\).

    2. (b)

      If \(i,j \in T\) then \(a_{it} = a_{jt}\).

    3. (c)

      If \(i\in S\) and \(j\in T\), then \(a_{is} = a_{jt}\).

  7. 7.

    Using \(a_{it}=a_{jt}\) for \(i,j\in T\), as given by b) in the above point, and considering equation (ii), we have \(a_t + |T|a_{it} = 0\) for \(i\in T\). Therefore, \(a_{it} = -\dfrac{a_t}{|T|}\), (since \(T \ne \emptyset \)). Similarly, \(a_s + |S|a_{is} = 0\) for \(i\in S\), i.e \(a_{is} = -\dfrac{a_s}{|S|}\), (since \(S \ne \emptyset \)).

  8. 8.

    Let \(i \in S\) and \(j\in T\), we define the set A as in step 6 and denote \(\omega _s = |A\cap S| + 1\) and \(\omega _t = |A\cap T|\). It follows from (iii) that \(a_s + a_t + \omega _sa_{is} + \omega _ta_{jt} + a_{st} = 0\) i.e. \(a_{st} = - a_s - a_t +{ \dfrac{a_s\omega }{|S|} + \dfrac{a_t\omega _t}{|T|}}\) for \(i\in S\) and \(j\in T\).

  9. 9.

    Finally, considering the above steps, the inequality

    $$\begin{aligned} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n + a_{12} y_{12} + a_{13} y_{13} + \cdots a_{n-1,n} y_{n-1,n} \le a_0 \end{aligned}$$

    reduces to

    $$\begin{aligned} a_s x_s + a_t x_t + \sum \limits _{i\in S} a_{is} y_{is} + \sum \limits _{i\in T} a_{it} y_{it} + a_{st} y_{st} \le 0 \end{aligned}$$

    which, using the identities \(a_{is} = a_{jt}\), \(a_{jt} =- \dfrac{a_t}{|T|}\) and \(a_{is} = - \dfrac{a_s}{|S|}\) for \(i \in S, j \in T\), is equivalent to

    $$\begin{aligned} a_s x_s + a_t x_t - \dfrac{a_s}{|S|}\sum \limits _{i\in S} y_{is}- \dfrac{a_t}{|T|} \sum \limits _{i\in T}y_{it} + \left( { \dfrac{a_s\omega _s}{|S|} + \dfrac{a_t\omega _t}{|T|}} - a_s - a_t\right) y_{st} \le 0. \end{aligned}$$

    We finally have

    $$\begin{aligned} \dfrac{a_s}{|S|}\left[ |S| x_s + |T| x_t - \sum \limits _{i \in S} y_{is} - \sum \limits _{i \in T} y_{it} - (|S| + |T| - {\omega _s - \omega _t}) y_{st}\right] \le 0. \end{aligned}$$

    Since \((e_s,0)\) satisfies the inequality \(a(x,y) \le a_0\), i.e \(a_s \le 0\), and given that \(\omega _s + \omega _t = b - 2\), this ends the proof.