NDLI: SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances

Content Provider	Springer Nature Link
Author	Rinaldi, Giovanni Piacentini, Mauro Grippo, Luigi Piccialli, Veronica Palagi, Laura
Copyright Year	2012
Abstract	We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained $$\{-1,1\}$$ quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex 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 Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans–Williamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours.
Ending Page	373
Page Count	21
Starting Page	353
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	2
Volume Number	136
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-10-11
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Semidefinite programming Theoretical, Mathematical and Computational Physics Max-Cut Linear algebraic groups over finite fields Modular representations and characters Mathematical Methods in Physics Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Low rank factorization Unconstrained binary quadratic programming Nonlinear programming Combinatorics Maximal subgroups
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

Speedp: a new algorithm to compute the sdp relaxations of max-cut for very large graphs (2010).

SpeeDP: a new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

New approaches for optimizing over the semimetric polytope

Regularized Newton method for unconstrained convex optimization

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Binary positive semidefinite matrices and associated integer polytopes

SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances

Similar Documents

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

Speedp: a new algorithm to compute the sdp relaxations of max-cut for very large graphs (2010).

SpeeDP: a new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

New approaches for optimizing over the semimetric polytope

Regularized Newton method for unconstrained convex optimization

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Binary positive semidefinite matrices and associated integer polytopes

SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances