library

A New Library of Structured Semidefinite Programming Instances

by E. de Klerk and R. Sotirov

In order to stimulate further development of codes for semidefinite programming (SDP), that include more sophisticated pre-processing techniques for problems with special structure, we present a new test set of SDP instances. The instances arise from applications of SDP in coding theory, computational geometry, graph theory, and truss topology design. Most of these instances have a structure that may be exploited during a pre-processing phase, e.g. algebraic symmetry, chordal structure, or low rank in the constraint matrices.

Documentation:

A new library of structured SDP instances, Optimization Methods and Software, 24(6):959-971, 2009 (preprint).

** The authors would also like to thank Katsuki Fujisawa, Hans Mittelmann, Maho Nakata, and Makoto Yamashita for providing more accurate optimal values for several of the SDP instances in the new library by using the SDPA–GMP solver.

The test instances come from the following applications of SDP:

• Estimation of the crossing number in graphs crossing

• Computing the theta and theta' of the Erdös-Renyi graphs

• Computing bounds in coding theory

• Computing bounds on kissing numbers in various dimensions

• SDP relaxation of the Quadratic Assignment Problem

• SDP relaxation of the Traveling Salesman Problem

• Truss topology design problems

• Free Material Optimization

All problems are stored in the SDPA sparse format:

Download a description of the file format.

Other test sets of SDP instnces:

Generator for difficult and degenerate random SDPs by Florian Jarre.

Output in SeDuMi format. If output in SDPA-format is needed download Brian Borchers's code for converting data from SeDuMi to SDPA-format to the same directory.

• SDPLIB

• DIMACS library

• Benchmarks for Optimization Software