There are 50 Challenge benchmark problems in 12 groups. For details, see the appendix and the preliminary report available at [8].
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.