Lesson plan
Multidimensional assignment problem
The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla. This problem can be seen as a generalization of the linear assignment problem. In words, the problem can be described as follows: : An instance of the problem has a number of agents (i.e., cardinality parameter) and a number of job characteristics (i.e., dimensionality parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some cost. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the total cost of assigning the agents so that the assignment of agents to each job characteristic is an injective function, or one-to-one function from agents to a given job characteristic. Alternatively, describing the problem using graph theory: :The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.
Article summary
The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by William Pierskalla. This problem can be seen as a generalization of the linear assignment problem. In words, the problem can be described as follows: : An instance of the problem has a number of agents (i.e., cardinality parameter) and a number of job characteristics (i.e., dimensionality parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some cost. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the total cost of assigning the agents so that the assignment of agents to each job characteristic is an injective function, or one-to-one function from agents to a given job characteristic. Alternatively, describing the problem using graph theory: :The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.