SDPLIB 1.2 

http://euler.nmt.edu/~brian/sdplib/ 

SDPLIB is a collection of semidefinite programming test problems. All problems are stored in the SDPA sparse format.
This is the new web site for version 1.2 of SDPLIB. Although there have been no changes to the actual problems in the library, I have taken the opportunity to provide some additional information about the problems here.
A paper describing SDPLIB has been published. 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.
Hans Mittelman has benchmarked a number of SDP codes on the SDPLIB problems.

Downloads

• Download a PDF preprint of the paper describing the library: SDPLIB 1.2, A Library of Semidefinite Programming Test Problems, June 28, 1999. Or, the original postscript version of the preprint.
• Download the entire library: (.tar.gz, .zip)
• Download individual problems.
• Download output files showing the solution of the SDPLIB problems by CSDP 6.0.1.
• Download a detailed description of the problems.
• Download a description of the file format.
• Download an outdated description of the problems, showing what was known about the solutions in 1998.

Contact the author.
Return to Brian Borchers Homepage

Fast approximations to solve packing/covering LPs and constant-sum games via multiplicative-weights technique

Fast approximations to solve packing/covering LPs and constant-sum games via multiplicative-weights technique

Ajay Shankar Bidyarthy∗ Rajiv Raman† Dilys Thomas†

June 1, 2012

The multiplicative weights algorithm is a well-known technique for approximately solving packing/covering linear programs. The technique originated in the 1940s in the context of solving constant-sum games. There has been considerable recent research building on this work, develop-ing fast and approximate solutions to packing/covering linear as well as semi-definite programs.
We have implemented several variants of this technique and evaluated these algorithms experimentally. In particular, we evaluated the non-uniform increment technique of Garg and K ̈nemann o [1], as well as recent extensions by Koufogiannakis and Young [2]. The performance of our implementation compare well with the best linear programming solvers. For example, the figure on the
left shows our algorithms run much faster for moderately small approximation factors and largeinstances (5000 × 5000 dense real matrices), compared to Sedumi [3] (a well-known LP and SDP solver), while the figure on the right shows that Sedumi can converge faster ( < 0.02) than the classic Grigoriadis-Khachiyan fictitious play.

These algorithms are a building-block for solving large-scale combinatorial optimization problems approximately. Our algorithms have been implemented in MATLAB and have been tested on multiple modern 2-core machines.

References
[1] Naveen Garg and Jochen K ̈nemann. Faster and simpler algorithms for multicommodity flow o and other fractional packing problems. SIAM J. Comput., 37(2):630–652, 2007.
[2] Christos Koufogiannakis and Neal E. Young. Beating simplex for fractional packing and covering linear programs. CoRR, abs/0801.1987, 2008. (earlier published in FOCS 2007).
[3] Jos. F. Strum. SeDuMi ver. 1.3, http://sedumi.ie.lehigh.edu/.

∗ Indian Institute of Technology, Guwahati, India. E-mail: b.ajay@iitg.ac.in
† TCS Innovation labs, TRDDC, Pune, India. E-mail: rajiv.raman@tcs.com,dilys@cs.stanford.com