swMATH ID: 
7003

Software Authors: 
Grippo, Luigi; Palagi, Laura; Piacentini, Mauro; Piccialli, Veronica; Rinaldi, Giovanni

Description: 
SpeeDP: an algorithm to compute SDP bounds for very large maxcut instances
We consider lowrank semidefinite programming (LRSDP) relaxations of unconstrained \({1,1}\) quadratic problems (or, equivalently, of maxcut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the maxcut problem. We further include SpeeDP within a simply modified version of the GoemansWilliamson algorithm and we show that the corresponding heuristic SpeeDPMC can generate highquality cuts for very large, sparse graphs of size up to a million nodes in a few hours. 
Homepage: 
http://www.dis.uniroma1.it/~palagi/papers10/SpeeDP.pdf

Keywords: 
low rank factorization;
unconstrained binary quadratic programming;
maxcut;
nonlinear programming

Related Software: 
Biq Mac;
COL;
Algorithm 769;
Algorithm 815;
Tabu search;
DIMACS;
TTTPLOTS;
CirCut;
SDPA;
PERL;
GRASP;
QAPLIB;
QuadProgBB;
Ipopt;
YALMIP;
CPLEX;
CSDP;
PRMLT;
LIBSVM;
Benchmarks for Optimization Software

Referenced in: 
4 Publications
