The DIMACS library of mixed semidefinite-quadratic-linear programs

Abstract:

To provide access to test problems for the participants of the 7th DIMACS Implementation Challenge, we assembled a library of test problems.
Our main concerns in the selection were to create a library of instances that
o arise from the widest possible range of sources, and applications.
o are as realistic as possible.
o represent all levels of difficulty.
o have their origin and the formulation used clearly documented.
             Currently, we have 12 problem sets. More are welcome; please see the "Submissions" section below.

Developers:

o Gabor Pataki University of North Carolina, Chapel Hill
o Stefan H. Schmieta Columbia University

Problem descriptions:

oA table with problem sizes and known solutions.
oA table listing problem originators, formulators, and donators.

Technical report:

o A preliminary version with more details.

Problem formats:

o The .mat files contain the problems in the format used by Sedumi .
that solves a problem of the form min { c'x | st. Ax=b, x in K }, where K is an appropriate cone, representing
semidefinite, quadratic, and linear constraints on x; for details, see the report.
This format is probably the easiest to convert to all other formats, if you have Matlab.
For some large graph problems, only a .dat file containing the graph description is available,
with a commented Matlab code that can generate the .mat file from it.
o Two converter codes are provided below, both written by Brian Borchers.

Reporting the solution quality:

o A document describing the required format for reporting the error of the obtained solutions is here

Links:

o Hans Mittellman's independent benchmarking results.
o The SDPLIB library by Brian Borchers.

Problem sets:

o The complete problem library as a tar file and compressed with gzip.
o The torus set:  Max cut problems from the Ising model of spin glasses.
     Caveat: these max { cx | st. Ax =b, x in K } type problems
     are given as min { -cx | st. Ax =b, x in K }. To get the optimal values in the table,
     you must multiply the optimal value of the latter problem by (-1).
     In addition, the optimal values of the torusg (that is, Gaussian instances) must be divided by 100,000.
o The fap set : Min k-uncut problems from frequency assignment.
o The bisection set : Min bisection problems from circuit partitioning.

o The nql set : Quadratic problems to compute plastic collapse states: plain strain models.

The problems tagged "old" contain the formulations originally present in the library. They, although equivalent, are inferior formulations and are not true to the formulations as they were submitted.

o The qssp set: Quadratic problems to compute plastic collapse states: supported plate models.

The problems tagged "old" contain the formulations originally present in the library. They, although equivalent, are inferior formulations and are not true to the formulations as they were submitted.

o The filter set: Mixed SDP/SOCP problems from PAM (pulse amplitude modulation) filter design.
o The hinf set: LMI (Linear Matrix Inequality) problems.
o The truss set: Truss topology design problems
o The antenna set: Antenna array design problems
o The copos set: Checking a sufficient condition for copositivity of a matrix
o The hamming set: Instances computing the theta function of Hamming graphs for which the exact value is known.
o The sched set: Quadratic relaxations of scheduling problems.

The files tagged "_orig" contain the models as they were submitted. The corresponding "_scaled" files are reformulations that (among other things) scale the problem. The scale factor for the objective function is contained in the mat-file as c_mult.

Submissions:

To add a problem set to the collection send a description of the set to Gabor Pataki or Stefan H. Schmieta.

Back to the Challenge page

Back to the DIMACS home page

This page maintained by: Stefan H. Schmieta schmieta@corc.ieor.columbia.edu