Munkres Class

Hungarian method for solving the assignment problem, also known as the Kuhn–Munkres algorithm or Munkres assignment algorithm.

Inheritance Hierarchy

SystemObject
Accord.Math.OptimizationMunkres

Namespace: Accord.Math.Optimization
Assembly: Accord.Math (in Accord.Math.dll) Version: 3.8.0

Syntax

Copy

public class Munkres : IOptimizationMethod, IOptimizationMethod<double[], double>

Public Class Munkres
	Implements IOptimizationMethod, IOptimizationMethod(Of Double(), Double)

Request Example View Source

The Munkres type exposes the following members.

Constructors

	Name	Description
	Munkres(Double)	Initializes a new instance of the Munkres class.
	Munkres(Int32, Int32)	Initializes a new instance of the Munkres class.

Top

Properties

	Name	Description
	CostMatrix	Gets or sets the cost matrix for this assignment algorithm. This is a (W x T) matrix where N corresponds to the NumberOfWorkers and T to the NumberOfTasks.
	MinCol	Gets the minimum values across the cost matrix's columns.
	MinRow	Gets the minimum values across the cost matrix's rows.
	NumberOfTasks	Gets the number of variables (free parameters) in the optimization problem. In the assigment problem, this gives the number of jobs (or tasks) to be performed.
	NumberOfVariables	Gets or sets the number of variables in this optimization problem (NumberOfTasks * NumberOfWorkers).
	NumberOfWorkers	Gets or sets the number of workers in the assignment algorithm. The workers are the entites that can be assigned jobs according to the costs in the CostMatrix.
	Solution	Gets the current solution found, the values of the parameters which optimizes the function.
	Tolerance	Gets or sets the tolerance value used when performing cost comparisons. Default is 1e-10. If the algorithm takes too much time to finish, try decreasing this value.
	ValidCol	Gets a boolean mask indicating which columns contain at least one valid element.
	ValidRow	Gets a boolean mask indicating which rows contain at least one valid element.
	Value	Gets the output of the function at the current Solution.

Top

Methods

	Name	Description
	Equals	Determines whether the specified object is equal to the current object. (Inherited from Object.)
	Finalize	Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection. (Inherited from Object.)
	GetHashCode	Serves as the default hash function. (Inherited from Object.)
	GetType	Gets the Type of the current instance. (Inherited from Object.)
	Maximize	Finds the maximum value of a function. The solution vector will be made available at the Solution property.
	MemberwiseClone	Creates a shallow copy of the current Object. (Inherited from Object.)
	Minimize	Finds the minimum value of a function. The solution vector will be made available at the Solution property.
	ToString	Returns a string that represents the current object. (Inherited from Object.)

Top

Extension Methods

	Name	Description
	HasMethod	Checks whether an object implements a method with the given name. (Defined by ExtensionMethods.)
	IsEqual	Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices. (Defined by Matrix.)
	To(Type)	Overloaded. Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime. (Defined by ExtensionMethods.)
	ToT	Overloaded. Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime. (Defined by ExtensionMethods.)

Top

Remarks

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.

James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm.The time complexity of the original algorithm was O(n^4), however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an O(n^3) running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

This code has been based on the original MIT-licensed code by R.A. Pilgrim, available in http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html, and on the BSD-licensed code by Yi Cao, available in http://fr.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-

References:

Examples

Copy

// This is the same example that is found in Wikipedia:
// https://en.wikipedia.org/wiki/Hungarian_algorithm

double[][] costMatrix =
{
    //                      Clean bathroom, Sweep floors,  Wash windows
    /* Armond   */ new double[] {    2,           3,           3       },
    /* Francine */ new double[] {    3,           2,           3       },
    /* Herbert  */ new double[] {    3,           3,           2       },
};

// Create a new Hungarian algorithm
Munkres m = new Munkres(costMatrix);

bool success = m.Minimize();    // solve it (should return true)
double[] solution = m.Solution; // Solution will be 0, 1, 2
double minimumCost = m.Value;   // should be 6

Reference

Accord.Math.Optimization Namespace

Accord.Math.OptimizationIOptimizationMethod