Organizing committee Schedule of the Challenge
The purpose of the Challenge Topics
The problem library List of participants as of 6/1/00
Organizing committee   David Johnson, AT&TLabs

  Gabor Pataki , University of North Carolina at Chapel Hill

The purpose of the Challenge In conjunction with its special year on large scale discrete optimization problems, the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) invites participation in an implementation challenge on Semidefinite and related optimization problems.

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. 

Topics We have received and still invite proposals dealing with all computational aspects of semidefinite programming and related problems. For example:

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.

We expect a very exciting part of the Challenge to be the testing of mature, and new algorithms on our
Problem library The variety of problems one can tackle using SDP, and conic quadratic programming is truly striking. A short list of problems already available, or to come soon:

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!

Schedule: All communications regarding the challenge should be directed to in particular preliminary proposal submission, extended abstracts, and possible submission of software and problem instances should be sent to the above address. 

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

Back to DIMACS Page