Below we present two random graph generators for the bipartite weighted and maximum cardinality matching problems. These generators were developed for benchmarking approximate (weighted) matching algorithms at scale. Their primary design criteria was to allow for a tunable and known solution, to avoid having to exactly solve for the optimal match at a very large scale when evaluating solution quality against each benchmark instance. It is not know exactly how 'interesting' these generated graphs are for traditional solvers, but they are at least possibly useful for testing solver scalability.

Modifiable generation parameters depends on the specific generator variant, but typically include methods to vary the number of vertices, sizes of bipartite sets, degree distributions, and cardinalities or weights of the optimal matching solution. Please see the README in each directory linked below for compilation and running instructions.

The methods have been modified to output in the DIMACS format for the Assignment Problem and Bipartite Matching problems as part of the 13th DIMACS Implementation Challenge. They should easily scale to the limits of 32-bit integers. We include a few large-scale test instances that represent the possible parameter spaces. The methods should also be usable in-memory with little modification to existing application code (as long as the application can handle a basic edgelist).