## Invited Session Wed.1.H 2036

#### Wednesday, 10:30 - 12:00 h, Room: H 2036

**Cluster 4: Conic programming** [...]

### New conic optimization approaches for max-cut and graph equipartition

**Chair: Miguel F. Anjos**

**Wednesday, 10:30 - 10:55 h, Room: H 2036, Talk 1**

**Nathan Krislock**

Improved semidefinite bounding procedure for solving max-cut problems to optimality

**Coauthors: Jérôme Malick, Frédérick Roupin**

**Abstract:**

We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them can be controlled by two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.

**Wednesday, 11:00 - 11:25 h, Room: H 2036, Talk 2**

**Andreas Schmutzer**

Branch-and-cut for the graph 2-equipartition problem

**Coauthors: Miguel F. Anjos, Frauke Liers, Gregor Pardella**

**Abstract:**

A minimum 2-equipartition of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such that the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefinite relaxations for the equicut problem and find that linear bounds are competitive with the corresponding semidefinite ones but can be computed much faster. We further present detailed computational evaluations for a branch-and-cut algorithm using linear relaxations.

**Wednesday, 11:30 - 11:55 h, Room: H 2036, Talk 3**

**Angelika Wiegele**

Lasserre hierarchy for max-cut from a computational point of view

**Coauthors: Elspeth Adams, Miguel Anjos, Franz Rendl**

**Abstract:**

The max-cut problem is one of the classical NP-complete problems

defined on graphs. SDP-relaxations turned out to be in particular

successful on these problems. Beside the basic semidefinte relaxation

(underlying the Goemans-Williamson hyperplane rounding algorithm) and

tightenings of this relaxation, iterative approaches exist that converge towards the cut polytope. Such a systematic hierarchy was introduced by Lasserre. The first relaxation in this hierarchy coincides with the basic SDP relaxation. Due to the high computational

cost, already the second relaxation in this Lasserre-hierarchy is

intractable for small graphs.

We present an iterative algorithm for computing a strengthened

SDP-relaxation towards this second relaxation combined with constraints from the metric polytope. This can also be viewed as a strengthening of the basic SDP relaxation using semidefinte cuts. We present theoretical facts and report preliminary computational results.