Linear bottleneck assignment problem
Encyclopedia
In combinatorial optimization
, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.
In plain words the problem is stated as follows:
The term "bottleneck
" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.
Usually the weight function is viewed as a square real-valued matrix
C, so that the cost function is written down as:
subject to:
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.
In plain words the problem is stated as follows:
- There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.
The term "bottleneck
Bottleneck
A bottleneck is a phenomenon where the performance or capacity of an entire system is limited by a single or limited number of components or resources. The term bottleneck is taken from the 'assets are water' metaphor. As water is poured out of a bottle, the rate of outflow is limited by the width...
" is explained by a common type of application of the problem, where the cost is the duration of the task performed by an agent. In this setting the "maximum cost" is "maximum duration", which is the bottleneck for the schedule of the overall job, to be minimized.
Formal definition
The formal definition of the bottleneck assignment problem is- Given two sets, A and T, together with a weight functionWeight functionA weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more "weight" or influence on the result than other elements in the same set. They occur frequently in statistics and analysis, and are closely related to the concept of a...
C : A × T → RReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
. Find a bijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
f : A → T such that the cost function:
-
- is minimized.
Usually the weight function is viewed as a square real-valued matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
C, so that the cost function is written down as:
Mathematical programming formulation
subject to: