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


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


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


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.


  personal loan . In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.