Henry Wolkowicz's Research

Research Home
Publications & Abstracts
Talks & Presentations
Semidefinite
Programming
EDM
and SNL
Graph
Partitioning

Maximum
Cut

Linear
Programming
Quadratic
Assignment

NLP,
Regularization,
TRS
Set
Partitioning
Matrix
Approximation
Misc. Software/Opt. Matrices
and
Optimization

Maximum Cut

 

Algorithms and Benchmarks



The research report Simple Efficient Solutions for Semidefinite Programming
describes an algorithm that can be applied to solve the SDP relaxation of the max-cut problem. Numerical tests were done using MATLAB 6 with the files in this directory.
Also available: a ps file with the latest numerical test.
    Please note that these are MATLAB files. They do not include mex files. Therefore the speed is misleading when compared to other packages that are written in compiled languages. In addition, these files are under constant improvement. The CPU times are significantly better than those reported in the above cited Research Report.
The algorithm is based on an inexact Gauss-Newton (GN) method using preconditioned conjugated gradients (PCG) to solve the least squares problem.

Important features: q-quadratic convergence and high accuracy.

We use the PCG-type algorithm LSQR written (in MATLAB) by Michael Saunders and available on his web page.

Available from Hans Mittelmann:
benchmarks for two max-cut problems from SDPLIB (mcp250-1, mcp500-1),
for several packages.
Further details about the problems are available from SDPLIB.

See also Gset, a group of graph problems from Yinyu Ye
(from Brian Borchers' web page).

 






Last Modified:  Friday 22 December 2006