  


SpeeDP: A new algorithm to compute the SDP relaxations of MaxCut for very large graphs
Luigi Grippo(grippodis.uniroma1.it) Abstract: 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. When the rank of solution matrix is bounded by a given value (independent on the problem size n), SpeeDP is still able to provide a valid upper bound for MaxCut. This feature makes it possible to design an algorithm, called SpeeDPMC and based on the GoemansWilliamson heuristic, that has two interesting features: (a) it provides heuristic solutions to MaxCut along with a guaranteed optimality error; (b) it runs with a O(n+m) memory requirement (where m is the number of edges of the graph), thus overcoming a serious drawback of interior point based methods that demand O(n^2) memory. Exploiting the latter feature, we could run it on very large graphs with sizes of up to a million nodes, obtaining very small optimality error bounds in reasonable computation times. Keywords: Semidefinite programming, low rank factorization, unconstrained binary quadratic programming, MaxCut, nonlinear programming. Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Combinatorial Optimization Citation: Technical Report DIIUTOVRM 13.10 Dipartimento di Ingegneria dell'Impresa University of Rome Tor Vergata, 09/2010 Download: [PDF] Entry Submitted: 10/15/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  