Kevin Tierney

TMLR Journal 2025 Journal Article

Neural Deconstruction Search for Vehicle Routing Problems

• André Hottung
• Paula Wong-Chung
• Kevin Tierney

Autoregressive construction approaches generate solutions to vehicle routing problems in a step-by-step fashion, leading to high-quality solutions that are nearing the performance achieved by handcrafted operations research techniques. In this work, we challenge the conventional paradigm of sequential solution construction and introduce an iterative search framework where solutions are instead deconstructed by a neural policy. Throughout the search, the neural policy collaborates with a simple greedy insertion algorithm to rebuild the deconstructed solutions. Our approach matches or surpasses the performance of state-of-the-art operations research methods across three challenging vehicle routing problems of various problem sizes.

TMLR Journal 2025 Journal Article

On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI

• André Artelt
• Martin Olsen
• Kevin Tierney

Providing clear explanations to the choices of machine learning models is essential for these models to be deployed in crucial applications. Counterfactual and semi-factual explanations have emerged as two mechanisms for providing users with insights into the outputs of their models. We provide an overview of the computational complexity results in the literature for generating these explanations, finding that in many cases, generating explanations is computationally hard. We strengthen the argument for this considerably by further contributing our own inapproximability results showing that not only are explanations often hard to generate, but under certain assumptions, they are also hard to approximate. We discuss the implications of these complexity results for the XAI community and for policymakers seeking to regulate explanations in AI.

ICLR Conference 2025 Conference Paper

PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization

• André Hottung
• Mridul Mahajan
• Kevin Tierney

Reinforcement learning-based methods for constructing solutions to combinatorial optimization problems are rapidly approaching the performance of human-designed algorithms. To further narrow the gap, learning-based approaches must efficiently explore the solution space during the search process. Recent approaches artificially increase exploration by enforcing diverse solution generation through handcrafted rules, however, these rules can impair solution quality and are difficult to design for more complex problems. In this paper, we introduce PolyNet, an approach for improving exploration of the solution space by learning complementary solution strategies. In contrast to other works, PolyNet uses only a single-decoder and a training schema that does not enforce diverse solution generation through handcrafted rules. We evaluate PolyNet on four combinatorial optimization problems and observe that the implicit diversity mechanism allows PolyNet to find better solutions than approaches that explicitly enforce diverse solution generation.

TMLR Journal 2025 Journal Article

RouteFinder: Towards Foundation Models for Vehicle Routing Problems

• Federico Berto
• Chuanbo Hua
• Nayeli Gast Zepeda
• André Hottung
• Niels Wouda
• Leon Lan
• Junyoung Park
• Kevin Tierney

This paper introduces RouteFinder, a comprehensive foundation model framework to tackle different Vehicle Routing Problem (VRP) variants. Our core idea is that a foundation model for VRPs should be able to represent variants by treating each as a subset of a generalized problem equipped with different attributes. We propose a unified VRP environment capable of efficiently handling any combination of these attributes. The RouteFinder model leverages a modern transformer-based encoder and global attribute embeddings to improve task representation. Additionally, we introduce two reinforcement learning techniques to enhance multi-task performance: mixed batch training, which enables training on different variants at once, and multi-variant reward normalization to balance different reward scales. Finally, we propose efficient adapter layers that enable fine-tuning for new variants with unseen attributes. Extensive experiments on 48 VRP variants show RouteFinder outperforms recent state-of-the-art learning methods. Our code is publicly available at https://github.com/ai4co/routefinder.

IJCAI Conference 2023 Conference Paper

A Survey of Methods for Automated Algorithm Configuration (Extended Abstract)

• Elias Schede
• Jasmin Brandt
• Alexander Tornede
• Marcel Wever
• Viktor Bengs
• Eyke Hüllermeier
• Kevin Tierney

Algorithm configuration (AC) is concerned with the automated search of the most suitable parameter configuration of a parametrized algorithm. There are currently a wide variety of AC problem variants and methods proposed in the literature. Existing reviews do not take into account all derivatives of the AC problem, nor do they offer a complete classification scheme. To this end, we introduce taxonomies to describe the AC problem and features of configuration methods, respectively. Existing AC literature is classified and characterized by the provided taxonomies.

