Exploiting Structure in the Bottleneck Assignment Problem

By definition, $w(e_{3})=\max_{\{i,j\}\in\mathcal{M}_{3}}w(\{i,j\})\leq\max_{\{i,j\}\in\mathcal{M}}w(\{i,j\})$ for any arbitrary $\mathcal{M}\in\mathcal{C}_{3}$. Since $\tilde{\mathcal{M}}=\mathcal{M}_{1}\cup\mathcal{M}_{2}\in\mathcal{C}_{3}$, $w(e_{3})\leq\max_{\{i,j\}\in\tilde{\mathcal{M}}}w(\{i,j\})=\max\{w(e_{1}),w(e_{2})\}$.∎

Given Assumptions 9 and 10, the set $\mathcal{M}_{1}\cup\mathcal{M}_{2}$ is an MCM of $\mathcal{G}_{3}$. This MCM is possibly suboptimal to $BOT(\mathcal{G}_{3})$. However, this bound of the BAP allows us to make a decision before solving Problem 11 exactly. If the suboptimal solution is sufficient in our application, there is no need to invest further resources to solve Problem 11 exactly.

We now introduce the novel concept of a bottleneck cluster. In Khoo et al. (2019), conditions for determining if an edge is a bottleneck edge of a given graph are presented. We build on this result and discuss corresponding conditions under which $\mathcal{M}_{3}=\mathcal{M}_{1}\cup\mathcal{M}_{2}$ is an exact solution to $BOT(\mathcal{G}_{3})$ when $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are both bottleneck clusters.

Once again, consider an arbitrary complete bipartite graph $\mathcal{G}_{b}=(\mathcal{V}_{b},\mathcal{E}_{b})$. Given $\mathcal{M}$ is an MCM of $\mathcal{G}_{b}$, we define $\phi(\mathcal{G}_{b},\mathcal{M}):=\mathcal{M}\cup\{e\in\mathcal{E}_{b}|w(e)<\max_{e^{\prime}\in\mathcal{M}}w(e^{\prime})\}$, the union of $\mathcal{M}$ and the set of edges that have weight strictly smaller than the largest edge in $\mathcal{M}$. With this tool we define a bottleneck cluster and a critical bottleneck edge.

Lemma 15 allows us to find a new MCM, which will have at least one less edge with weight $\max_{e\in\mathcal{M}}w(e)$ than $\mathcal{M}$.

An MCM that is a solution to $BOT(\mathcal{G}_{b})$ may contain more than one critical bottleneck edge. The following proposition shows how a critical bottleneck edge forms a particular alternating path between the bottleneck agent and bottleneck task.

Path $P=\{e_{c}\}$ is trivially an alternating path relative to $\mathcal{M}_{b}$; edge $e_{c}\in\mathcal{M}_{b}$, so $P\subseteq\phi(\mathcal{G}_{b},\mathcal{M}_{b})$. It remains to show that there does not exist another. Assume for contradiction that there exists an alternating path $P^{\prime}\neq P$, $P^{\prime}\subseteq\phi(\mathcal{G}_{b},\mathcal{M}_{b})$ relative to $\mathcal{M}_{b}$ between $a_{c}$ and $b_{c}$. It follows that $e_{c}\notin P^{\prime}$ and therefore $P^{\prime}\subseteq\phi(\mathcal{G}_{b},\mathcal{M}_{b})\backslash\{e_{c}\}$. Furthermore, $P^{\prime}$ is an augmenting path relative to $\mathcal{M}_{b}\backslash\{e_{c}\}$. By Definition 14, $e_{c}$ is not a critical bottleneck edge of $\mathcal{G}_{b}$, which contradicts Assumption 17. ∎

The following corollary describes the structure of a bottleneck cluster $\mathcal{G}_{b}$ based on Proposition 18.

Fig. 1 illustrates Corollary 19. The graph $\mathcal{G}_{b}$ is represented by two alternating trees $\mathcal{S}_{\nu}(\mathcal{G}_{b})$ and $\mathcal{S}_{\mu}(\mathcal{G}_{b})$ with roots $b_{1}$ and $a_{1}$ respectively. The roots $a_{1}$ and $b_{1}$ are incident to the critical bottleneck edge $e_{c}$ with weight $w(e_{c})=20$. All edges in both trees are elements of $\phi(\mathcal{G}_{b},\mathcal{M}_{b})$ as their weights are smaller than or equal to $w(e_{c})$ and all edges not in the matching are strictly smaller than $w(e_{c})$. Recall from Theorem 12 that $w(e_{3})\leq\max\{w(e_{1}),w(e_{2})\}$. Given Assumptions 9 and 10, the contrapositive of the following lemma provides conditions for the bottleneck edge of graph $\mathcal{G}_{3}$ to have equal weight to $\max\{w(e_{1}),w(e_{2})\}$.

