Gabor Pataki , University of North Carolina at Chapel Hill [email protected]

The purpose of DIMACS computational challenges has been to encourage the experimental evaluation of algorithms, in particular those with efficient performance from a theoretical point of view. The past Challenges brought together researchers to test time proven, mature, and novel, experimental approaches on a variety of problems in a given subject. As the subject of the last Challenge of this century, one could hardly think of a better choice than Semidefinite Programming (SDP) - one of the most interesting and challenging areas in optimization theory to emerge in the last decade. In the past few years much has been learned on both the kinds of problem classes that SDP can tackle, and the best SDP algorithms for the various classes. In addition a great deal has been learned about the limits of the current approaches to solving SDP's. 

In addition to semidefinite programming a closely related problem is that of conic quadratic programming, or second order cone programming (SOCP). This problem resides in between linear and semidefinite programming. It also arises in a variety of applications from statistics to engineering; and a number of combinatorial optimization problems, in particular in the Steiner tree problems and plant location problems have found SOCP as a subproblem. Similar to semidefinite programming a great deal is known about optimization with convex quadratic constraints as well as limitation of current methods. Finally this knowledge has been extended to problems containing variables and constraints with some or all of linear, convex quadratic or semidefinite constraints. 

This Challenge attempts to distill and expand upon this accumulated knowledge. 

Computational testing of general purpose methods for SDP and/or for conic quadratic programming.

Computational testing of solution algorithms for special classes of SDP/conic quadratic programming.

Special aspects of SDP/SOCP: novel combinatorial applications; computing relaxations/heuristic solutions for specific problem classes using publicly available codes.

SDP's based on cut problems from theoretical physics; frequency assignment; and VLSI circuit design. Since there are few methods that can handle such large, and sparse SDP's, these instances truly are a challenge !

Conic quadratic programs arising from mechanical engineering (plastic collapse analysis); machine scheduling; portfolio optimization; antenna array design; and quadratic assignment problems.

SDP's from filter design; copositivity checking of matrices; and relaxations of multiclass queuing models.

SDP's and conic quadratic problems that are small, and innocent looking (primal-dual strictly feasible). However, due to their "malicious" facial structure, no code we tried can solve them to any reasonable degree of accuracy!

September 15, 2000 : Progress reports due for comment and feedback;   we are expecting a report of at least 5 pages long.

October 15, 2000: Extended abstracts due date for consideration for the workshop 

November 2-3, 2000: The workshop will take place 

Final drafts due date for appearance in the workshop proceedings will be determined later