This GitHub repository is a "modern" presentation of the original SDPLIB 1.2 library by Brian Borchers hosted at http://euler.nmt.edu/~brian/sdplib/sdplib.html.

If you use SDPLIB and wish to cite it, please refer to:

Borchers, B., SDPLIB 1.2, A Library of Semidefinite Programming Test Problems. Optimization Methods and Software. 11(1):683-690, 1999.

This is version 1.2 of SDPLIB. The only change in this version of SDPLIB is that problem hinf37 has been removed- the problem was removed because it was identical to problem hinf9.

The data directory contains the SDPLIB collection of semidefinite programming test problems. There are a total of 92 problems in the collection. All problems are stored in the SDPA sparse format [5].

The following table describes the problems, and gives optimal objective values that have been computed by SDPA and cross checked against results from the problem originators. Note that in some cases, very slight changes in the optimal objective function value have occurred as a result of the conversion into SDPA format. Furthermore, different authors have adopted different conventions for the primal and dual SDP problems. The results reported here are based on the SDPA conventions- thus some objective function values have their signs changed, and primal or dual infeasibility means infeasibility with respect to SDPA's primal and dual.

1. These truss topology design problems were contributed by Katsuki Fujisawa. They are originally from [8].

2. These problems from control and system theory were contributed by Katsuki Fujisawa [4].

3. These graph equipartition problems were supplied by Steve Benson [2]. The random graphs were originally generated by Christoph Helmberg and Franz Rendl [7].

4. These graph partitioning problems were contributed by Katsuki Fujisawa [4][6].

5. These linear matrix inequalities from control systems engineering are taken from the SDPPACK web site [1]. The problems were originally developed by P. Gahinet.

6. These infeasible problems were generated by a MATLAB procedure provided by Mike Todd.

7. These max cut problems were supplied by Steve Benson [2]. The random graphs were originally generated by Christoph Helmberg and Franz Rendl [7].

8. These max cut problems were contributed by Katsuki Fujisawa [4].

9. These quadratic assignment problems were contributed by Katsuki Fujisawa [6].

10. These SDP relaxations of box constrained quadratic programming problems were supplied by Steve Benson [2]. The random graphs were originally generated by Christoph Helmberg and Franz Rendl [7].

11. These Lovasz theta problems are taken from [3].

12. These Lovasz theta problems were contributed by Steve Benson [2]. The random graphs were originally generated by Christoph Helmberg and Franz Rendl [7].

13. These truss topology design problems are taken from the SDPPACK web site [1]. The problems were originally developed by A. Nemirovski.

The SDP problems in this directory are all encoded in the SDPA sparse format [5]. This file provides a description of the file format.

We work with a semidefinite programming problem that has been written in the following standard form:

(P)    min   c1*x1+c2*x2+...+cm*xm
       s.t.  F1*x1+F2*x2+...+Fm*xm - F0 = X
                                     X >= 0

The dual of the problem is:

(D)    max   tr(F0*Y)
       s.t.  tr(Fi*Y) = ci    i = 1,2,...,m
                   Y >= 0

Here all of the matrices F0, F1, ..., Fm, X, and Y are assumed to be symmetric of size n by n. The constraints X >= 0 and Y >= 0 mean that X and Y must be positive semidefinite.

Note that several other standard forms for SDP have been used by a number of authors- these can generally be translated into the SDPA standard form with little effort.

The file consists of six sections:

1. Comments. The file can begin with arbitrarily many lines of comments. Each line of comments must begin with " or *.

2. The first line after the comments contains m, the number of constraint matrices. Additional text on this line after m is ignored.

3. The second line after the comments contains nblocks, the number of blocks in the block diagonal structure of the matrices. Additional text on this line after nblocks is ignored.

4. The third line after the comments contains a vector of numbers that give the sizes of the individual blocks. The special characters ,, (, ), {, and } can be used as punctuation and are ignored. Negative numbers may be used to indicate that a block is actually a diagonal submatrix. Thus a block size of -5 indicates a 5 by 5 block in which only the diagonal elements are nonzero.