AAAI Conference 2023 Conference Paper

AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration

• Jasmin Brandt
• Elias Schede
• Björn Haddenhorst
• Viktor Bengs
• Eyke Hüllermeier
• Kevin Tierney

We study the algorithm configuration (AC) problem, in which one seeks to find an optimal parameter configuration of a given target algorithm in an automated way. Although this field of research has experienced much progress recently regarding approaches satisfying strong theoretical guarantees, there is still a gap between the practical performance of these approaches and the heuristic state-of-the-art approaches. Recently, there has been significant progress in designing AC approaches that satisfy strong theoretical guarantees. However, a significant gap still remains between the practical performance of these approaches and state-of-the-art heuristic methods. To this end, we introduce AC-Band, a general approach for the AC problem based on multi-armed bandits that provides theoretical guarantees while exhibiting strong practical performance. We show that AC-Band requires significantly less computation time than other AC approaches providing theoretical guarantees while still yielding high-quality configurations.

AIJ Journal 2023 Journal Article

The first AI4TSP competition: Learning to solve stochastic routing problems

• Yingqian Zhang
• Laurens Bliek
• Paulo da Costa
• Reza Refaei Afshar
• Robbert Reijnen
• Tom Catshoek
• Daniël Vos
• Sicco Verwer

This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods. The instances and code for the competition are available at https: //github. com/paulorocosta/ai-for-tsp-competition.

JAIR Journal 2022 Journal Article

A Survey of Methods for Automated Algorithm Configuration

• Elias Schede
• Jasmin Brandt
• Alexander Tornede
• Marcel Wever
• Viktor Bengs
• Eyke Hüllermeier
• Kevin Tierney

Algorithm configuration (AC) is concerned with the automated search of the most suitable parameter configuration of a parametrized algorithm. There is currently a wide variety of AC problem variants and methods proposed in the literature. Existing reviews do not take into account all derivatives of the AC problem, nor do they offer a complete classification scheme. To this end, we introduce taxonomies to describe the AC problem and features of configuration methods, respectively. We review existing AC literature within the lens of our taxonomies, outline relevant design choices of configuration approaches, contrast methods and problem variants against each other, and describe the state of AC in industry. Finally, our review provides researchers and practitioners with a look at future research directions in the field of AC.

ICLR Conference 2022 Conference Paper

Efficient Active Search for Combinatorial Optimization Problems

• André Hottung
• Yeong-Dae Kwon
• Kevin Tierney

