Walid Ben-Ameur
email: walid.benameur@telecom-sudparis.eu

Antoine Glorieux
email: antoine.glorieux@telecom-sudparis.eu

José Neto
email: jose.neto@telecom-sudparis.eu

From graph orientation to unweighted maximum cut

In this paper, starting from graph orientation problems, we introduce some new mixed integer linear programming formulations for the unweighted maximum cut problem. Then a new semidefinite relaxation is proposed and shown to be tighter than the Goemans and Williamson's semidefinite relaxation. Preliminary computational results are also reported.

Introduction

Let G = (V , E) be a simple undirected graph, with node set V , edge set E, and let (w e ) e∈E denote nonnegative edge-weights. Given a node subset S ⊆ V , the cut defined by S, denoted by δ(S), is the subset of edges in E having exactly one endpoint in S, i.e. δ(S) = {ij ∈ E : |S ∩ {i, j}| = 1}. The weight of the cut defined by S, denoted by w(δ(S)) is the sum of the weights of the edges belonging to the cut, i.e., w(δ(S)) = e∈δ(S) w e . The maximum cut problem consists in finding a cut of maximum weight, denoted by w , in the graph G: max{w(δ(S)) : S ⊂ V }. The cardinality of V will be denoted by n.

The maximum cut problem is a fundamental combinatorial optimization problem that emerges in several scientific disciplines: VLSI design [START_REF] Barahona | An application of combinatorial optimization to statistical physics and circuit layout design[END_REF], sparse matrix computation [START_REF] Ashcraft | Using domain decomposition to find graph bisectors[END_REF], parallel programming [START_REF] Calzarossa | Workload characterization: a survey[END_REF], statistical physics [START_REF] Barahona | An application of combinatorial optimization to statistical physics and circuit layout design[END_REF], quadratic programming [START_REF] Hammer | Some network flow problems solved with pseudo-boolean programming[END_REF], etc. A less known application is given by frequency assignment in networks where the weight of each edge represents the interference level between two nodes. Assuming that only two frequencies (resources) are available, assigning a frequency to each node such that the whole interference between nodes using the same frequency is minimized is a maximum cut problem.

The maximum cut problem is known to be NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF] in general, and not approximable within a ratio 16 17 + for any > 0 unless P = NP [START_REF] Hastad | Some optimal inapproximability results[END_REF]. However, the problem may be polynomial for some instances. We know, for example, that the problem becomes easy when the underlying graph is weakly bipartite and the weights are nonnegative [START_REF] Grötschel | Weakly bipartite graphs and the max-cut problem[END_REF]. Other polynomial cases are reviewed, e.g., in [START_REF] Ben-Ameur | The Maximum Cut Problem, in Paradigms of Combinatorial Optimization[END_REF].

