Sensitivity Analysis for Bottleneck Assignment Problems

Michael Elad, Tony A. Wood, Chris Manzie, Iman ShamesarXiv 2021 · DOI · arXiv

TL;DR

This paper introduces a novel framework for sensitivity analysis in Bottleneck Assignment Problems (BAP), moving beyond traditional "one-at-a-time" weight changes to handle simultaneous perturbations across all assignment weights. By leveraging a new theoretical tool called "exclusive sets," the authors provide algorithms to calculate the maximum allowable intervals for weights that keep an assignment optimal, offering a more robust way to handle uncertainty in parallel task systems.

What Problem Does This Paper Address?

In a classic assignment problem, you want to match $n$ agents to $m$ tasks to minimize a cost. While most research focuses on the Linear Assignment Problem (minimizing the total sum of costs), this paper focuses on the Bottleneck Assignment Problem (BAP). BAP aims to minimize the maximum cost in the assignment—think of it as minimizing the time the last drone in a swarm takes to reach its destination.

The challenge is that real-world costs (weights) are rarely exact. They are subject to measurement errors, communication delays, or dynamic environments. Sensitivity analysis tells us how much these weights can change before our "optimal" solution is no longer optimal.

Existing methods usually only look at what happens if one weight changes while others stay fixed. However, in parallel systems (like a fleet of robots), weights often change simultaneously. This paper fills that gap by providing a way to calculate allowable perturbation intervals for all edges at once.

Methods

The authors introduce two primary frameworks for sensitivity:

  1. Bottleneck Edge Sensitivity: How much can weights change such that a specific edge remains the bottleneck of some optimal assignment?
  2. Bottleneck Assignment Sensitivity: How much can weights change such that the entire current assignment remains optimal?

Key Innovations:

  • Exclusive Sets: This is the paper's central theoretical contribution. An exclusive set $S_{e^*}$ for an edge $e^*$ is a collection of edges such that every possible assignment must either include $e^*$ or at least one edge from $S_{e^*}$. This allows the authors to mathematically "trap" the bottleneck.
  • Lexicographic Ordering: To find the "best" intervals, the authors use lexicographic maximization. Instead of just finding any range, they find the range that is "largest" in a specific priority order (maximizing the smallest bound, then the second smallest, and so on).
  • Algorithms: They present two main algorithms. Algorithm 1 constructs the exclusive set iteratively by removing bottleneck edges and finding new ones. Algorithm 2 builds on this to construct the full array of allowable intervals for the entire assignment.

Datasets

The paper does not use large-scale public datasets. Instead, it utilizes constructed numerical examples (e.g., $3 \times 3$ weight matrices) to provide a "walkthrough" of the algorithms and to compare their results against previous methods like the "sensitivity radius" proposed by Sotskov et al. (1995).

Key Insights and Ideas

  • Parallelism Matters: The authors argue that simultaneous perturbation is the only realistic way to view sensitivity in BAP because the very nature of BAP (minimizing the maximum) implies tasks are being performed in parallel.
  • The "Aha" Moment on Exclusive Sets: By identifying edges that must be used if the current bottleneck is avoided, you can define exactly how much "room" you have to increase the current bottleneck's weight or decrease the weights of alternative edges.
  • Warm-Starting for Speed: The authors note that their iterative algorithms can be "warm-started" using previous optimal solutions, significantly reducing the computational burden compared to solving a BAP from scratch at every step.

Key Results

  • Optimality Proof: The authors theoretically prove that their methods produce the lexicographically largest set of allowable perturbations.
  • Computational Complexity:
    • Bottleneck Edge Sensitivity can be computed in $O(n^3)$ for dense graphs.
  • Bottleneck Assignment Sensitivity is slightly more intensive at $O(n^4)$.
  • Granularity: Compared to the "sensitivity radius" method (which gives a single uniform bound for all edges), this paper’s approach provides individualized intervals for every edge. This means some edges might be revealed to be much more "sensitive" than others, providing better decision-making data for engineers.

Limitations and Future Work

  • The Uniqueness Assumption: The current algorithms rely on "Assumptions 1 and 2," which state that the bottleneck edge found at each iteration must be unique. If there are ties (multiple edges with the same bottleneck weight), the algorithm isn't guaranteed to find the absolute largest lexicographic interval.
  • Tie-Breaking: The authors suggest that a "weight scaling" approach might be a way to relax these uniqueness assumptions in the future.
  • Broader Applications: While this paper focuses on BAP, the "exclusive set" logic could potentially be expanded to other combinatorial optimization problems where "bottleneck" objectives are common.

Summary updated

Abstract

In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all assignment weights. Focusing on the bottleneck assignment problem, we provide two different methods of quantifying the sensitivity of the optimal assignment, and present algorithms for each. Numerical examples as well as a discussion of the complexity for all algorithms are provided.
BibTeX
@misc{elad2021sensitivity,
  author = {Michael Elad and Tony A. Wood and Chris Manzie and Iman Shames},
  title = {{Sensitivity Analysis for Bottleneck Assignment Problems}},
  year = {2021},
  eprint = {2104.00803},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2104.00803},
}
Figure