The Bottleneck Assignment Problem

The bottleneck assignment problem is an interesting problem in combinatorial optimization. It has many variants and is as well a variant of the assignment problem. In general, the problem is defined based on a set of agents that must be assigned to a set of tasks while ensuring that each task is done by one agent. Each assignment has a cost and we seek the minimization of the maximum cost within the individual assignments. In other words, we want an assignment that will minimize the maximum individual cost. The same problem definition goes for the profit maximization case. In the following parts, I want to highlight, for a real case, its modelization ways as well as its resolution. The goal is introducing the problem as well as some modeling insights useful in terms of resolution efficiency.

The usage of the word “bottleneck”, meaning the neck or mouth of a bottle, comes from a popular application of this problem in timed tasks performed by a specific person. In this context, we seek the minimization of the maximum duration, i.e. we make the neck of the schedule of the whole job to minimize tight.

Real Case Example

This problem has many applications in the real life. Still, I would like to explain it through an example I learnt in one of my courses which is the Curling Game. Let’s suppose we want to organize a friendly curling tournament where we want to form mixed teams consisting of 1 man and 1 woman per team from a set of N men and N women. Each player has a ranking. We want to make teams while minimizing the mean ranking of the strongest team. The mean is calculated as the average of rankings for each team.

Method 1 — A Min Max with the Bisection Method

Let’s start by first looking to the sets, parameters and variables necessary to model the problem. The number of men is equal to the number of women. The parameters are the mean of each possible team computed from the individual rankings of men and women. The variable is binary, i.e. it takes one if a team is selected and zero otherwise. These definitions are kept for this method as well as the remaining ones.

Since the objective is minimizing the mean of the strongest team, the objective can take the form of a min-max (i.e. minimizing the maximum). Two constraints must be added. First, each man should be assigned to exactly one woman. Second, each woman should be assigned exactly to one man. Then, positivity constraints are added.

Obviously, this model is non-linear. To solve it, we can use the bissection method. This method consists of solving several assignment problems until we reach the minimal threshold. Given the values of team rankings, we can limit the minimum average of the strongest between an upper and a lower value [A, B]. We start by selection M1 in the middle of this interval and we verify whether the assignment problem is feasible. If it is feasible, our new interval becomes [A,M1], and we select the middle of this new interval. Otherwise, our new interval becomes [M1,B], and we select the middle of this new interval. Either case, we solve again the assignment problem with the new value of M, i.e. M2. We keep repeating this cycle until reaching the smallest M feasible. In order to ensure a rapid convergence, it is good to have the smallest interval [A,B] possible. The number of assignment problems to solve is finite.

Method 2 — A First Linear Model

We can make the first model linear by changing slightly the objective function and adding N² constraints to the problem as shown below. Since we minimize Z, the resolution will seek minimizing the mean ranking of the strongest team. For this model, we add the binary constraint on the variables.

Method 3 — A Better Linear Model

We can make the previous linear model better by changing the N² constraints added into only N constraints as shown below. It is better due to the reduced number of constraints. Furthermore, the resolution of the relaxation problem of this new model, i.e. without forcing the variables to be binary, will provide a better lower bound compared to the relaxation of the previous one.

Method 4 — The Han De Watcher Method

Another possible way to tackle this problem is the Han De Watcher method that consists of sorting men in increasing rankings and sorting women in decreasing rankings. Then, we form teams as shown in the figure below. We can prove, by absurd, that this method is also optimal.

Applications

In real life, either in business or in personal work, we may need to form teams, assign agents to tasks, personal to departments, operators to machines, demands to compartments, origins to sources, and all others types of assignments. This can be done using the bottleneck assignment problem or any other variant within the broader area of assignment problems. Companies may gain significantly from modeling their problems as optimization problems in terms of costs reduction or profits increase. Furthermore, these problems are not very difficult to solve generally and have the integrity property, it means that, generally, the required effort to obtain a good solution, if not optimal, is by far less compared to the expected gain.

In this quick article, I wanted to highlight, through understandable and concrete examples, the importance of optimization in our daily life and how we can take benefit from it by applying it to solve the different problems we face through the bottleneck assignment problem. I also wanted to share about some of the various modeling and resolution tricks that are available for assignment problems, which are solved rapidly using available optimizers in the market such as CPLEX, FICO Xpress, etc.

What are your insights on the topic? I am looking forward to hearing them :).