Recently numerous machine learning based methods for combinatorial optimization problems have been proposed that learn to construct solutions in a sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straightforward to integrate them into a high-level search procedure offering strong search guidance. Bello et al. (2016) propose active search, which adjusts the weights of a (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of a given model and outperform state-of-the-art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.

AIJ Journal 2022 Journal Article

Neural large neighborhood search for routing problems

• André Hottung
• Kevin Tierney

Learning how to automatically solve optimization problems has the potential to provide the next big leap in optimization technology. The performance of automatically learned heuristics on routing problems has been steadily improving in recent years, but approaches based purely on machine learning are still outperformed by state-of-the-art optimization methods. To close this performance gap, we propose a novel large neighborhood search (LNS) framework for vehicle routing that integrates learned heuristics for generating new solutions. The learning mechanism is based on a deep neural network with an attention mechanism and has been especially designed to be integrated into an LNS search setting. We evaluate our approach on the capacitated vehicle routing problem (CVRP), the split delivery vehicle routing problem (SDVRP), and the capacitated team orienteering problem (CTOP). We show that the NLNS approach is able to outperform a handcrafted LNS on the CVRP and SDVRP and match the performance of a standard LNS on the CTOP. NLNS is thus able to quickly and effectively learn high performance heuristics to maneuver through the search space of difficult routing problems, coming close to the performance of state-of-the-art optimization approaches.

NeurIPS Conference 2022 Conference Paper

Simulation-guided Beam Search for Neural Combinatorial Optimization

• Jinho Choo
• Yeong-Dae Kwon
• Jihoon Kim
• Jeongwoo Jae
• André Hottung
• Kevin Tierney
• Youngjune Gwon

Neural approaches for combinatorial optimization (CO) equip a learning mechanism to discover powerful heuristics for solving complex real-world problems. While neural approaches capable of high-quality solutions in a single shot are emerging, state-of-the-art approaches are often unable to take full advantage of the solving time available to them. In contrast, hand-crafted heuristics perform highly effective search well and exploit the computation time given to them, but contain heuristics that are difficult to adapt to a dataset being solved. With the goal of providing a powerful search procedure to neural CO approaches, we propose simulation-guided beam search (SGBS), which examines candidate solutions within a fixed-width tree search that both a neural net-learned policy and a simulation (rollout) identify as promising. We further hybridize SGBS with efficient active search (EAS), where SGBS enhances the quality of solutions backpropagated in EAS, and EAS improves the quality of the policy used in SGBS. We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable runtime assumptions.

ICLR Conference 2021 Conference Paper

Learning a Latent Search Space for Routing Problems using Variational Autoencoders

• André Hottung
• Bhanu Bhandari
• Kevin Tierney

Methods for automatically learning to solve routing problems are rapidly improving in performance. While most of these methods excel at generating solutions quickly, they are unable to effectively utilize longer run times because they lack a sophisticated search component. We present a learning-based optimization approach that allows a guided search in the distribution of high-quality solutions for a problem instance. More precisely, our method uses a conditional variational autoencoder that learns to map points in a continuous (latent) search space to high-quality, instance-specific routing problem solutions. The learned space can then be searched by any unconstrained continuous optimization method. We show that even using a standard differential evolution search strategy our approach is able to outperform existing purely machine learning based approaches.

SAT Conference 2021 Conference Paper

PyDGGA: Distributed GGA for Automatic Configuration

• Carlos Ansótegui
• Josep Pon
• Meinolf Sellmann
• Kevin Tierney

Abstract We present PyDGGA, a Python tool that implements a distributed version of the automatic algorithm configurator GGA, which is a specialized genetic algorithm to find high quality parameters for solvers and algorithms. PyDGGA implements GGA using an event-driven architecture and runs a simulation of future generations of the genetic algorithm to maximize the usage of the available computing resources. Overall, PyDGGA offers a friendly interface to deploy elastic distributed AC scenarios on shared high-performance computing clusters.

ECAI Conference 2020 Conference Paper

Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem

• André Hottung
• Kevin Tierney

Learning how to automatically solve optimization problems has the potential to provide the next big leap in optimization technology. The performance of automatically learned heuristics on routing problems has been steadily improving in recent years, but approaches based purely on machine learning are still outperformed by state-of-the-art optimization methods. To close this performance gap, we propose a novel large neighborhood search (LNS) framework for vehicle routing that integrates learned heuristics for generating new solutions. The learning mechanism is based on a deep neural network with an attention mechanism and has been especially designed to be integrated into an LNS search setting. We evaluate our approach on the capacitated vehicle routing problem (CVRP) and the split delivery vehicle routing problem (SDVRP). On CVRP instances with up to 297 customers, our approach significantly outperforms an LNS that uses only handcrafted heuristics and a well-known heuristic from the literature. Furthermore, we show for the CVRP and the SDVRP that our approach surpasses the performance of existing machine learning approaches and comes close to the performance of state-of-the-art optimization approaches.

AAAI Conference 2017 Conference Paper

Reactive Dialectic Search Portfolios for MaxSAT

• Carlos Ans—tegui
• Josep Pon
• Meinolf Sellmann
• Kevin Tierney

Metaheuristics have been developed to provide general purpose approaches for solving hard combinatorial problems. While these frameworks often serve as the starting point for the development of problem-specific search procedures, they very rarely work efficiently in their default state. We combine the ideas of reactive search, which adjusts key parameters during search, and algorithm configuration, which fine-tunes algorithm parameters for a given set of problem instances, for the automatic compilation of a portfolio of highly reactive dialectic search heuristics for MaxSAT. Even though the dialectic search metaheuristic knows nothing more about MaxSAT than how to evaluate the cost of a truth assignment, our automatically generated solver de- fines a new state of the art for random weighted partial MaxSAT instances. Moreover, when combined with an industrial MaxSAT solver, the self-assembled reactive portfolio was able to win four out of nine gold medals at the recent 2016 MaxSAT Evaluation on random, crafted, and industrial partial and weighted-partial MaxSAT instances.

AIJ Journal 2016 Journal Article

ASlib: A benchmark library for algorithm selection

• Bernd Bischl
• Pascal Kerschke
• Lars Kotthoff
• Marius Lindauer
• Yuri Malitsky
• Alexandre Fréchette
• Holger Hoos
• Frank Hutter

The task of algorithm selection involves choosing an algorithm from a set of algorithms on a per-instance basis in order to exploit the varying performance of algorithms over a set of instances. The algorithm selection problem is attracting increasing attention from researchers and practitioners in AI. Years of fruitful applications in a number of domains have resulted in a large amount of data, but the community lacks a standard format or repository for this data. This situation makes it difficult to share and compare different approaches effectively, as is done in other, more established fields. It also unnecessarily hinders new researchers who want to work in this area. To address this problem, we introduce a standardized format for representing algorithm selection scenarios and a repository that contains a growing number of data sets from the literature. Our format has been designed to be able to express a wide variety of different scenarios. To demonstrate the breadth and power of our platform, we describe a study that builds and evaluates algorithm selection models through a common interface. The results display the potential of algorithm selection to achieve significant performance improvements across a broad range of problems and algorithms.

IJCAI Conference 2015 Conference Paper

Model-Based Genetic Algorithms for Algorithm Configuration

• Carlos Ansotegui
• Yuri Malitsky
• Horst Samulowitz
• Meinolf Sellmann
• Kevin Tierney

AAAI Conference 2014 Conference Paper

Online Search Algorithm Configuration

• Tadhg Fitzgerald
• Barry O'Sullivan
• Yuri Malitsky
• Kevin Tierney

SoCS Conference 2014 Conference Paper

ReACT: Real-Time Algorithm Configuration through Tournaments

• Tadhg Fitzgerald
• Yuri Malitsky
• Barry O'Sullivan
• Kevin Tierney

The success or failure of a solver is oftentimes closely tied to the proper configuration of the solver

ICAPS Conference 2012 Conference Paper

Automated Planning for Liner Shipping Fleet Repositioning

• Kevin Tierney
• Amanda Jane Coles
• Andrew Coles
• Christian Kroer
• Adam M. Britt
• Rune Møller Jensen

The Liner Shipping Fleet Repositioning Problem (LSFRP) poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between services in a liner shipping network. The LSFRP is characterized by chains of interacting activities, many of which have costs that are a function of their duration; for example, sailing slowly between two ports is cheaper than sailing quickly. Despite its great industrial importance, the LSFRP has received little attention in the literature. We show how the LSFRP can be solved sub-optimally using the planner POPF and optimally with a mixed-integer program (MIP) and a novel method called Temporal Optimization Planning (TOP). We evaluate the performance of each of these techniques on a dataset of real-world instances from our industrial collaborator, and show that automated planning scales to the size of problems faced by industry.

ECAI Conference 2010 Conference Paper

ISAC - Instance-Specific Algorithm Configuration

• Serdar Kadioglu
• Yuri Malitsky
• Meinolf Sellmann
• Kevin Tierney

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with categorical, ordinal, and/or continuous parameters, a training benchmark set of input instances for that solver, and an algorithm that computes a feature vector that characterizes any given instance. ISAC then provides high quality parameter settings for any new input instance. Experiments on a variety of different constrained optimization and constraint satisfaction solvers show that automatic algorithm configuration vastly outperforms manual tuning. Moreover, we show that instance-specific tuning frequently leads to significant speed-ups over instance-oblivious configurations.