One line of research to solve this problem has consisted in the development of (meta)heuristics, see, e.g. [6,[START_REF] Festa | Randomized heuristics for the MAX-CUT problem[END_REF][START_REF] Sahni | P-complete approximation algorithms[END_REF]. Another important line of research relies on linear programming formulations of the problem. This has namely led to deep investigations on the polyhedral structure of the cut polytope: the convex hull of the incidence vectors of all the cuts of the graph, which has then been extensively used, e.g., in Branch and Cut algorithms [START_REF] Barahona | On the cut polytope[END_REF][START_REF] Ben-Ameur | The Maximum Cut Problem, in Paradigms of Combinatorial Optimization[END_REF][START_REF] Deza | Geometry of cuts and metrics[END_REF]. More recently, essentially since the mid-1990's and the breakthrough paper by Goemans and Williamson [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF], there has been a growing interest in semidefinite programming based algorithms. Goemans and Williamson's work presents a 0.87856-approximation algorithm for the maximum cut problem when the edge weights are nonnegative. Their method relies on the following semidefinite relaxation of the problem for a complete graph (SDP0)

         max 1 2 n i=1 n j=i+1 w ij (1 -y ij ) s.t. y ii = 1, ∀i ∈ 1, n , Y 0, Y ∈ S n ,
where Y represents the matrix with entry y ij in the ith row and jth column, Y 0 is the constraint that the matrix Y is positive semidefinite, and, for any given integer n, S n denotes the set of symmetric matrices with order n.

To improve the quality of the bound Z SDP0 given by the formulation (SDP0) [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF], different approaches have been proposed in the literature: namely by making use of polyhedral knowledge on the cut polytope and adding linear inequalities [START_REF] Fischer | Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition[END_REF][START_REF] Helmberg | A cutting plane algorithm for large scale semidefinite relaxations[END_REF], or by means of lift-and-project techniques [START_REF] Anjos | Strengthened semidefinite relaxations via a second lifting for the max-cut problem[END_REF][START_REF] Laurent | Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure[END_REF]. Another way to improve the upper bound given by the semidefinite relaxation is described in [START_REF] Ben-Ameur | Spectral bounds for the maximum cut problem[END_REF][START_REF] Ben-Ameur | Spectral bounds for unconstrained (-1, 1)-quadratic optimization problems[END_REF] where some spectral techniques are used leading to polynomial-time algorithms for some low rank weight matrices. This semidefinite approach of the problem also led to efficient solvers such as BiqMac [START_REF] Rendl | Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations[END_REF] and BiqCrunch [START_REF] Krislock | Improved semidefinite bounding procedure for solving Max-Cut problems to optimality[END_REF].

The reader can find in [START_REF] Ben-Ameur | The Maximum Cut Problem, in Paradigms of Combinatorial Optimization[END_REF][START_REF] Deza | Geometry of cuts and metrics[END_REF] and the references therein further results about the maximum cut problem including applications, polynomial cases, approximation algorithms, relationships with other combinatorial problems, polyhedral studies etc.

The paper is organized as follows. We introduce some new mixed integer linear programming formulations for the maximum cut problem based on graph orientations (Section 2). A semidefinite programming relaxation is then proposed. We show that the bound provided by this new SDP relaxation is stronger than the bound given by the relaxation (SDP0) introduced by Goemans and Williamson (Section 3). We also prove that the new bound is tight for complete graphs. We then introduce further Mixed Integer Programming formulations (Section 4). Several numerical experiments have been conducted showing the relevance of the SDP formulation and the performances of the new Mixed Integer Programming formulations (Section 6). A conclusion follows.

Mixed integer linear programming formulations

In this section, we gradually introduce our new formulation for the maximum cardinality cut problem, i.e. the maximum cut problem for the case when all the edge-weights are equal to 1: w e = 1, ∀e ∈ E. For our purposes, we shall think of the original graph G = (V , E) as directed (consider any arbitrary orientation) and let B ∈ {-1, 0, 1} |V |×|E| stand for its incidence matrix, i.e., the column corresponding to the arc uv (or, equivalently, to the edge uv directed from node u to node v), has only nonzero entries in the rows corresponding to the nodes u and v: B u,uv = 1 and B v,uv = -1, respectively.

For clarity, we start introducing an auxiliary formulation. It involves two types of variables. The first type of variables x ∈ {-1, 1} |E| describes an orientation of the graph G and may be interpreted as follows. For each edge ij ∈ E which is originally directed from node i to node j: if x ij = 1 then ij is directed from i to j (i.e., the orientation is the same as the original one) and is directed from j to i otherwise (i.e., the edge is "reversed" with respect to the original orientation). The other variables are binary and denoted y v k , with v ∈ V and k ∈ -d v , d v , where d v denotes the degree of the node v in G. They have the following interpretation:

y v k = 1 if and only if B v x = k
, where B v denotes the row of B corresponding to vertex v, so that the following equation trivially holds dv k=-dv

ky v k = B v x, ∀v ∈ V . ( 1
)
Notice that

B v x = d (x,+) v -d (x,-) v
, where d

(x,+) v (resp. d (x,-) v
) denotes the outdegree (resp. indegree) of the node v w.r.t. the orientation described by x.

Also, given the interpretation for the variables y, among those of the form y v k , for some fixed node v ∈ V , exactly one of them has value 1. Thus, the following contraints are satisfied dv k=-dv

y v k = 1, ∀v ∈ V . (2)
Then we can show the maximum cardinality cut problem may be formulated as the mixed-integer program (MIP1)

       Z MIP1 = 1 2 max v∈V dv k=-dv |k|y v k s.t. (1), (2), x ∈ [-1; 1] |E| , y v k ∈ {0, 1}, ∀v ∈ V , ∀k ∈ -d v , d v .
Proposition 1. The optimal objective value of (MIP1) equals the maximum cardinality of a cut in the graph G: Z MIP1 = w .

Proof. First, note that it is equivalent to take x ∈ [-1; 1] |E| or x ∈ {-1; 1} |E| since B is totally unimodular, the integrity of y implies the integrality of x.

Observe that introducing sign variables z ∈ {-1, 1} |V | with the following interpretation: z v is the sign of the only k for which y v k = 0, (MIP1) is equivalent to the following

       max 1 2 v∈V z v dv k=-dv ky v k s.t. (1), (2), y v k ∈ {0, 1}, ∀v ∈ V , ∀k ∈ -d v , d v , z ∈ {-1, 1} |V | , x ∈ [-1; 1] |E| . ⇔    max 1 2 v∈V z v B v x = 1 2 z t Bx s.t. z ∈ {-1, 1} |V | , x ∈ {-1, 0, 1} |E| . ⇔    max 1 2 uv∈E x uv (z v -z u ) = 1 2 x t B t z s.t. z ∈ {-1, 1} |V | , x ∈ {-1, 1} |E| . ⇔    max 1 2 uv∈E |z v -z u | s.t. z ∈ {-1, 1} |V | .
Noting that, for any z ∈ {-1, 1} |V | , the quantity uv∈E |z v -z u | equals twice the number of edges in δ(S), with S = {v ∈ V : z v = 1}, the proposition follows.

Remark 1. Given a cut δ(S) with maximum cardinality, we can associate to it the following feasible solution of (MIP1): the vector x corresponds to an orientation of all edges in the cut from S to V \ S, all other edges are not oriented (x uv = 0, ∀uv ∈ E \ δ(S)), and y v k = 1 if and only if k is equal to the outdegree minus the indegree w.r.t. the orientation given by x (ignoring edges which are not oriented). Then, for any edge uv ∈ E which has the original orientation from u to v (i.e. the one given by the matrix B), the following equation holds:

x uv = du k=1 y u k - dv k=1 y v k .
From the latter we deduce (developing the expression B v x):

dv k=-dv ky v k = B v x = uv∈E dv k=1 y v k - du k=1 y u k . ( 3
)
Observe also that each vertex v is incident to at least dv 2 edges in the maximum cut. This implies that the variables y v k with k ∈ {1-dv 2 , . . . , dv 2 -1} may be removed from formulation (MIP1), while Proposition 1 remains valid.

It follows that, in place of (MIP1), we may consider a formulation involving variables of the form y v k only: replace equations ( 1) by ( 3). For each vertex v, we only consider

y v k variables for k ∈ -d v , -dv 2 ∪ dv 2 , d v . We therefore denote for all v ∈ V , I - v = -d v , -dv 2 , I + v = dv 2 , d v and I v = I - v ∪ I + v . (MIP2)            Z MIP2 = 1 2 max v∈V k∈Iv |k|y v k s.t. k∈Iv y v k = 1, ∀v ∈ V , k∈Iv ky v k = uv∈E ( k∈I + v y v k -k∈I + u y u k ), ∀v ∈ V , y v k ∈ {0, 1}, ∀v ∈ V , ∀k ∈ I v .
Formulation (MIP2) involves about O(|E|) variables and O(|V |) constraints. It will be studied in a forthcoming paper. We will rather consider a strengthening of the linear relaxation of (MIP2) through reformulation-linearization techniques. The latter is obtained by multiplying constraints of (MIP2) and then linearizing. Some other constraints follow from the afore mentioned interpretation of the variables in (MIP2). So, let Y uv kl , with (u, v) ∈ V 2 , (k, l) ∈ I u × I v , denote a binary variable representing the product y u k y v l . Then, given that the variables y v k are binary and satisfy [START_REF] Ashcraft | Using domain decomposition to find graph bisectors[END_REF] we have Y uu kl = 0, ∀u ∈ V , ∀k = l. Considering then the product of the left side of (2) with itself we deduce k∈Iv Y vv kk = 1. Using other equations obtained by multiplying variables of the form y v k with equations (2) and others obtained from (3), we can deduce from (MIP2) the following exact formulation for the maximum cardinality cut problem.

(MIP3)                                                                  Z MIP3 = 1 2 max v∈V k∈Iv |k|Y vv kk s.t. k∈Iv Y vv kk = 1, ∀v ∈ V , k∈Iv kY vv kk = uv∈E ( k∈I + v Y vv kk - k∈I + u Y uu kk ), ∀v ∈ V , Y vv kk = l∈Iu Y vu kl , ∀u, v ∈ V , ∀k ∈ Iv, (dv -k)Y vv kk = uv∈E l∈I + u Y vu kl , ∀v ∈ V , ∀k ∈ I + v , -kY vv kk = uv∈E l∈I + u Y vu kl , ∀v ∈ V , ∀k ∈ I - v , l∈Iu lY vu kl = uw∈E ( l∈I + w Y vw kl - l∈I + u Y vu kl ), ∀v = u ∈ V , ∀k ∈ Iv, Y vu kl = Y uv lk , ∀u, v ∈ V , ∀(k, l) ∈ Iv × Iu, Y vu kl ∈ {0, 1}, ∀u, v ∈ V , ∀(k, l) ∈ Iv × Iu, (4a) (4b)
(4c) (4d) (4e) (4f) (4g) (4h)
Proposition 2. The optimal objective value of (MIP3) equals the maximum cardinality of a cut in the graph G: Z MIP3 = w .

Observe that (MIP3) was derived from (MIP2) using lifting. Other formulations could be obtained using some other well-known lifting techniques such as the one of Lassere, the Sherali-Adams technique or the lifting of Lovász-Schrijver [START_REF] Rothvoß | The Lasserre hierarchy in Approximation algorithms[END_REF][START_REF] Laurent | A Comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre Relaxations for 0-1 Programming[END_REF][START_REF] Wiegele | Nonlinear Optimization Techniques Applied to Combinatorial Optimization Problems[END_REF]. Since the aim of this paper is not to compare lifting techniques, we do not elaborate more on this topic.

A semidefinite programming bound

Let Y denote a symmetric matrix with rows and columns indexed by all pairs (u, k) with u ∈ V and k ∈ I u . The entry in the row indexed by (u, k) and column indexed by (v, l) corresponds to the variable Y uv kl . Then, let (SDP3) denote the relaxation obtained from (MIP3) replacing the symmetry (4g) and binary constraints (4h) by the following ones

Y -Diag(Y )Diag(Y ) t 0 (5) Y vu kl ≥ 0, ∀u, v ∈ V , ∀k ∈ I - v ∪ I + v , l ∈ I - u ∪ I + u , (6)
where Diag(Y ) denotes the vector corresponding to the diagonal of Y . We are going to prove that the semidefinite relaxation (SDP3) provides a generally better upper bound for the maximum cardinality cut problem than that from Goemans & Williamson's relaxation. For, consider the following semidefinite relaxation of a 0/1 formulation of the maximum cardinality cut problem whose optimal objective value coincides with Z SDP0 , (SDP4)

         Z SDP4 = max 1 2 u∈V v:uv∈E (x u + x v -2X uv ) s.t. Diag(X) = x, X -xx t 0, x ∈ R |V | , X ∈ S |V | ,
where X uv stands for the entry of the matrix X in the row corresponding to node u, and column corresponding to node v. Proposition 3. The following inequality holds Z SDP3 ≤ Z SDP4 (= Z SDP0 ).

Proof. Let Y denote a feasible solution for the formulation (SDP3) and let (X, x) ∈ R |V |×|V | ×R |V | be defined as follows:

X uv := -1 k=-du -1 l=-dv Y uv kl , ∀u, v ∈ V with u = v and X vv = x v := -1 k=-dv Y vv kk , ∀v ∈ V . We now show X -xx t 0. For, let z ∈ R |V |
and define z of convenient dimension as follows: z v k = z v if k < 0 and 0 otherwise. Then, we have

z t Y z = u∈V -1 k=-du v∈V -1 l=-dv z u k z v l Y uv kl = u∈V v∈V z u z v ( -1 k=-du -1 l=-dv Y uv kl ) = u∈V v∈V z u z v X uv = z t Xz. Also, z t Diag(Y ) = v∈V -1 k=-dv z v k Y vv kk = v∈V (z v -1 k=-dv Y vv kk ) = v∈V z v x v = z t x. It follows that z t (X -xx t )z = z t (Y -Diag(Y )Diag(Y ) t )z ≥ 0,
where the last inequality follows from the feasibility of Y w.r.t. (SDP3), and thus X -xx t 0. So, we have shown (X, x) is a feasible solution for (SDP4).

Since Y is symmetric, the same holds for X. We now show the objective value of (X, x) w.r.t. (SDP4), denoted Z X equals that of Y w.r.t. (SDP3).

Z X = 1 2 ( u∈V v : uv∈E (x u + x v -2X uv )) = v∈V d v x v -u∈V uv∈E X uv = v∈V d v -1 k=-dv Y vv kk -u∈V uv∈E -1 k=-du -1 l=-dv Y uv kl = v∈V d v -1 k=-dv Y vv kk -u∈V -1 k=-du (k + d u )Y uu kk = -u∈V -1 k=-du kY uu kk = u∈V du k=1 kY uu kk .
By Proposition 3, it follows that a randomized algorithm similar to the one by Goemans and Williamson [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF] but applied to an optimal solution Y of (SDP3) has the same approximation ratio. To be more precise, let Z ∈ R |V |×|V | denote the matrix with entries Z uv = 4(X uv -

x u x v ) + (2x u -1)(2x v -1)
, where

X uv := -1 k=-du -1 l=-dv Y uv kl , ∀u, v ∈ V with u = v and X vv = x v := -1
k=-dv Y vv kk , ∀v ∈ V . It can be checked that Z is a feasible solution for the formulation (SDP0) with the same objective value as Y . Then, let H ∈ R m×|V | (for some m ≤ |V |) denote a matrix such that Z = H t H and let r denote a vector which is randomly generated according to a uniform distribution on the unit sphere in R m . The cut returned by the algorithm is then δ(S) with S := {v ∈ V : r t h v ≥ 0}, where h v stands for the column of H corresponding to node v ∈ V .

The new bound is exact (i.e., equal to the maximum cardinality of a cut) for some graph classes. For space limitation reasons, we will only consider the case of complete graphs. We already know that the bound provided by relaxation (SDP0) is exact for even complete graphs (K n with n even). This does not hold for odd complete graphs. We prove that the bound given by (SDP3) is exact for all complete graphs. Proposition 4. For a complete graph, the optimal objective value of (SDP3) is exact:

Z SDP3 = w . Proof. See Appendix A.
In fact the proof of Proposition 4 implies implies that the linear relaxation of (MIP3) is exact. Details about this linear relaxation will follow in an extended version of the paper.

Further mixed integer linear programming formulations

In this section, we present three new exact formulations for the unweighted maximum cardinality cut problem with interesting computational performances. The first one stems from (MIP2) using the fact that for all v ∈ V , k∈I - v y v k = 1 -k∈I + v y v k deleting all the variables y v k where k is negative. We obtain the following exact formulation.

(MIP5)                Z MIP5 = max v∈V k∈I + v ky v k s.t. k∈I + v y v k ≤ 1, ∀v ∈ V , uv∈E ( k∈I + v y v k -k∈I + u y u k ) ≤ k∈I + v ky v k -dv 2 (1 -k∈I + v y v k ), ∀v ∈ V , uv∈E ( k∈I + v y v k -k∈I + u y u k ) ≥ k∈I + v ky v k -d v (1 -k∈I + v y v k ), ∀v ∈ V , y v k ∈ {0, 1}, ∀v ∈ V , ∀k ∈ I + v .
It involves about half as many variables as (MIP2) and has generally better performance, detailed results can be found in section 6. In order to further reduce the number of variables for an exact formulation, we can aggregate the variables y v k with k ∈ I + v for a vertex v to form a variable x v equal to k∈I + v y v k . For doing so, we need another variable z v equal to k∈I + v ky v k in order to keep the information about the difference between the outdegree and indegree of v important for the objective function. We thus obtain the following exact formulation.

(MIP6)            Z MIP6 = max v∈V z v s.t. dv 2 + dv 2 x v -z v ≤ uv∈E x u ≤ d v -z v , ∀v ∈ V , dv 2 x v ≤ z v ≤ d v x v , ∀v ∈ V , x ∈ {0, 1} V , z ∈ R V .
(MIP6) involves 2|V | variables, half of which are integer variables and its performance is better than that of (MIP5) for many instances (see Section 6). This formulation can also be obtained using the linearization technique of Glover [START_REF] Glover | Improved linear integer programming formulations of nonlinear integer problems[END_REF] applied to the standard quadratic program modeling the maximum cut problem. One can also propose a third formulation somewhat in between (MIP5), i.e. no aggregation of variables, and (MIP6), i.e. total aggregation of the variables for each vertex. To do so, we partition the interval I + v for each vertex v ∈ V . Let α > 1, we parametrize such a partition with α defining the following sequences

for each v ∈ V    a v 1 = dv 2 , a v i = 1 + b v i-1 , for i > 1, b v i = min( α * a v i , d v )
, and compute k v , the smallest integer such that b v kv = d v . Then similarly to the formulations (MIP1), (MIP2) and (MIP3), we take a variable y v k for each vertex v ∈ V and each k ∈ 1, k v whose interpretation is the following:

y v k = 1 if and only if z v ∈ a v k , b v k .
We therefore obtain the following exact formulation for all α > 1.

(MIP7[α])                Z MIP7 = max v∈V z v s.t. dv 2 + dv 2 x v -z v ≤ uv∈E x u ≤ d v -z v , ∀v ∈ V , kv k=1 y v k = x v , ∀v ∈ V , kv k=1 a v k y v k ≤ z v ≤ kv k=1 b v k y v k , ∀v ∈ V , x ∈ [0, 1] V , y v ∈ {0, 1} kv , ∀v ∈ V , z ∈ R V .
For the purpose of comparing performances, we now give a basic exact formulation for the unweighted maximum cut problem based on the triangle inequalities. It involves one variable x i,j for each unordered pair of vertices {i, j} ⊂ V (i = j). Hence O(n 2 ) variables and O(n 3 ) constraints.

(MIP8)          max ij∈E x i,j s.t. x i,j + x j,k + x i,k ≤ 2, ∀{i, j, k} ⊂ V , |{i, j, k}| = 3, x i,j + x j,k -x i,k ≥ 0, ∀(i, j, k) ∈ V 3 , |{i, j, k}| = 3, x i,j ∈ {0, 1}, ∀{i, j} ⊂ V , i = j.

Preliminary computational experiments

Some numerical experiments have been conducted to evaluate the quality of the new SDP bound. For each problem instance, we report w (the maximum cardinality of a cut), Z SDP0 (the optimal objective value of (SDP0)) and Z SDP3 (the optimal objective value of (SDP3)). We also mention some results related to the Mixed integer Programming formulations of the previous Section reporting the running time of (MIP2), (MIP5), (MIP6), (MIP7 [1.5]), (MIP7 [1.3]), (MIP7 [1.1]) and (MIP8) for each instance.

The algorithms used for these computations were written in C/C++ calling COIN-OR's CSDP library to solve the semidefinite programs and IBM's ILOG CPLEX optimizer c for the linear and mixed integer programs; all have been performed with a processor 1.9GHzx4, 15.6GB RAM. In order to further the relevance of our comparison, we also give for each instance the running time (BC) of the semi-definite based solver BiqCrunch [START_REF] Krislock | Improved semidefinite bounding procedure for solving Max-Cut problems to optimality[END_REF] compiled in Python and run on the same machine as the mixed integer programs.

The graph instances used for the computations are denoted as follows:

• K n : the complete graph with n vertices,

• W n : the wheel graph with n vertices (i.e. n -1 spokes),

• Pe, Co, Oc, Do and Ic: the Petersen graph, the Coxeter graph, the octahedron, the dodecahedron and the icosahedron respectively. (Information about the platonic graphs can be found in [START_REF] Read | An atlas of graphs[END_REF]), • C n : the cycle graph with n vertices, • G t2 n1,n2 : the 2-dimensional toroidal grid graph, i.e. the cartesian product of two cycles The random graphs were generated using rudy, a machine-independent graph generator by Giovanni Rinaldi. Let us start with the results related to the new SDP bound. The first set of instances considered consists of two basic graph classes : odd complete graphs and wheel graphs. One can see that Z SDP3 = w for complete graphs as shown in Proposition 4. The bound seems to be exact for wheels (according to numerical experiments). We report in Table 2 results obtained on some well-known graphs: the Petersen graph, the Coxeter graph, the octahedron, the dodecahedron and the icosahedron, along with some toroidal grid graphs. The results reported in Table 3 were computed from randomly generated graphs.

C n1 • C n2 , • G t k n : the n-dimensional toroidal grid graph of length k, i.e. the cartesian product • n i=1 C k , • R n
The preliminary computational results from Tables 1-3 not only confirm the inequality proved in Proposition 3, but clearly point out that the quality of the new bound presented in the previous Sections is sometimes significatively better than that of Goemans and Williamsons relaxation.

Let us now look at the running times of the Formulations (MIP8), (MIP2), (MIP5), (MIP6), (MIP7 [1.5]), (MIP7 [1.3]) and (MIP7 [1.1]) and of the solver (BC) on several bigger instances found in Table 4. For the entries marked ">900", the running time exceeded 900s and the process was therefore interrupted and for the entries marked "-", the memory of the machine was full and the process was therefore interrupted. First, one can see that the new formulations introduced in Section 4 perform much better than the classical triangular formulation (MIP8) for all the studied graph families except the general random graphs, and on all of these instances, there is one of our formulation that performs better than BiqCrunch does. More specifically, we can see that (MIP5) has generally better performance than (MIP2) and that for some instances, (MIP5) is drastically better than (MIP6), and for others, it is the other way around. Interestingly, we observe that being (MIP7) somewhat in between (MIP5) and (MIP6), there exists for almost each graph instance a value of α for which (MIP7[α]) has the shortest computing time. Practically, (MIP7[1.1]) seems to be the most robust of them.

Conclusion

Starting from graph orientation, we have seen that the maximum cut problem can be modeled in several new ways. By lifting, one can get some bounds that are stronger than the standard semidefinite bound of [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming[END_REF]. The bounds are even exact for some graph classes. Several new mixed integer programming formulations have been obtained using discretization and aggregation techniques. The performance of these formulations compares to and is often better than the performance of the BiqCrunch solver on many graph families, it can even be improved if we strengthen the formulations either by adding valid inequalities or using other lifting techniques. Also the new formulations we introduced here for the unweighted maximum cut problem may lead to similar formulations for the weighted case. This will be part of a forthcoming paper.

  ,d : a randomly generated graph with n vertices and density d: d = 200|E| n(n-1) , • P n,D : a randomly generated planar graph with n vertices and proportion of edges with respect to a maximum planar graph D: D = 100|E| 3(n-2) .

Table 1 .

 1 Computational results of (SDP3) for complete graphs and wheel graphs

	Instance K5 K7 K11 W5 W8	W10	W12	W15 W17 W20	W22 W25
	w	6	12	30	6	10	13	16	21	24 28	31	36
	Z SDP3 Z SDP0	6 6.25 12.25 30.25 6.25 10.614 13.809 16.979 21.875 25 29.566 32.703 37.5 12 30 6 10 13 16 21 24 28 31 36

Table 2 .

 2 Computational results of (SDP3) for special graph classes

	Instance Pe	Co Oc Do	Ic	C3 C5	C7	C9	C11	C13	C15
	w	12 36	8 24	20	2	4	6	8		10	12	14
	Z SDP3 Z SDP0	12 36.167 9 25 12.5 37.9 9 26.18 21.708 2.25 4.523 6.653 8.729 10.777 12.811 14.836 21 2 4 6.125 8.25 10.383 12.463 14.523
	Instance C17	C19	C21	C23	C25 G t 2 3,3 G	t 2 3,4 G t 2 3,5	G t 2 4,5	G	t 2 5,5	G	t 3 3
	w	16	18	20	22	24	12	20 22	36	40	54
	Z SDP3 Z SDP0	16.58 18.621 20.653 22.685 24.709 13.5 20 23.639 36 16.855 18.87 20.883 22.893 24.901 13.5 21 24.818 38.09 45.225 60.75 44.168 60

Table 3 .

 3 Computational results of (SDP3) for randomly generated graphs

	Instance R5,8 R10,9 R10,14 R10,18 R10,23 R10,27 R10,34 R10,36 R15,21 R15,32 R15,42
	w	6	8	12	14	17	19	22	23	17	24	30
	Z SDP3 Z SDP0	6 6.25 8.25 12.585 14.399 17.603 19.962 22.676 23.346 18.006 25.357 31.569 8 12 14 17 19 22 23 17 24.236 30.381
	Instance R15,53 R20,19 R20,38 R20,57 R30,44 P5,7 P5,9 P10,10 P10,12 P10,18 P10,24
	w	36	16	29	43	37	5	6	8	10	13	16
	Z SDP3 Z SDP0	36.567 16 37.39 16.679 30.682 44.757 39.005 5.432 6.25 8.409 10.715 13.932 16.992 29.202 43 37.31 5 6 8 10 13 16
	Instance P20,11 P20,16 P20,27 P20,41 P20,54 P25,35 P25,52 P25,69 P30,8 P30,17 P30,42
	w	9	15	21	30	36	28	39	46	7	15	33
	Z SDP3 Z SDP0	9 9.25 15.25 22.495 31.289 38.131 29.705 40.614 48.468 7.25 15.25 34.412 15 21 30 36.207 28.091 39 46.446 7 15 33.037

Table 4 .

 4 Running time for the MIP formulations (in seconds)

	Instance w	MIP8 MIP2 MIP5 MIP6 MIP7	MIP7	MIP7	BC |V |	|E|
							[1.5]	[1.3]	[1.1]
	R20,90	99	3	1	1	3	1	1	1	0	20	171
	R25,50	97	7	63	9	1	2	5	5	1	25	150
	R25,90	152	71	12	3	11	20	16	4	0	25	270
	R30,50	141	30 341	71	13	21	26	39	1	30	217
	R30,90	219 >900	44	21 144	111	99	23	0	30	391
	R40,25	136	29 >900 748	33	49	47	114	1	40	195
	P50,50	373	2	1	0	0	0	0	0	3	46	72
	P50,90	598	3	17	10	2	2	1	1	4	50	129
	P75,40	75	89	0	0	1	0	1	0	5	66	87
	P75,50	90	77	2	1	1	1	1	0	6	70	109
	P75,70	120	22	7	5	1	1	1	2	2	75	153
	P75,100	146 >900 >900 >900 172 >900	62	38	47	75	219
	P100,40	100	73	0	1	0	0	1	0	8	87	117
	P100,90	190 168 >900 >900	47	102	35	34	40	100	264
	P200,50	246 >900 >900 272	75	47	31	26 304	188	297
	P300,50	376	-	>900 >900	340	203	64	53 >900	282	447
	K50	625 >900	2	1	0	0	0	0	0	50 1225
	K100	2500 >900	17	7	4	1	1	1	64	100 4950
	K150	5625 >900 179	42	29	4	3	3 166	150 11175
	K175	7656 >900 322	77 >900 >900 >900	3	5	175 15225
	K200	10000 >900 704 145	4	7	4	6 368	200 19900
	K225	12656 >900 >900 223 >900 >900 >900	8	11	225 25200
	K300	22500	-	>900	875 >900 >900	106	208 177	300 44850
	G t 4 4 G t 2 10,10 G t 2 8,15 G t 2 11,12 G t 2 15,20 G t 2 20,20 G t 2 100,100 20000 1024 >900 200 121 232 >900 252 >900 580 >900 >900 >900 0 1 0 0 2 1 40 8 800 >900 0 0 -7 29	0 0 1 2 86 0 43	0 0 0 2 75 0 45	0 0 1 1 32 1 17	1 0 0 2 32 150 19 2 6 5 0 109 17 >900 10000 20000 256 1024 100 200 120 240 132 264 300 600 400 800
	W75	111	26	2	3	1	1	0	1	4	75	148
	W100	148	58	2	7	5	3	0	1	11	100	198
	W175	261 >900	9 333	22	14	1	1	44	175	348
	W250	373 >900	61 >900	26	26	2	2 301	250	498
	W400	598 >900	62 >900 >900 >900	4	3 >900	400	798
	W550	823	-	>900 >900 >900 >900	5	5 >900	550 1098
	W775	1161	-	>900 >900 >900 >900	11	10	-	775 1548
	W925	1386	-	>900 >900 >900	626	15	15	-	925 1848
	W1250	1873	-	>900 >900 >900 >900	34	39	-	1250 2548
	C100	100 105	0	0	0	0	0	0	5	100	100
	C175	174 889	0	0	0	0	0	0	31	175	175
	C250	250 >900	0	0	0	0	0	0	71	250	250
	C550	550	-	1	0	0	0	0	0 >900	550	550
	C1250	1250	-	0	0	0	0	1	0	-	1250 1250
	C1750	1750	-	1	0	1	1	1	0	-	1750 1750
	C3000	3000	-	1	1	2	1	1	2	-	3000 3000
	C5725	5725	-	13	12	37	13	11	13	-	5725 5725
	C9000	9000	-	2	7	10	8	7	7	-	9000 9000

Appendix A Proof of Proposition 4

Since Z SDP0 is exact for even complete graphs, Z SDP3 is also exact by Proposition 3. Let us now consider odd complete graphs. Let Y be an optimal solution of (SDP3). Let π be any permutation of the set of vertices. By symmetry of the complete graph, the solution defined by Y π(u)π(v) kl = Y uv kl is obviously still an optimal solution of (SDP3). By considering the set of all permutations Π n (the symmetric group), and combining all solutions, we still get an optimal solution (by linearity) Z where

. Since we consider all permutations, Z uv kl does not depend on u and v. In other words, there are numbers f (k, l) and g(k) such that

Let us build another solution Z of (SDP3) as follows:

. By symmetry of complete graphs, Z is also an optimal solution of (SDP3). Then, Z = 1 2 (Z + Z ) is also optimal. Observe that Z" uv kl = Z" uv (-k)(-l) . This implies that we can assume that g(k) = g(-k) and f (k, l) = f (-k, -l).

Moreover, constraints (4a) lead to

From (4c), we deduce that

Using equalities (4d), we can also write that

Considering (4f) for a positive k, we obtain l∈ n-1

Combining ( 8) and ( 9), we deduce that

Observe that [START_REF] Dolezal | A comparison of approximation algorithms for the MaxCut problem[END_REF] implies that when

. We can then assume in the rest of the proof that k < n -1.

Observe that the left side of (10) satisfies

where the last equality is induced by [START_REF] Dolezal | A comparison of approximation algorithms for the MaxCut problem[END_REF]. Let k max be the largest k such that f (k, l) = 0 for some l. We already know that k max ≤ n -2. The right side of (10) necessarily satisfies

Combining the two previous inequalities together with [START_REF] Deza | Geometry of cuts and metrics[END_REF], we obtain

By considering the case k = k max in ( 12), the sum

In other words, we necessarily have k max ≤ n+1

2 . This implies that g(k) = 0 and f (k, l) = 0 if either k > n+1 2 or k < -n+1 2 (we use here the fact that g(k) = g(-k) and ( 8)). Writing ( 10) and ( 11) for k = n-1 2 and k = n+1 2 , we get the next 4 equations.

(n -1)f (

) ( 16)

Substracting ( 13) from ( 14) leads to f

. By nonnegativity of the f values, we deduce that f

). Substracting (n -1)×( 15) from ( 16) leads in a similar way to f

2 ). Using [START_REF] Calzarossa | Workload characterization: a survey[END_REF] and the previous observations we get that:

Using the fact that f ( n+1 2 , 1-n 2 ) = f ( n-1 2 , -n-1 2 ) and g( n+1 2 ) + g( n-1 2 ) = 1 2 , one can deduce that f ( n-1 2 , -n-1 2 ) = n+1 8n . Consequently, g( n+1 2 ) = n-1 4n and g( n-1

2 ) = n+1 4n . Remember that Z SDP3 = 1 2 v∈V k |k|Y vv kk = v∈V k>0 kY vv kk , leading to Z SDP3 = n n+1 2 g( n+1 2 ) + n-1 2 g( n-1 2 ) = n 2 -1 4 , and ending the proof.