The DIMACS Implementation Challenges help understand and improve the practical performance of algorithms for important problems, particularly those that are hard in the theoretical sense. The Challenges aid in determining realistic algorithm performance where worst-case analysis is overly pessimistic and probabilistic models are too unrealistic. Experimentation can provide insight into realistic algorithm performance when purely analytical methods fail, and it can provide new perspective that motivates deeper analytical results. Experimentation tests assumptions about implementation methods and data structures and provides an opportunity to develop and test problem instances instance generators to facilitate future comparisons.
The Implementation Challenges were inspired by David S. Johnson and date back to the early years of DIMACS. Each challenge addresses a particular problem or group of related problems and focuses the attention of many people on that problem. The challenges involve setting up a common infrastructure and library of test problems to allow researchers to evaluate their own implementations and compare them with those of others. The idea is to establish a common “playing field” in order to compare results and establish a common vision of the “state of the art.”
The overarching goal of a challenge is to encourage interaction among the participants. Through these challenges, researchers exchange ideas, share test problems, combine methods, and focus on the most promising aspects of different methods. Though staged as a "competition," there are no real prizes. Implementation Challenges are about collaboration.
Implementation Challenges:
12th Challenge (2020-22): Vehicle Routing Problems
11th Challenge (2014): Steiner Tree Problems
10th Challenge (2012): Graph Partitioning and Graph Clustering
9th Challenge (2005-6): Shortest Path Problem
8th Challenge (2001): Traveling Salesman Problem
7th Challenge (2000): Semidefinite and Related Optimization Problems
6th Challenge (1998): Near Neighbor Searches
5th Challenge (1995-6): Priority Queues, Dictionaries, and Multi-Dimensional Point Sets
4th Challenge (1994-5): Two Problems in Computational Biology: Fragment Assembly and Genome Rearrangements
3rd Challenge (1993-4): Effective Parallel Algorithms for Combinatorial Problems
2nd Challenge (1992-3): NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability
1st Challenge (1990-1): Network Flows and Matching
The Implementation Challenge webpage on the archived website contains additional information on some of the earlier challenges.
Other Computational Challenges: Occasionally, DIMACS sponsors other types of computational challenges that are not part of the Implementation Challenge series:
MIP 2022 Computational Challenge: In its first computational challenge MIP2022 tasked participants with creating general-purpose (preferrably LP-free) primal heuristics for mixed-integer linear optimization problems. [View details]
Machine Learning Challenge for Combinatorial Problems in Robotics (2021): Object Rearrangement Learning Competition.