Second DIMACS Challenge Update: August 22, 1993 There are a few new files, and a few announcements this time around: 1) The papers submitted for presentation at the conference are now being examined by the committee. There were more than 40 papers submitted, of which roughly 20 are on satisfiability, 15 on cliques, a handful on all three problems, and 5 on graph coloring. Paper selection will be complete very early in September. 2) The Challenge conference will be held October 11-13 at DIMACS, Rutgers University. The official announcement will be made right after paper selection. Information on hotel reservations and so on will be contained in the announcement. There will be some funds available to support graduate students in attending this conference. More information on the conference will be available in early September. 3) We could use more solution files to match up with the problem files. The formats are in the format files. Note that there has been a change in the graph output format to avoid conflicts with comment lines. 4) I have received a set of satisfiability instances collected by researchers at the Forschungsinstitut fuer anwendungsorientierte Wissensverarbeitung in Ulm Germany. Some of those instances are being placed in the benchmarks directory as I get them translated into DIMACS format. These are denoted (FAW) in the contents.tex file. Mike Trick Challenge Coordinator/ Carnegie Mellon University Change in clique output format: "c" conflicted with comments, so has been changed to "v". New directory: Each benchmark directory will have a SOLUTIONS file (only clique solutions submitted so far) containing solutions to instances. New contributed work: graph/contributed/soriano: From Patrick Soriano (patrick@crt.umontreal.edu): A generator in PASCAL for clique instances as described in "Solving the maximum clique problem using a tabu search approach" Annals of OR 41 385-403. Some instances are included in the benchmarks. sat/contributed/iwama: From Kazuo Iwama (iwama@csce.kyushu-u.ac.jp): Two generators (one for satisfiable and one for unsatisfiable instances) with control on attributes of instances. Some instances will be included in benchmarks when I figure out what would be some interesting instances. iwama_prog.sh is a shell file, extracted by the command: sh iwama_prog.sh sat/contributed/pretolani: From Daniele Pretolani (daniele@crt.umontreal.edu): Two generators (source code) and two exact solution codes (Sun Sparc executable only) for satisfiability. One generator is for k-SAT formulae where the number of literals in each clause is uniformly distributed, while the other is based on graph 2-coloring with a parity contraint (the latter determines whether the instance is satisfiable or not). Instances of the second class are in the benchmarks. sat/contributed/zhang: From Hantao Zhang (hzhang@cs.uiowa.edu). Contains source for "sato", a decision procedure for propositional logic.