Implementation Challenges

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.