TBA

Anytime and Exact Extensions of A* for the TSP-TW

Abstract: The Travelling Salesman Problem (TSP) may be solved by searching for a best path in a state-transition graph which is derived from Bellman equations, and this state-transition graph may be easily extended to solve the TSP with Time-windows (TSP-TW), where arrival times are constrained to belong to given time intervals, or with time-dependent cost functions, where travel times depend on departure times. In this talk, we will provide an overview of exact and anytime extensions of A* which may be used to search for best paths in state-transition graphs, and show how to combine them with local search (in order to faster find solutions of higher quality) and with bounding and time window constraint propagation (in order to filter the search space). We will present an experimental comparison with state-of-the-art approaches for solving the TSPTW and the time-dependent TSPTW.

TBA

When Models Meet the Real World: Lessons from Applied AI Research

Abstract: In theory, there is no difference between theory and practice; in practice, there is." While the authorship of this famous quote remains debated, it resonates deeply, particularly in the context of applied AI.  When we move from the controlled environment of fundamental research to the complexities of real-world problems, especially with search and model-based AI approaches, the gap between expectation and reality can be vast. This talk will explore some of the challenges encountered when deploying models and search algorithms in practical settings. We'll delve into the lessons learned from bridging this gap, discussing the trade-offs, unexpected pitfalls, and unique rewards of applied research.

Bio: Mauro Vallati is a UKRI Future Leaders Fellow and ACM Distinguished Speaker on Artificial Intelligence (AI) for the UK. He is a Professor of AI at the University of Huddersfield, where he leads the Autonomous Intelligent Systems research center and the AI for Urban Traffic Control research team. Mauro has extensive experience in real-world applications of AI methods and techniques, spanning from healthcare to train dispatching. In 2014, he started working on AI applied to the field of urban traffic control, a line of research that led to numerous high-impact academic publications, patents filed in the United Kingdom, China, and the United States, as well as the deployment of the resulting techniques in urban areas of the United Kingdom.

Heuristic Search vs. Constraint Programming for Single Machine Scheduling

Abstract: In the scheduling literature, single-machine scheduling problems are defined to isolate challenging problem characteristics and investigate the boundary between P and NP-completeness. Typically, problems in the latter class are solved with mixed-integer linear programming, customized branch-and-bound, or dynamic programming. In this tutorial, I will use two recently proposed single-machine scheduling problems to introduce approaches to scheduling using domain-independent dynamic programming (DIDP) and constraint programming (CP). Inspired by AI planning, DIDP is a model-and-solve approach to combinatorial optimization problems that models problems as dynamic programs in a solver-independent modeling language and, currently, solves the models using heuristic search. CP is a well-developed approach to combinatorial optimization with a mature set of concepts for scheduling problems. My primary goals are to introduce the SoCS community to DIDP as a potential area for heuristic search research and to present the higher-level constructs that make CP a state-of-the-art approach to scheduling problems.

Bio: J. Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. For over 25 years, Chris has explored intelligent problem solving in Artificial Intelligence and Operations Research through the frameworks of constraint programming, mixed integer programming, heuristic search, and, most recently, dynamic programming. He has published over 170 papers in international conferences and journals. He has served as the President of both the Executive Committee of the International Conference on Automated Planning and Scheduling and of the Association for Constraint Programming and is an Editor-in-Chief of the Journal of Artificial Intelligence Research. Chris was elected as a AAAI Fellow in 2025.

TBA