1.2.0

Release notes

This release is focused on improving performance for sparse inputs, i.e. input graphs for which only some edges are available for matching.

To this end, we make it possible to provide sparse inputs in to Solver, as well as the specialized ShortestPathSolver and PseudoflowSolver. Inputs may be given in compressed sparse row (CSR) format but can also be converted from a dense representation. The former approach will have higher performance if a sparse representation is already available.

New features

• Introduce sparse matrix functionality in SparseMatrixInt and SparseMatrixDouble.
• Make it possible to control whether or not cost inputs can be manipulated by the solvers to the cost of creating copies. (#1)

API changes

• Cost inputs are now kept intact by default, where they could previously be overwritten. (#1)

1.1.0

Release notes

This release introduces a new solver, based on the cost-scaling assignment (CSA) approach of

A.V. Goldberg and R. Kennedy.
An efficient cost scaling algorithm for the assignment problem.
Math. Program., 71:153–177, 1995

for inputs with integral weights. The new solver is available as PseudoflowSolver.Solve, while the previously existing functionality survives as ShortestPathSolver. A generic facade called Solver can be used to access both solver types. Which one to prefer will depend on characteristics of the input, and it's often worth it to try both, when possible.

New features

• Introduce pseudoflow-based CSA algorithm as PseudoflowSolver.

API changes

• Solver now refers to a generic facade to all solvers, with the existing functionality in Solver being available through ShortestPathSolver.

1.0.5

Release notes

This release makes it possible to maximize the sum of the weights of the assignment, where we would otherwise only ever minimize the sum. To maximize, specify maximize: true in Solver.Solve.

New features

• Introduce maximization of cost.

1.0.4

Release notes

This release extends the class of allowed inputs.

New features

• Allow inputs with more columns than rows.
• Allow negative entries in input cost.

1.0.3

Release notes

This release revamps the naming of the main solver interface to more accurately match history.

API changes

• JonkerVolgenant is now simply Solver.

1.0.2

Initial release.