There are 50 Challenge benchmark problems in 12 groups. For details, see the appendix and the preliminary report available at [8].

- The
**torus**set: Max cut problems from the Ising model of spin glasses. - The
**bisection**set: Min bisection problems from circuit partitioning. - The
**fap**set: Min k-uncut problems from frequency assignment. - The
**nql**set: Quadratic problems to compute plastic collapse states: plane strain models. - The
**qssp**set: Quadratic problems to compute plastic collapse states: supported plate models. - The
**filter**set: Mixed SDP/SOCP problems from PAM (pulse amplitude modulation) filter design. - The
**hinf**set: LMI (Linear Matrix Inequality) problems. - The
**truss**set: Truss topology design problems. - The
**antenna**set: Antenna array design problems. - The
**copos**set: Checking a sufficient condition for copositivity of a matrix. - The
**hamming**set: Instances computing the theta function of Hamming graphs for which the exact value is known. - The
**sched**set: Quadratic relaxations of scheduling problems.

- An entry [7; 3x5, 3, 4, 2x6 ] in the "SDP" column means that the problem has 7 SDP blocks whose sizes are 5,5,5,3,4,6,6 in this order. The meaning of the entries in the "QUADR" column is analogous.
- If an entry in the "opt. value" column has is not accompanied by a mark, or remark, then it has been computed by a primal-dual interior point code. Currently these codes provide the most accurate solutions. Still, these values are approximate, and which solver furnishes the most accurate solution can be told only after looking at the tables with the error measures, namely Tables 5, 10 and 11.
- If an entry is accompanied by the mark '*', then it has been computed by a code designed to obtain approximate solutions to large scale problems (such as BMPR, BMZ, BUNDLE, and DSDP).
- If in addition to the '*' mark, there is a 'lb, not opt' remark, this means that a lower bound on the objective value was computed by BMZ, or BUNDLE. These codes work with fully feasible dual solutions, whose value serves as a reliable lower bound, even when the termination criteria of the codes are not satisfied.
- Having a '(?)' mark means that the listed value is the currently known most accurate one; nevertheless, its accuracy is still not satisfactory, and the true value may be quite different.

**SOCP problems**

The results are contained in Tables 3, 4 and 5.
For all codes the primal objective values are listed.
The fastest code in this category is MOSEK, with SeDuMi a close second.
MOSEK uses its own
input format: extended QPS, which is an extension of the QPS format for
quadratic programs which in turn is an extension of the well-known
MPS format. All other SOCP problems
were given in SeDuMi format, and converted to QPS for input to MOSEK
with the help of a converter provided by its author. SeDuMi is a close
second on the SOCP problems. Only its memory usage kept it from solving
all instances.

