This archive contains the code accompanying the technical report Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs. Here is the online appendix that accompanies the paper.

SDPLR is a C package for solving large-scale semidefinite programming problems. An easy-to-use Matlab interface is provided.

The current version is 1.03-beta (June 30, 2009). Click here for changes.

People involved in the development of SDPLR are:

• Samuel Burer (University of Iowa)
• Renato D.C. Monteiro (Georgia Tech)
• Changhui Choi (University of Colorado Denver)

Please feel free to contact samuel-burer@uiowa.edu with any questions, comments, requests or bug reports.

The development of SDPLR has been supported from 1998 by NSF grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113, CCR-0203426, and CCF-0545514, as well as by ONR grant N00014-03-1-0401.

Source Code

• SDPLR-1.03-beta.zip
• Source code broswer

User's Guide

• SDPLR-1.03-beta-usrguide.pdf

Binaries

• Windows binary

Previous Versions

• SDPLR-1.02 – Link to directory containing source code, binaries, etc.

• SDPLR-1.01 – Link to directory containing source code, binaries, etc.

• SDPLR-1.0 – Link to directory containing source code, binaries, etc.

• SDPLR v0.130301.tar.gz – This version contains specialized codes for the maximum cut, minimum bisection, and Lovász theta SDPs and hence, for these problem classes, may be quicker than SDPLR v1.0, which is a general purpose code.

Primary (please cite first)

• S. Burer and R.D.C. Monteiro. A Nonlinear Programming Algorithm for Solving Semidefinite Programs Via Low-Rank Factorization. Mathematical Programming (series B), 95(2):329-357, 2003.

Secondary

• S. Burer and R.D.C. Monteiro. Local Minima and Convergence in Low-Rank Semidefinite Programming. Mathematical Programming (series A), 103(3):427-444, 2005.

• S. Burer and C. Choi. Computational Enhancements in Low-Rank Semidefinite Programming. Optimization Methods and Software, 21(3):493-512, 2006.

Related

• S. Burer and R.D.C. Monteiro. A Projected Gradient Algorithm for Solving the Maxcut SDP Relaxation. Optimization Methods and Software, 15(3-4):175-200, 2001.

SDPLR on the Internet

Try SDPLR over the Web at the NEOS Server for Optmization. Thanks to Hans Mittelmann for the NEOS implementation.

• Matlab binary input
• Sparse SDPA input

Large-Scale Test Problems

Sparse SDPA format

• Hans Mittelmann's collection
• Electronic structure SDPs (hosted by M. Fukuda)
• Structural optimization SDPs (hosted by M. Kocvara)
• SDPs with special structure (hosted by E. de Klerk and R. Sotirov)

SDPLR format (hosted by S. Burer)

• Maxcut SDPs
• Lovász theta SDPs
• DIMACS Challenge
• SDPLIB
• Hans Mittelmann's collection

Other Test Problems

• SDPLIB (hosted by B. Borchers)

Links

• Sparse SDPA format
• Hans Mittelmann's benchmark
• CSDP
• DSDP
• Pennon
• SBMethod
• SDPA
• SDPT3
• SeDuMi
• YALMIP

Max-AO is a C package for heuristically solving the (unweighted) maximum stable set and maximum clique problems from graph theory. The details of the algorithm behind Max-AO can be found in the paper “Maximum Stable Set Formulations and Heuristics Based on Continuous Optimization” written by Samuel Burer, Renato D.C. Monteiro, and Yin Zhang.

• The current version of Max-AO is version 0.120301; click to download.
• Download the paper.

Extremely fast, scalable, Goemans-Williamson-quality heuristics for the maximum cut problem, maximum bisection problem, and other graph partitioning problems; maintained by Yin Zhang of Rice University. Click here.