5. The fourth line after the comments contains the objective function vector c.

6. The remaining lines of the file contain entries in the constraint matrices, with one entry per line. The format for each line is

   <matno> <blkno> <i> <j> <entry>
   

Here <matno> is the number of the matrix to which this entry belongs, <blkno> specifies the block within this matrix, <i> and <j> specify a location within the block, and <entry> gives the value of the entry in the matrix. Note that since all matrices are assumed to be symmetric, only entries in the upper triangle of a matrix are given.

min   10 * x1 + 20 * x2

s.t.  X = F1 * x1 + F2 * x2 - F0
      X >= 0

where

F0 = [1 0 0 0
      0 2 0 0
      0 0 3 0
      0 0 0 4]

F1 = [1 0 0 0
      0 1 0 0
      0 0 0 0
      0 0 0 0]

F2 = [0 0 0 0
      0 1 0 0
      0 0 5 2
      0 0 2 6]

In SDPA sparse format, this problem can be written as:

"A sample problem.
2 =mdim
2 =nblocks
{2, 2}
10.0 20.0
0 1 1 1 1.0
0 1 2 2 2.0
0 2 1 1 3.0
0 2 2 2 4.0
1 1 1 1 1.0
1 1 2 2 1.0
2 1 2 2 1.0
2 2 1 1 5.0
2 2 1 2 2.0
2 2 2 2 6.0

1. F. Alizadeh, J.P. Haberly, M. V. Nayakkankuppam, M. L. Overton, and S. Schmieta. SDPpack user's guide- version 0.9 beta, Technical Report 1997-737, Courant Institute of Mathematical Sciences, NYU, New York NY, June 1997. https://cs.nyu.edu/media/publications/TR1997-737.pdf

2. S. J. Benson, Y. Ye, and X. Zhang. Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization, SIAM J. Optim., 10-2 (2000), 443–461. DOI: 10.1137/S1052623497328008

3. B. Borchers. CSDP, a C library for semidefinite programming, Optimization Methods and Software, 11:1-4 (1999), 613-623, DOI: 10.1080/1055678990880576

4. K. Fujisawa, M. Fukuda, M. Kojima, and K. Nakata. Numerical Evaluation of SDPA (Semidefinite Programming Algorithm). In: Frenk H., Roos K., Terlaky T., Zhang S. (eds) High Performance Optimization. Applied Optimization, vol 33., Springer (2000), Boston, MA. DOI: 10.1007/978-1-4757-3216-0_11

5. K. Fujisawa, M. Kojima, and K. Nakata. SDPA (Semidefinite Programming Algorithm) User's Manual, Technical Report B-308, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology. Revised, May, 1998. http://www.is.titech.ac.jp/~kojima/articles/b-308.pdf

6. K. Fujisawa, M. Kojima and K. Nakata. Exploiting Sparsity in Primal-Dual Interior-Point Methods for Semidefinite Programming, Mathematical Programming, 79(1997):235-253. DOI: 10.1007/BF02614319

7. C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming, SIAM J. Optim., 10-3 (2000), 673–696. DOI: 10.1137/S1052623497328987

8. T. Nakamura and M. Ohsaki. A Natural Generator of Optimum Topology of Plane Trusses for Specified Fundamental Frequency, Computer Methods in Applied Mechanics and Engineering 94(1992):113-129. DOI: 10.1016/0045-7825(92)90159-H

• June 28, 1999: Removed problem hinf37, which was identical to problem hinf9.

• July 24, 1998: Reduced the size of many problem files by removing extraneous and unneeded zeros. For example, 1.00000e+00 is shortened to 1.0.

• July 27, 1998: Slightly more accurate optimal objective function values for some problems.

• September 18, 1998: Added 11 new problems provided by Steve Benson.