LOQO which grew out of a LP/QP code to a general NLP solver, has
an AMPL interface and accepts QPS input but only for QP's. More recently,
it was equipped with a Matlab-based interface to read SOCP problems
and even with an interface to input and solve SDP problems in sparse
SDPA format. The SOCP results for LOQO in the tables were obtained
with the Matlab interface. If a run was not successful because not
all of LOQO's convergence criteria were satisfied, this problem was
also solved utilizing the AMPL interface and the QPS to AMPL converted
files provided by us per anonymous `ftp`.
These results are in parentheses. The
LOQO option `convex' was used and the maximum iteration number increased.
It should be noted that LOQO is in continuous development and while here
version 5.04 was used in the mean time a filter-based version 6.0 is
available.

**SDP problems**

The results are contained in Tables 6, 7, 9,
10, and 11.
For all codes, except for BMZ, BUNDLE and DSDP the primal objective values are listed.
On the SDP side eight codes are
competing and the collection of the test problems is naturally more diverse.
Three of the codes - BMPR, BMZ, and BUNDLE - do not make use of second order information, and
are therefore successful mostly on large-scale combinatorial SDPs.

The important difference between BMPR and the two other codes, BMZ and BUNDLE are as follows.
BMPR is a *primal* method, that works with *primal infeasible* solutions, attaining
feasibility in the limit only: its objective value is therefore mathematically less
reliable, but it produces primal approximations very efficiently. BMZ and BUNDLE are both
*dual* methods, that work with *dual feasible* solutions, hence any objective value
they furnish is a mathematically reliable lower bound on the objective value, even before
their termination criteria have been met. The difference in the approaches - primal vs. dual -
explains the differences in the reported objective values in Table 6.
We remark that some kind of error computation is possible for these codes as well,
but this was not incorporated into our testing, and we refer to the authors' contributions in this volume.

One can draw cautiously the following conclusions concerning the first three codes. BUNDLE outperforms BMZ in the maxcut and bisection classes, generates excellent starting guesses in the class of theta problems and seems consequently very efficient there. However, in the FAP class BMZ is clearly superior to BUNDLE. This becomes evident from the smallest instance while a further comparison was hampered by the large jump in size to the two larger instances in this class. Taking into account that BUNDLE is applicable to a wider class of SDP problems but that BMZ due to its general approach may still be generalized [7], both methods have their advantages and disadvantages, no "winner" can be declared.

A remark is in order on the results for the FAP problems in Table 7 and the codes BMZ and BUNDLE. Both codes finished with the given times and function values on the two smaller problems. On FAP36 BMZ reached the maximum function value of 63.780 after seconds, then the value dropped slightly to 63.775 and after the given endtime the code crashed, putting out NaN's. BUNDLE, on the other hand, reached the given function value after the given time when the machine crashed and the code was not restarted.

The code BMPR, written by a subset of the BMZ authors, competes very well in the maxcut, bisection, and theta classes. While it does not have a convergence theory, it appears to be the most efficient code for the problems that are part of the Challenge in these classes. BUNDLE's performance in the theta class is largely due to the choice of starting values. It can without doubt be stated that these three first order methods have proven their value for larger instances in certain classes and that further generalizations and improvements may be expected.

It remains to assess the performance of the remaining codes, especially on the SDP problems. Among these, DSDP is the only code employing a dual approach. Of the others, SDPA, SDPT3, and CSDP were run with HKM or XZ directions although the first two allow alternative choices, while SeDuMi utilizes the NT direction or scaling. SDPA is the most traditional code. It has not been updated since 1999 but it performs in a robust way, satisfying all the basic expectations a user would have in the primal-dual approach it is based on. SeDuMi from the start was designed to solve SQL (semidefinite, quadratic, linear) problems while SDPT3 only recently was extended to this class. SeDuMi was slightly upgraded from the currently still distributed version 1.03 to the version 1.04 used for our tests. It employs a number of measures assuring a high numerical robustness while maintaining good efficiency except when the SDP problem involves large matrix variables without block-diagonal structure. Before SDPT3's extension, SeDuMi may have been considered the best broadly, to both SDP and SOCP classes, applicable program.

DSDP is the only dual code which has both advantages and disadvantages. It can exploit certain problem features to reduce storage and increase efficiency. This does not show very much with the limited selection of Challenge problems; in fact, on the larger SDPs DSDP has a comparable performance to CSDP, which is a primal-dual code, but is especially good at handling one large matrix variable. More information about DSDP's performance can be found in [2].

CSDP in its previous version did not have the robustness of the other methods but was stabilized in version 3.2. In several of the cases listed as failed it came close to satisfying the termination criteria. Its memory requirements limit it somewhat but the fact that it is entirely in C or f77 makes it still very economical in that respect and also allows to compile it in 64-bit mode on appropriate platforms. CSDP solved, for example, the maxcut problems in about the time of DSDP and only 2-4 times slower than the more specialized BMZ.

The code SDPT3 underwent the largest changes except possibly for DSDP during the course of the Challenge. While version 2.1 was comparable to SDPA, it was modified in a minor way for the currently available version 2.2 and in a major way for the version 3.0 the authors asked us to consider. SDPT3-3.0 is a contender in both SDP and SOCP classes and in both smaller and somewhat larger problem sizes. Still, its basic primal-dual strategy and direct linear algebra and the use of Matlab set some limits on problem size.

There were initial difficulties with running SDPT3 under Matlab 6 on a Solaris platform. These lead us to provide additional benchmarking information, see the next paragraph. However, in the mean time these problems seem to have been fixed. As far as one can tell from the limited Challenge numbers, SDPT3-3.0 is comparable though not necessarily faster than SeDuMi on small SDP/SOCP problems. But, it is able to solve much larger cases limited mainly through the memory allocation of Matlab and to do this quite efficiently. This can partly be seen from the results below but was also confirmed through other computations we did.

For an additional comparison on large SDPs, we provide the
following additional benchmark result. The case `neosfbr24`, an
SDP relaxation of the QAP Nug24, generated by the authors of [22]
was solved by us on a single processor of a Sun HPC server E6500 (24
processors, Ultra Sparc II, 400 MHz, 24 GB shared memory) in 6
days and 5 hours using CSDP and in 19 hours and 10 minutes using SDPT3.
With default settings, then SDPT3 had reduced the relative duality gap to
1E-9 while CSDP's was 9E-8.
For the case `neosfbr25` SDPT3 had memory allocation problems while CSDP
solved it in 10 days and 2 hours. Even the very large case `neosfbr30`
was solved by the 64-bit version of CSDP; this, however, took
nearly eight weeks. The datafiles just mentioned were made available by us
through anonymous `ftp`. The NEOS solvers for CSDP and SDPT3 are currently
installed on the E6500, while we have installed SDPA, SeDuMi, and MOSEK
(extended MPS input for LP/QP/SOCP problems) on
another computer. To complete the list of the codes considered here,
DSDP and LOQO are also installed at NEOS([21]).

In summary it can be said that the Challenge and this benchmarking effort have provided a good overview of the state of the art in the solution of SDP and SOCP problems. All participating codes proved to be valuable in their own right. Many are successful or even excel in solving a subclass of the problems considered here, others in the solution of classes that extend beyond those. The `general' SDP respectively SQL codes SDPA and SeDuMi are both reliable and fairly efficient for small to medium problem sizes but both have not been updated, while the codes CSDP and SDPT3 have undergone changes which allow them to solve relatively large SDP respectively SQL cases. We have reason to believe that these as well as several of the other codes will soon be further enhanced and generalized.

**Acknowledgement** The work of Gabor Pataki and the referees is gratefully
acknowledged. They greatly helped us to present the results in this form.