Mark Wallace

The Zinc modelling language was developed as part of the G12 project, which aimed to generate a new approach to constraint programming. A key feature of Zinc was its solver-independence, deliberately designed to separate the modelling of a discrete optimisation problem from how it is solved. This viewpoint was critical for the later design and uptake of the modelling language MiniZinc, created as a potential standard for constraint programming modelling, by cutting features from the existing Zinc language. MiniZinc has subsequently gone on to grow to encompass most of the Zinc features that were cut, and is widely used.

This article is a retrospective look at practical applications of constraint programming following up on the original article published in 1996.

The transition to battery electric buses (BEBs) presents new challenges to the transportation and energy sectors, necessitating meticulous decision-making for a sustainable transition. This article proposes an integrated optimization model to determine the required number of chargers, charger power, grid capacity upgrade, battery sizing, and charging schedules for a heterogeneous fleet of BEBs. The proposed battery-degradation-aware (DA) model captures the interdependencies of charger deployment, battery sizing, and battery degradation to determine the optimal decisions based on an assumed battery degradation behavior. To this end, we assume an arbitrary nonlinear degradation model and develop a tractable mixed-integer linear programming formulation using a decomposition approach and McCormick relaxation. We further account for the uncertainty of electricity prices to design a robust model. The model is then implemented for a real fleet of 78 buses with different trip schedules, and two empirical battery degradation models are employed. The results show that, considering the two degradation models, the DA model reduces the overall costs by 28.6% and 46.8% in comparison with the degradation-neutral (DN) model due to prolonging the estimated cycle life of batteries by 67% and 135% on average.

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.

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.

This paper investigates what properties a neighbourhood requires to support beneficial local search. We show that neighbourhood locality, and a reduction in cost probability towards the optimum, support a proof that search among neighbours is more likely to find an improving solution in a single search step than blind search. This is the first paper to introduce such a proof. The concepts underlying these properties are illustrated on a satisfiability problem class, and on travelling salesman problems. Secondly, for a given cost target t, we investigate a combination of blind search and local descent termed local blind descent, and present various conditions under which the expected number of steps to reach a cost better than t using local blind descent, is proven to be smaller than with blind search. Experiments indicate that local blind descent, given target cost t, should switch to local descent at a starting cost that reduces as t approaches the optimum.