\documentstyle[12pt]{article} \setlength{\topmargin}{-.5in} \addtolength{\textheight}{1.5in} \addtolength{\textwidth}{\evensidemargin} \addtolength{\textwidth}{\oddsidemargin} \setlength{\oddsidemargin}{.25in} \setlength{\evensidemargin}{.25in} \addtolength{\textwidth}{-1.0\oddsidemargin} \addtolength{\textwidth}{-1.0\evensidemargin} \begin{document} \setlength{\baselineskip}{20pt} \title{ The Second DIMACS International \\ Algorithm Implementation Challenge: \\ General Information } \author{ } \date{September 28, 1992} \maketitle \noindent {\it This document provides a general overview of the Challenge and gives information about where to find more material.} \section{Introduction} In conjunction with its Special Year on Combinatorial Optimization, the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) invites participation in an international Implementation Challenge to find effective optimization and approximation algorithms for the following NP-hard problems: {\bf Maximum Clique}, {\bf Graph Coloring}, and {\bf Satisfiability}. The Implementation Challenge will take place between September 1992 and August 1993. Participants are invited to carry out research projects related to these problem areas and to present research papers at a DIMACS workshop to be held in Fall of 1993. A refereed workshop proceedings will be published by the AMS. The purpose of this Challenge is to encourage high quality empirical research on difficult problems. The problems chosen are known to be difficult to solve in theory. How difficult are they to solve in practice? How can we best measure the practical difficulty of solution? If optimal solutions are unobtainable in practice, how close to optimal can we get in reasonable amounts of time? Do artificial problem generators generate instances with characteristics similar to those of real--world instances? What approaches are most robust for a wide variety of instances? How can special structure in instances be exploited? These are some of the many questions that might be addressed within the Challenge. The Challenge is intended to create several tangible benefits. One will be the refereed proceedings, that should provide a state--of--the--art overview of the field. Another will be a database of test instances, comparable to the traveling salesman problem testbed, TSPLIB. Other possible products include solution codes, problems generators, annotated bibliographies, and other items that are submitted by participants. Many of these will be accessible both during and after the Challenge through anonymous ftp and other electronic mail based methods. The success of this Challenge will be based on the efforts of the participants. DIMACS's role will simply be to provide general guidance and coordination, to be a clearinghouse for instances, codes and other material, and to sponsor the eventual Workshop and Proceedings. \section{Description of Problems} Separate documents are, or will shortly be, available giving an overview and annotated bibliography for each of the three problems that are the subject of the Challenge. This section offers a brief description of each problem. \paragraph{Maximum Clique} Given an undirected graph, a {\it clique} of of the graph is a set of pairwise adjacent nodes. A {\it maximum clique} of a graph is a clique such that no other clique has more vertices. There are also weighted versions of the clique problem where either the nodes or the edges have weights and the objective is to find a clique that maximizes the total weight of the nodes in the clique or the edges connecting nodes of the clique. This problem is is equivalent to the {\it Independent Set Problem} on the complement of a graph, where an independent set is a set of pairwise non--adjacent nodes. \paragraph{Graph Coloring} Given a an undirected graph, a {\it coloring} of its nodes is an assignment label to each node such that adjacent nodes have different labels. A {\it minimum coloring} is a coloring that uses the fewest distinct labels. This value is called the chromatic number of a graph. \paragraph{Satisfiability} Satisifiability comes in many forms. Most generally, a satisfiability problem consists of a number of boolean variables $x_i$ contained in some logical formula $F$. The problem is to determine if there is an assignment of values to the variables so that the formula evaluates to TRUE. Often the formula is expected to be in a particular form. The most common form is {\it conjunctive normal form (CNF)}, where the formula consists of a number of {\it clauses}, each consisting of the conjunction of a number of variables or their negation. The formula is TRUE if and only if each clause evaluates to TRUE. This form is general, in the sense that every formula can be written in such a manner, though the form may be exponentially sized compared to alternative forms. In addition to the pure satisfiability problem, there is also a optimality version of the CNF Satisfiability problem (find a truth assignment that satisfies the maximum possible number of clauses). \section{Participation} There are several ways to participate in the Challenge. In fact, almost any aspect of empirical research related to the three problems addressed would be appropriate for the Challenge. Below are a few possible directions. \paragraph{1. Implement and evaluate algorithms.} Participants may implement one or more algorithms (or perhaps alternative data structures or strategies for a single algorithm) for experimental evaluation. DIMACS and the participants of the Challenge will determine a benchmark set of inputs for each problem; this will facilitate comparisons between approaches. Participants are invited to perform more extensive tests as desired. Guidelines and support tools for experimental study are also available from DIMACS. These algorithms need not try to solve the instances to optimality. We are interested in heuristics and relaxations as well as optimal solution finding methods. We are also interested in determining the effectiveness of such general purpose heuristic techniques as simulated annealing, genetic algorithms, and tabu search applied towards these problems. \paragraph{2. Create test inputs and input generators.} Participants are also invited to submit test inputs or input generators for these problems. \begin{itemize} \item We invite generators of ``random'' inputs having some quantifiable combinatorial structure and which suggest a useful model of average-case performance. \item Also of interest are generators of inputs that are arguably ``hard'' for certain algorithms (causing loss of efficiency), and which can be used to distinguish algorithmic robustness with respect to input. \item Input instances from real applications are particularly encouraged. One natural issue is the relationship between artificially generated instances and real--world instances. Do algorithms work similarly on the two or are there differences? \end{itemize} Authors of test generators should be able to describe the kinds of instances generated and to argue why they are interesting. They should perform at least limited tests to determine whether their generators yield different answers than the standard benchmarks. With author's permission, submitted inputs and generators will be made available to Challenge participants; some may be included in the set of DIMACS benchmarks. Generated inputs are expected to follow a standard format; see Section 5 for further information. \paragraph{3. Test on an unusual architecture or environment.} Participants with access to a machine not widely available are invited to adapt algorithms (or existing programs) for testing on that architecture. Implementations tuned for a particular architecture (Cray, Connection Machine, etc.) are welcome. \paragraph{4. Exploit Special Structure} One very active research area is in characterizing special cases of all these problems that can be solved effectively. The goal of this Challenge, however, is to examine the solution of general instances. As such, mechanisms for solving structured problems should concentrate either on addressing particularly well--motivated special cases or on using the special structure to attack the more general case. The latter might include recognizing that special structure ``often'' occurs, using the special structure in a subroutine for the general problem, or other approaches. \section{Challenge Goals, Rules, and Specifications} A committee of DIMACS members will provide general direction for the Implementation Challenge. Committee members are Va\v{s}ek Chv\'atal, Rutgers University, Bill Cook, Bell Communications Research, David Johnson, AT\&T Bell Laboratories, Cathy McGeoch, Amherst College, Bob Tarjan, Princeton University, and Michael Trick, DIMACS Visiting Fellow/Carnegie Mellon University (Coordinator). DIMACS can provide neither financial support for research projects nor machine cycles for the experiments, although some limited confirmatory tests may be carried out at DIMACS. The intent of the Challenge is to use DIMACS facilities (and the Internet), to provide a catalyst for experimental research on these problems, to promote communication among researchers in these areas, and to provide a clearing-house for exchange of implementations and input generators. \paragraph{Important Dates.} The Challenge begins September 1992 and continues through August 1993. The only firm deadline in the Challenge is {\bf August 1, 1993}, by which time extended abstracts must be submitted for consideration for the workshop. Later deadlines will be set for submission of the full paper for the refereed proceedings. The goal of this Challenge, however, is to use the period from September 1, 1992 through August 1, 1993 to provide feedback and interaction for ongoing research. It is during this period that the committee will be reviewing short abstracts and suggesting alternative approaches. It is also during this period that researchers will be able to coordinate and interact with others doing similar work. We therefore suggest that prospective participants do the following: \begin{enumerate} \item Register with the Challenge as soon as possible by following the instructions in Section 5. This will put the participant on a mailing list. This list will announce available documents as well as provide a forum about ongoing research. \item Submit a two or three page abstract by {\bf January 15, 1993} which will be reviewed by the committee. \item Submit a progress report by {\bf April 1, 1993} which will also be reviewed by the committee. \item Submit an (up to ten page) extended abstract by {\bf August 1, 1993} from which the workshop presenters will be chosen by the Committee. \end{enumerate} \paragraph{Project proposals.} At each review step, the committee will examine each project to identify duplicated research efforts and to suggest modifications as may seem appropriate. Approximately one month before the workshop, the set of accepted extended abstracts in each problem domain will be circulated to those with accepted presentations. This will allow participants to prepare their workshop presentations with the related papers already in mind and will encourage further communication between participants. Shortly after the workshop, a DIMACS technical report will be prepared that consists of the (possibly revised) extended abstracts. Full papers will be due one or two months after the workshop for consideration in the refereed proceedings. Support code, program development and testing tools, input generators, and input instances may be submitted and are welcome at any time. See Section 5 for submission information. General announcements of new files and test inputs available from DIMACS will be made periodically. \section{Accessing Other Documents} There are a number of other documents that are ready, or will be ready soon. These include \begin{enumerate} \item Definition of input formats. To achieve compatibility of input generators and test implementations, a standard input format will be defined for each problem. Translation programs for converting to and from other standard representations will be distributed as they become available. \item Annotated bibliography and suggested research directions. Each of the three problems will have a separate review of the literature and suggestions for future research. \end{enumerate} Announcement of these documents will be made to the mailing list. There are a number of ways to access these and any other documents. \paragraph{Anonymous FTP.} The easiest way to access Challenge documents is through anonymous FTP to DIMACS. To use this facility type the following command sequence. Human-generated commands appear in {\tt typewriter} font; {\tt name@address } refers to your full email address. \begin{verse} \% {\tt ftp dimacs.rutgers.edu}\\ Connected to dimacs.rutgers.edu.\\ 220 dimacs.rutgers.edu FTP server (Version 6.15 Fri Apr 10 01:00:01 EDT 1992) ready.\\ Name (local.system.name): {\tt anonymous}\\ 331 Guest login ok, send e-mail address as password.\\ Password: {\tt name@address}\\ 230 Guest login ok, access restrictions apply.\\ ftp$>$ cd {\tt pub/challenge}\\ 250 CWD command successful.\\ \end{verse} Typing a {\tt ?} at the {\tt ftp>} prompt will produce a list of commands. Typing {\tt help commandname} will give a very short description of what the command does. Typing {\tt remotehelp commandname} gives a description of command format. For further information, contact either your local support group or send mail to the Challenge address {\tt challenge@dimacs.rutgers.edu} and we will send more detailed information. The main directory contains several files of general interest. The file INDEX list the available files and describes the various subdirectories. \paragraph{Electronic Mail.} Electronic mail should be used to be placed on the mailing list. In addition, some participants may not have capabilities for anonymous FTP. In this case files and related information can be obtained by electronic mail. The following addresses may be used. \begin{description} \item[challenge@dimacs.rutgers.edu] Requests to be put on the mailing list, project proposals, general questions and comments should be sent to this address. \item[challenge-submit@dimacs.rutgers.edu] Submitted programs and data files may be mailed to this address. If a submission consists of more than one file, please bundle all files into a single mail message, preferably using the commonly available ``shar'' utility. Please also send a message to {\tt challenge@dimacs.rutgers.edu} with a short description of your submission. \item[challenge-server@dimacs.rutgers.edu] This is an automatic mail server, from which files can be requested. For help using it, send a message to it with the single line ``help''. \end{description} \end{document}