Bjorck, J., Q. Shi, C. Brown-Lima, J. Dean, A. Fuller, and C. Gomes. Learning augmented methods for matching: Improving invasive species management and urban mobility. Association for the Advancement of Artificial Intelligence.
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 are 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 opportunistic 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.
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 are 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 opportunistic 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.