Without loss of generality, let $e_{1}=\{a_{1},b_{1}\}$. By Proposition 18, $e_{1}$ is the only alternating path between $a_{1}$ and $b_{1}$ in $\phi(\mathcal{G}_{1},\mathcal{M}_{1})$. Assume there does not exist vertices $i$ and $j$ such that all i., ii., and iii. are true. Thus, $e_{1}$ is the only alternating path between $a_{1}$ and $b_{1}$ in $\phi(\mathcal{G}_{3},\mathcal{M}_{1}\cup\mathcal{M}_{2})$. By Definition 14, $e_{1}$ is also a critical bottleneck edge of $\mathcal{G}_{3}$ since $e_{1}\in\arg\max_{e\in\mathcal{M}_{1}\cup\mathcal{M}_{2}}w(e)$ and there does not exist an augmenting path in $\phi(\mathcal{G}_{3},\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$ relative to $(\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$. Thus, $w(e_{3})=w(e_{1})$. ∎

In general, the converse of Lemma 20 does not hold unless we apply some additional assumptions. This leads to the following theorem.

The necessary condition for $w(e_{3})<w(e_{1})$ holds from Lemma 20. We now prove the sufficient condition. Assume there exists vertices $i$ and $j$ such that all i., ii., and iii. are true. Then, aside from path $P=\{e_{1}=\{a_{1},b_{1}\}\}$, there exists another alternating path $P^{\prime}$ between $a_{1}$ and $b_{1}$, which does not contain the edge $e_{1}$. Namely, the alternating path $P^{\prime}$ constructed from the union of the alternating paths between $a_{1}$ and $b^{\prime}$, $b^{\prime}$ and $i$, $i$ and $j$, $j$ and $a^{\prime}$, and $a^{\prime}$ and $b_{1}$. Thus, there exists an augmenting path $P^{\prime}\subseteq\phi(\mathcal{G}_{3},\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$ relative to $(\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$. From Lemma 15, there exists an MCM $\mathcal{M}^{\prime}$ of $\mathcal{G}_{3}$ such that $\mathcal{M}^{\prime}\in\phi(\mathcal{G}_{3},\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$. By the assumptions on $e_{1}$, $\phi(\mathcal{G}_{3},\mathcal{M}_{1}\cup\mathcal{M}_{2})\backslash\{e_{1}\}$ contains only edges with weights strictly smaller than $w(e_{1})$. Thus, there exists an MCM of $\mathcal{G}_{3}$ with all edges having weight smaller than $w(e_{1})$, i.e., $w(e_{3})$ must be smaller than $w(e_{3})$. ∎

Fig. 2 illustrates the sufficient condition of Theorem 21. The orange dashed line is an edge that satisfies the condition i. since $\alpha_{2}\in\mathcal{V}_{2}$ and there exists edge $\{\alpha_{2},b_{3}\}\in\mathcal{V}_{3}$, where $b_{3}$ is a task in the vertex set of $\mathcal{S}_{\nu}(\mathcal{G}_{1})$. The blue dashed line satisfies condition ii. since $\beta_{1}\in\mathcal{V}_{2}$ and there exists edge $\{\beta_{1},a_{2}\}\in\mathcal{V}_{3}$, where $a_{2}$ is an agent in the vertex set of $\mathcal{S}_{\mu}(\mathcal{G}_{1})$. Condition iii. is satisfied since there is an alternating path $P=\{\{\alpha_{1},\beta_{1}\},\{\alpha_{2},\beta_{2}\},\{\alpha_{1},\beta_{2}\}\}$ between $\beta_{1}$ and $\alpha_{2}$, and $|\{\{\alpha_{1},\beta_{1}\},\{\alpha_{2},\beta_{2}\}\}|>|\{\{\alpha_{1},\beta_{2}\}\}|$, i.e., $P$ starts with a dashed line and ends with a dashed line. Corollary 22 follows from Theorem 12 and 21.

Solving Problem 11 by pruneBAP with an arbitrary MCM $\mathcal{M}_{0}$ at initialisation does not make use of Assumptions 9 and 10. We denote this as a cold-start to pruneBAP. Given Assumptions 9 and 10, consider the following. It holds that the set $\tilde{\mathcal{M}}:=\mathcal{M}_{1}\cup\mathcal{M}_{2}$ is an MCM of the graph $\mathcal{G}_{3}$. Without loss of generality, let $w(e_{1})\geq w(e_{2})$. Then, it also holds that $e_{1}$ is the largest edge in $\tilde{\mathcal{M}}$. We use make use of $\tilde{\mathcal{M}}$ to solve Problem 1 by choosing it as the initial MCM of pruneBAP. Edges in the set $\{e\in\mathcal{E}_{3}|w(e)\geq w(e_{1}),e\notin\mathcal{M}_{0}\}$ are removed from $\mathcal{E}_{3}$ in the first iteration. We denote this as a warm-start to pruneBAP. Fig. 4 illustrates a warm-start to pruneBAP.

Given Assumptions 9 and 10, warm-starting is a way to make use of the available information to solve Problem 11.

By Theorem 12, the assignment obtained from solving $BOT((\mathcal{A}\cup\mathcal{B}_{1},\mathcal{E}))$ and $BOT((\mathcal{A}_{2}\cup\mathcal{B}_{2},\mathcal{E}_{2}))$ in Case Study 1 is not necessarily the optimal solution to $BOT((\mathcal{A}\cup\mathcal{B}_{1}\cup\mathcal{B}_{2},\mathcal{E}_{3}))$, where $\mathcal{E}_{3}=\{\{i,j\}|i\in\mathcal{A},j\in\mathcal{B}_{1}\cup\mathcal{B}_{2}\}$. Fig. 5 shows a numerical example of a case where the optimal assignment is of lower cost than the assignment used to warm-start pruneBAP. For this example, $m_{3}=40$, $n_{1}=20$ and $n_{2}=20$. The data was generated using continuous uniform distributions with range $[0,100)$ for both coordinates $x$ and $y$. Fig. 6 shows a plot of the average cost of the assignment used as warm-start to initialise pruneBAP and the average cost of the optimal assignment after pruneBAP has terminated. For all simulations, $m_{3}=n_{1}+n_{2}$. For each even value of $m_{3}$, 100 simulations were generated. We observe that the cost of the assignment obtained from the subproblems is never greater than the cost of an optimal solution to $BOT(\mathcal{G}_{3})$, in accordance with Theorem 12. In this case, the unstructured distribution of the locations results in all of the conditions in Theorem 21 being satisfied and we observe that $w(e_{3})<\max\{w(e_{1}),w(e_{2})\}$ as expected.

In Case Study 2, we illustrate an example where not all of the conditions i., ii., and iii. in Lemma 20 hold. Fig. 7 shows a numerical example where the initial assignment $\mathcal{M}_{1}\cup\mathcal{M}_{2}$ used to warm-start pruneBAP is in fact the optimal assignment of $\mathcal{B}_{1}\cup\mathcal{B}_{2}$ to $\mathcal{A}_{1}\cup\mathcal{A}_{2}$. In this example, $m_{1}=20$, $m_{2}=20$, $n_{1}=20$ and $n_{2}=20$. The data in Fig. 7 was generated using independant normal distributions with a variance of 100 for each distribution. The distributions for sets $\mathcal{A}_{1}$ and $\mathcal{B}_{1}$ are centred at the point $(x,y)=(40,60)$. The distributions for sets $\mathcal{A}_{2}$ and $\mathcal{B}_{2}$ are centred at the point $(x,y)=(60,40)$. Fig. 8 shows the number of instances out of 100 simulations for which the behaviour in Fig. 7 is observed. That is, the instances where the bottleneck edges obtained from the subproblems directly results in an optimal solution to $BOT(\mathcal{G}_{3})$, where $\mathcal{G}_{3}$ is defined as in Section 3. The number of agents equals the number of tasks for each simulation, i.e., $m_{1}=n_{1}=m_{2}=n_{2}$. For each simulation, positions were generated using the same normal distribution as in Fig. 7. We now observe realisations where the cost of the assignment obtained from the subproblems is equal to the cost of an optimal solution to $BOT(\mathcal{G}_{3})$. This illustrates that with this distribution of agents and tasks there are instances where there is structure such that the conditions in Theorem 21 do not all hold and $w(e_{3})=\max\{w(e_{1}),w(e_{2})\}$.