Mark Wallace

Abdallah Abuaisha, Bojie Shen, Daniel Harabor et al.

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.

Mark G. Wallace

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.

Mark G Wallace

This paper investigates why it is beneficial, when solving a problem, to search in the neighbourhood of a current solution. The paper identifies properties of problems and neighbourhoods that support two novel proofs that neighbourhood search is beneficial over blind search. These are: firstly a proof that search within the neighbourhood is more likely to find an improving solution in a single search step than blind search; and secondly a proof that a local improvement, using a sequence of neighbourhood search steps, is likely to achieve a greater improvement than a sequence of blind search steps. To explore the practical impact of these properties, a range of problem sets and neighbourhoods are generated, where these properties are satisfied to different degrees. Experiments reveal that the benefits of neighbourhood search vary dramatically in consequence. Random problems of a classical combinatorial optimisation problem are analysed, in order to demonstrate that the underlying theory is reflected in practice.

Mark Wallace, Aldeida Aleti

For most practical optimisation problems local search outperforms random sampling - despite the "No Free Lunch Theorem". This paper introduces a property of search landscapes termed Neighbours' Similar Fitness (NSF) that underlies the good performance of neighbourhood search in terms of local improvement. Though necessary, NSF is not sufficient to ensure that searching for improvement among the neighbours of a good solution is better than random search. The paper introduces an additional (natural) property which supports a general proof that, for NSF landscapes, neighbourhood search beats random search.

Aldeida Aleti, Mark Wallace, Markus Wagner

Premature convergence can be detrimental to the performance of search methods, which is why many search algorithms include restart strategies to deal with it. While it is common to perturb the incumbent solution with diversification steps of various sizes with the hope that the search method will find a new basin of attraction leading to a better local optimum, it is usually not clear how big the perturbation step should be. We introduce a new property of fitness landscapes termed "Neighbours with Similar Fitness" and we demonstrate that the effectiveness of a restart strategy depends on this property.

David A. Cohen, Martin C. Cooper, Artem Kaznatcheev et al.

We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variable interactions has bounded treewidth (in our construction, treewidth 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum. This is an improvement on prior recursive constructions of long steepest ascents, which we prove to need constraint graphs of unbounded treewidth.

Parisa Babaheidarian, Mark Wallace

Recent work (Baluja, 2017) showed that using a pair of deep encoders and decoders, embedding a full-size secret image into a container image of the same size is achieved. This method distributes the information of the secret image across all color channels of the cover image, thereby, it is difficult to discover the secret image using conventional methods. In this paper, we propose a new steganalysis technique which achieves complete recovery of the embedded secret in steganography images. We incorporate a deep neural network to decode an approximate estimate of the secret image followed by a domain adaptation technique based on generative adversarial networks which transfers the decoded image into a high quality RGB image with details visible to human eyes. Our steganalysis technique can be served as an attack model against which the security level of an arbitrary embedded-based digital watermarking or a steganography algorithm can be evaluated. Furthermore, our method can be used as a general framework to decode a high quality image message from a noisy observation of an encoded message.

Tim Dwyer, Christopher Mears, Kerri Morgan et al.

Drawings of highly connected (dense) graphs can be very difficult to read. Power Graph Analysis offers an alternate way to draw a graph in which sets of nodes with common neighbours are shown grouped into modules. An edge connected to the module then implies a connection to each member of the module. Thus, the entire graph may be represented with much less clutter and without loss of detail. A recent experimental study has shown that such lossless compression of dense graphs makes it easier to follow paths. However, computing optimal power graphs is difficult. In this paper, we show that computing the optimal power-graph with only one module is NP-hard and therefore likely NP-hard in the general case. We give an ILP model for power graph computation and discuss why ILP and CP techniques are poorly suited to the problem. Instead, we are able to find optimal solutions much more quickly using a custom search method. We also show how to restrict this type of search to allow only limited back-tracking to provide a heuristic that has better speed and better results than previously known heuristics.