Learning Augmented Methods for Matching: Improving Invasive Species Management and Urban Mobility

Johan Bjorck, Qinru Shi, Carrie Brown-Lima, Jennifer Dean, Angela Fuller, Carla P. GomesAAAI 2021 · OpenReview

Abstract

With the success of machine learning, integrating learned models into real-world systems has become a critical challenge. Naively applying predictions to combinatorial optimization problems can incur high costs, which has motivated researchers to consider learning augmented algorithms that can make use of faulty or incomplete predictions. Inspired by two matching problems in computational sustainability where data is abundant, we consider the learning augmented min weight matching problem where some nodes are revealed online while others are known a priori, e.g., by being predicted by machine learning. We develop an algorithm that is able to make use of this extra information and provably improves upon pessimistic online algorithms. We evaluate our algorithm on two settings from computational sustainability -- the coordination of unreliable citizen scientists for invasive species management, and the matching between taxis and riders under uncertain trip duration predictions. In both cases, we perform extensive experiments on real-world datasets and find that our method outperforms baselines, showing how learning augmented algorithms can reliably improve solutions for problems in computational sustainability.

1. Introduction

Matching problems are a cornerstone of combinatorial optimization, involving the pairing of "workers" (such as taxis or observers) to "jobs" (such as riders or observation sites) at the lowest possible cost. In real-world applications, these problems are often online, meaning information is revealed dynamically. Traditional online algorithms typically adopt a "pessimistic" approach, assuming worst-case scenarios to provide theoretical guarantees. However, this often leads to ignoring valuable, albeit imperfect, predictions from machine learning models. Conversely, naively following ML predictions can lead to catastrophic failures if the model is incorrect.

This paper addresses the semi-online matching problem, where a subset of nodes is known a priori (predicted by ML), while others are revealed dynamically. The goal is to develop an algorithm that is both consistent (performing optimally with perfect advice) and robust (maintaining a safety net when advice is poor).

2. Methodology: Learning Augmented Matching

The proposed framework interpolates between the classical Hungarian method for offline matching and Raghvendra’s online matching algorithm. The algorithm operates through three primary mechanisms:

  1. Initial Planning: The algorithm begins by calculating an optimal min-cost matching ($M_*$) using only the predicted workers ($R_p$).
  2. Handling Arrivals: When a predicted worker arrives, they are matched according to the pre-calculated plan. If an unpredicted (adversarial) worker arrives, the algorithm finds a minimum-weight augmenting path from that worker to an empty job, updating the global matching $M_*$ to minimize the increase in total cost.
  3. Local Search Improvement: To enhance practical performance, a "Local Search" routine is added. When an unpredicted worker arrives, the algorithm examines a small neighborhood of nearby jobs and workers to identify quick swaps that reduce total distance without violating the theoretical structure of the augmenting paths.
The algorithm handles predicted arrivals by following a pre-set plan and unpredicted arrivals by finding augmenting paths to update the matching.

The core theoretical contribution is a competitive ratio of $O(1 + \log k)$, where $k$ is the number of unpredicted workers. This ensures that performance scales with the number of prediction errors rather than the total problem size.

3. Experimental Setup and Datasets

The researchers evaluated their method on two massive, real-world datasets representing key challenges in computational sustainability:

  • NYC Taxi and Limousine Commission (TLC): Utilizing a dataset of approximately 2 million taxi rides, the authors used XGBoost to predict trip durations. Taxis arriving as predicted were "known" workers, while those arriving early or late due to traffic or model error were treated as "unpredicted."
  • iMapInvasives (New York Natural Heritage Program): This dataset includes 30 years of data covering 200,000 observations of 408 invasive species. "Predicted" workers were paid employees with set schedules, while "unpredicted" workers were opportunistic citizen scientists.

4. Results and Discussion

The proposed "Local" algorithm consistently outperformed all baselines, including greedy approaches and purely adversarial online algorithms.

In the urban mobility task, the "Local" method achieved the lowest total distance traveled across almost all test dates. For instance, on March 27th, the Local method resulted in 154 km of travel, compared to 183 km for the standard adversarial online algorithm. In the invasive species management task, the Local method was the top performer in 25 out of 28 years between 1992 and 2019.

Average cost decreases as the fraction of known (predicted) workers increases, with the 'local' method consistently achieving the lowest cost among practical algorithms.

Ablation studies demonstrate that as the fraction of predicted nodes increases, the average cost drops significantly. This confirms that the algorithm effectively leverages ML predictions while maintaining robustness against errors.

5. Conclusion and Future Work

This work demonstrates that learning augmented algorithms can significantly improve solutions for matching problems in computational sustainability. By utilizing augmenting paths and local search, the proposed method provides error-dependent guarantees that allow practitioners to benefit from ML predictions without fearing "black box" failure modes.

Future research directions include explicitly optimizing for passenger waiting times in ride-hailing contexts and extending the model to fully dynamic environments where both workers and jobs appear and disappear over time.

Summary updated

Abstract

With the success of machine learning, integrating learned models into real-world systems has become a critical challenge. Naively applying predictions to combinatorial optimization problems can incur high costs, which has motivated researchers to consider learning augmented algorithms that can make use of faulty or incomplete predictions. Inspired by two matching problems in computational sustainability where data is abundant, we consider the learning augmented min weight matching problem where some nodes are revealed online while others are known a priori, e.g., by being predicted by machine learning. We develop an algorithm that is able to make use of this extra information and provably improves upon pessimistic online algorithms. We evaluate our algorithm on two settings from computational sustainability -- the coordination of unreliable citizen scientists for invasive species management, and the matching between taxis and riders under uncertain trip duration predictions. In both cases, we perform extensive experiments on real-world datasets and find that our method outperforms baselines, showing how learning augmented algorithms can reliably improve solutions for problems in computational sustainability.
BibTeX
@inproceedings{bjorck2021learning,
  author = {Johan Bjorck and Qinru Shi and Carrie Brown-Lima and Jennifer Dean and Angela Fuller and Carla P. Gomes},
  title = {{Learning Augmented Methods for Matching: Improving Invasive Species Management and Urban Mobility}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=wQKLd7J0dO},
}
Figure