Mark Wallace

AAMAS Conference 2026 Conference Paper

TAXI2: Joint Pairing and Vehicle Assignment for Two-Passenger Shared Taxis

• Afzaal Hassan
• Irene Moser
• Mark Wallace
• Daniel Harabor

We study the two-passenger shared taxi problem where a dedicated fleet serves dynamic requests. Existing approaches typically decouple rider matching from fleet assignment by first identifying matches and then dispatching vehicles. This separation often leads to suboptimal fleet utilisation and excessive empty travel. In this work, we present TAXI2, an integer linear programme framework that jointly optimises rider pairing and vehicle assignment in a singledecisionstep. Wefocusonaflexibleservicemodelwheremodest delaysarepermittedtomaximisepoolingefficiency. Usingonehour of New York City taxi demand comprising approximately 24, 000 requests, we demonstrate that our joint formulation achieves 100% service rates. The results demonstrate that our method efficiently solves city-scale problems within practical runtimes, confirming its suitability for real-time operator deployment.

IJCAI Conference 2025 Conference Paper

Dynamic Replanning for Improved Public Transport Routing

• Abdallah Abuaisha
• Bojie Shen
• Daniel D. Harabor
• Peter J. Stuckey
• Mark Wallace

Delays in public transport are common, often impacting users through prolonged travel times and missed transfers. Existing solutions for handling delays remain limited; backup plans based on historical data miss opportunities for earlier arrivals, while snapshot planning accounts for current delays but not future ones. With the growing availability of live delay data, users can adjust their journeys in real-time. However, the literature lacks a framework that fully exploits this advantage for system-scale dynamic replanning. To address this, we formalise the dynamic replanning problem in public transport routing and propose two solutions: a "pull" approach, where users manually request replanning, and a novel "push" approach, where the server proactively monitors and adjusts journeys. Our experiments show that the push approach outperforms the pull approach, achieving significant speedups. The results also reveal substantial arrival time savings enabled by dynamic replanning.

AAAI Conference 2024 Conference Paper

Automatic Core-Guided Reformulation via Constraint Explanation and Condition Learning

• Kevin Leo
• Grame Gange
• Maria Garcia de la Banda
• Mark Wallace

SAT and propagation solvers often underperform for optimisation models whose objective sums many single-variable terms. MaxSAT solvers avoid this by detecting and exploiting cores: subsets of these terms that cannot collectively take their lower bounds. Previous work has shown manual analysis of cores can help define model reformulations likely to speed up solving for many model instances. This paper presents a method to automate this process. For each selected core the method identifies the instance constraints that caused it; infers the model constraints and parameters that explain how these instance constraints were formed; and learns the conditions that made those model constraint instances generate cores, while others did not. It then uses this information to reformulate the objective. The empirical evaluation shows this method can produce useful reformulations. Importantly, the method can be useful in many other situations that require explaining a set of constraints.

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.

AAAI Conference 2017 Short Paper

Fast Electrical Demand Optimization Under Real-Time Pricing

• Shan He
• Mark Wallace
• Campbell Wilson
• Ariel Liebman

The introduction of smart meters has motivated the electricity industry to manage electrical demand, using dynamic pricing schemes such as real-time pricing. The overall aim of demand management is to minimize electricity generation and distribution costs while meeting the demands and preferences of consumers. However, rapidly scheduling consumption of large groups of households is a challenge. In this paper, we present a highly scalable approach to find the optimal consumption levels for households in an iterative and distributed manner. The complexity of this approach is independent of the number of households, which allows it to be applied to problems with large groups of households. Moreover, the intermediate results of this approach can be used by smart meters to schedule tasks with a simple randomized method.

KER Journal 1995 Journal Article

Constraint-based reasoning by E. C. Freuder and A. K. Mackworth (Eds), MIT Press, Cambridge, MA, 1994, pp 403, £31.50/$47.25, ISBN 0–262–56075–5.

• Mark Wallace

IJCAI Conference 1991 Conference Paper

Compiling Integrity Checking into Update Procedures

• Mark Wallace