SDPLIB 1.2, Revised, September 20, 2009. This is an updated README for version 1.2 of SDPLIB, which was originally released on Jun 28, 1999. The actual problems have not been changed since 1999. However, better solutions have since been obtained for many of the problems- these solutions are described here. This 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 CSDP (and with a quadruple precision version of CSDP on some of the numerically challenging problems) 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. Problem m n Optimal Objective Value Notes arch0 174 335 5.6651727e-01 1 arch2 174 335 6.7151539e-01 1 arch4 174 335 9.7262741e-01 1 arch8 174 335 7.0569800e+00 1 control1 21 15 1.7784627e+01 2 control2 66 30 8.3000000e+00 2 control3 136 45 1.3633266e+01 2 control4 231 60 1.9794230e+01 2 control5 351 75 1.6883599e+01 2 control6 496 90 3.7304413e+01 2 control7 666 105 2.0625072e+01 2 control8 861 120 2.0286360e+01 2 control9 1081 135 1.4675425e+01 2 control10 1326 150 3.8533032e+01 2 control11 1596 165 3.1958667e+01 2 eqaulG11 801 801 6.2915529e+02 3 equalG51 1001 1001 4.0056013e+03 3 gpp100 101 100 -4.4943551e+01 4 gpp124-1 125 124 -7.3430761e+00 4 gpp124-2 125 124 -4.6862295e+01 4 gpp124-3 125 124 -1.5301413e+02 4 gpp124-4 125 124 -4.1898763e+02 4 gpp250-1 250 250 -1.5444917e+01 4 gpp250-2 250 250 -8.1868959e+01 4 gpp250-3 250 250 -3.0353932e+02 4 gpp250-4 250 250 -7.4732831e+02 4 gpp500-1 501 500 -2.5320544e+01 4 gpp500-2 501 500 -1.5606039e+02 4 gpp500-3 501 500 -5.1301760e+02 4 gpp500-4 501 500 -1.5670188e+03 4 hinf1 13 14 2.0325997e+00 5 hinf2 13 16 1.0967056e+01 5 hinf3 13 16 5.6940778e+01 5 hinf4 13 16 2.7476383e+02 5 hinf5 13 16 3.62e+02 5 hinf6 13 16 4.4892775e+02 5 hinf7 13 16 3.90812e+02 5 hinf8 13 16 1.16146e+02 5 hinf9 13 16 2.3624926e+02 5 hinf10 21 18 1.087118e+02 5 hinf11 31 22 6.5862e+01 5 hinf12 43 24 2e-1 5 hinf13 57 30 4.434e+01 5 hinf14 73 34 1.29898e+01 5 hinf15 91 37 2.395e+01 5 infd1 10 30 dual infeasible 6 infd2 10 30 dual infeasible 6 infp1 10 30 primal infeasible 6 infp2 10 30 primal infeasible 6 maxG11 800 800 6.2916478e+02 7 maxG32 2000 2000 1.5676396e+03 7 maxG51 1000 1000 4.0062555e+03 7 maxG55 5000 5000 1.2869867e+04 7 maxG60 7000 7000 1.5222268e+04 7 mcp100 100 100 2.2615735e+02 8 mcp124-1 124 124 1.4199048e+02 8 mcp124-2 124 124 2.6988017e+02 8 mcp124-3 124 124 4.6775011e+02 8 mcp124-4 124 124 8.6441186e+02 8 mcp250-1 250 250 3.1726434e+02 8 mcp250-2 250 250 5.3193008e+02 8 mcp250-3 250 250 9.8117257e+02 8 mcp250-4 250 250 1.6819601e+03 8 mcp500-1 500 500 5.9814852e+02 8 mcp500-2 500 500 1.0700568e+03 8 mcp500-3 500 500 1.8479700e+03 8 mcp500-4 500 500 3.5667380e+03 8 qap5 136 26 -4.3600000e+02 9 qap6 229 37 -3.8143840e+02 9 qap7 358 50 -4.2481971e+02 9 qap8 529 65 -7.5695525e+02 9 qap9 748 82 -1.4099411e+03 9 qap10 1021 101 -1.0926075e+01 9 qpG11 800 1600 2.4486591e+03 10 qpG51 1000 2000 1.1818000e+03 10 ss30 132 426 2.0239511e+01 1 theta1 104 50 2.3000000e+01 11 theta2 498 100 3.2879169e+01 11 theta3 1106 150 4.2166981e+01 11 theta4 1949 200 5.0321222e+01 11 theta5 3028 250 5.7232307e+01 11 theta6 4375 300 6.3477087e+01 11 thetaG11 2401 801 4.0000000e+02 12 thetaG51 6910 1001 3.4900000e+02 12 truss1 6 13 -8.9999963e+00 13 truss2 58 133 -1.2338036e+02 13 truss3 27 31 -9.1099962e+00 13 truss4 12 19 -9.0099963e+00 13 truss5 208 331 -1.3263568e+02 13 truss6 172 451 -9.0100140e+02 13 truss7 86 301 -9.0000140e+02 13 truss8 496 628 -1.3311459e+02 13 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]. Note that at one of these problems was unfortunately incorrectly converted into SDPA sparse format. Thus the objective value does not match the value obtained by other authors who used the original Helmberg and Rendl graph files. The optimal objective values for the maxG55 problem obtained directly from the G55 graph is 1.1039460e+04 instead of the value of 1.2869867e+04 reported here. The value given here is correct for the SDPA file as it appears in SDPLIB. 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. References: [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. [2] S. J. Benson, Y. Ye, and X. Zhang, Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization, May 10, 1998, Working Paper, Department of Management Science, University of Iowa, IA, 52242, USA. [3] B. Borchers, CSDP, a C library for semidefinite programming, New Mexico Tech, June 8, 1998. [4] K. Fujisawa, M. Fukuda, M. Kojima, and K. Nakata. Numerical Evaluation of SDPA (Semidefinite Programming Algorithm) Technical Report B-330, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, September, 1997. [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. [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. [7] C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming. ZIB Preprint SC-9737, Konrad Zuse Zentrum fur Informationstechnik, August 1997. [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.