Organizing committee
David Johnson,
AT&TLabs dsj@research.att.com
Gabor Pataki ,
University of North Carolina at Chapel Hill gabor@unc.edu
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
challenge@dimacs.rutgers.edu
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
|