Guido Tack

AAAI Conference 2025 Conference Paper

Resource Constrained Pathfinding with Enhanced Bidirectional A* Search

• Saman Ahmadi
• Andrea Raith
• Guido Tack
• Mahdi Jalili

The classic Resource Constrained Shortest Path (RCSP) problem aims to find a cost optimal path between a pair of nodes in a network such that the resources used in the path are within a given limit. Having been studied for over a decade, RCSP has seen recent solutions that utilize heuristic-guided search to solve the constrained problem faster. Building upon the bidirectional A* search paradigm, this paper introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks. Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.

AIJ Journal 2022 Journal Article

Globalizing constraint models

• Kevin Leo
• Christopher Mears
• Guido Tack
• Maria Garcia de la Banda

We present a method to detect implicit model patterns (such as global constraints) that might be able to replace parts of a combinatorial problem model that are expressed at a low-level. This can help non-expert users write higher-level models that are easier to reason about and often yield better performance. Our method generates candidate model patterns by analyzing both the structure of the model – its constraints, variables, parameters and loops – and the input data from one or more data files. Each candidate is scored by comparing a sample of its solution space with that of the part of the model it is intended to replace. The top-scoring candidates are presented to the user through an interactive display, which shows how they could be incorporated into the model. The method is implemented for the MiniZinc modeling language and available as part of the MiniZinc distribution.

SoCS Conference 2022 Conference Paper

Weight Constrained Path Finding with Bidirectional A

• Saman Ahmadi
• Guido Tack
• Daniel Harabor
• Philip Kilby

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i. e. , the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.

AAAI Conference 2021 Conference Paper

A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem

• Saman Ahmadi
• Guido Tack
• Daniel D. Harabor
• Philip Kilby

Resource constrained path finding is a well studied topic in AI, with real-world applications in different areas such as transportation and robotics. This paper introduces several heuristics in the resource constrained path finding context that significantly improve the algorithmic performance of the initialisation phase and the core search. We implement our heuristics on top of a bidirectional A* algorithm and evaluate them on a set of large instances. The experimental results show that, for the first time in the context of constrained path finding, our fast and enhanced algorithm can solve all of the benchmark instances to optimality, and compared to the state of the art algorithms, it can improve existing runtimes by up to four orders of magnitude on large-size network graphs.

SoCS Conference 2021 Conference Paper

Bi-Objective Search with Bi-directional A* (Extended Abstract)

• Saman Ahmadi
• Guido Tack
• Daniel Harabor
• Philip Kilby

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art bi-objective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

AAAI Conference 2020 Conference Paper

Modelling and Solving Online Optimisation Problems

• Alexander Ek
• Maria Garcia de la Banda
• Andreas Schutt
• Peter J. Stuckey
• Guido Tack

Many optimisation problems are of an online—also called dynamic—nature, where new information is expected to arrive and the problem must be resolved in an ongoing fashion to (a) improve or revise previous decisions and (b) take new ones. Typically, building an online decision-making system requires substantial ad-hoc coding to ensure the offline version of the optimisation problem is continually adjusted and resolved. This paper defines a general framework for automatically solving online optimisation problems. This is achieved by extending a model of the offline optimisation problem, from which an online version is automatically constructed, thus requiring no further modelling effort. In doing so, it formalises many of the aspects that arise in online optimisation problems. The same framework can be applied for automatically creating sliding-window solving approaches for problems that have a large time horizon. Experiments show we can automatically create efficient online and sliding-window solutions to optimisation problems.

AAAI Conference 2020 Conference Paper

Modelling Diversity of Solutions

• Linnea Ingmar
• Maria Garcia de la Banda
• Peter J. Stuckey
• Guido Tack

For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the nondominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.

AAAI Conference 2018 Conference Paper

A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems

• David Hemmi
• Guido Tack
• Mark Wallace

Stochastic programming is concerned with decision making under uncertainty, seeking an optimal policy with respect to a set of possible future scenarios. This paper looks at multistage decision problems where the uncertainty is revealed over time. First, decisions are made with respect to all possible future scenarios. Secondly, after observing the random variables, a set of scenario specific decisions is taken. Our goal is to develop algorithms that can be used as a back-end solver for high-level modeling languages. In this paper we propose a scenario decomposition method to solve multistage stochastic combinatorial decision problems recursively. Our approach is applicable to general problem structures, utilizes standard solving technology and is highly parallelizable. We provide experimental results to show how it efficiently solves benchmarks with hundreds of scenarios.

AIJ Journal 2017 Journal Article

Introduction to the special issue on Combining Constraint Solving with Mining and Learning

• Andrea Passerini
• Guido Tack
• Tias Guns

AIJ Journal 2017 Journal Article

MiningZinc: A declarative framework for constraint-based mining

• Tias Guns
• Anton Dries
• Siegfried Nijssen
• Guido Tack
• Luc De Raedt

We introduce MiningZinc, a declarative framework for constraint-based data mining. MiningZinc consists of two key components: a language component and an execution mechanism. First, the MiningZinc language allows for high-level and natural modeling of mining problems, so that MiningZinc models are similar to the mathematical definitions used in the literature. It is inspired by the Zinc family of languages and systems and supports user-defined constraints and functions. Secondly, the MiningZinc execution mechanism specifies how to compute solutions for the models. It is solver independent and supports both standard constraint solvers and specialized data mining systems. The high-level problem specification is first translated into a normalized constraint language (FlatZinc). Rewrite rules are then used to add redundant constraints or solve subproblems using specialized data mining algorithms or generic constraint programming solvers. Given a model, different execution strategies are automatically extracted that correspond to different sequences of algorithms to run. Optimized data mining algorithms, specialized processing routines and generic solvers can all be automatically combined. Thus, the MiningZinc language allows one to model constraint-based itemset mining problems in a solver independent way, and its execution mechanism can automatically chain different algorithms and solvers. This leads to a unique combination of declarative modeling with high-performance solving.

LOPSTR Conference 2016 Conference Paper

MiniZinc with Strings

• Roberto Amadini
• Pierre Flener
• Justin Pearson
• Joseph D. Scott
• Peter J. Stuckey
• Guido Tack

Abstract Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no constraint programming solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying only on integer variables. This conversion is obtained via rewrite rules, and does not require any extension of the existing FlatZinc specification. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

IJCAI Conference 2015 Conference Paper

Multi-Pass High-Level Presolving

• Kevin Leo
• Guido Tack

Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solverlevel programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.

IJCAI Conference 2013 Conference Paper

MiningZinc: A Modeling Language for Constraint-based Mining

• Tias Guns
• Anton Dries
• Guido Tack
• Siegfried Nijssen
• Luc De Raedt

We introduce MiningZinc, a general framework for constraint-based pattern mining, one of the most popular tasks in data mining. MiningZinc consists of two key components: a language component and a toolchain component. The language allows for high-level and natural modeling of mining problems, such that MiningZinc models closely resemble definitions found in the data mining literature. It is inspired by the Zinc family of languages and systems and supports user-defined constraints and optimization criteria. The toolchain allows for finding solutions to the models. It ensures the solver independence of the language and supports both standard constraint solvers and specialized data mining systems. Automatic model transformations enable the efficient use of different solvers and systems. The combination of both components allows one to rapidly model constraint-based mining problems and execute these with a wide variety of methods. We demonstrate this experimentally for a number of well-known solvers and data mining tasks.

LOPSTR Conference 2012 Conference Paper

An Introduction to Search Combinators

• Tom Schrijvers
• Guido Tack
• Pieter Wuille
• Horst Samulowitz
• Peter J. Stuckey

Abstract The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver.