The thesis argues the case for exploiting certain structures in integer linear programs. Integer linear programs are optimisation problems, where one minimises or maximises a linear function of variables, whose values are required to be integral as well as satisfying certain linear equalities and inequalities. For such an abstract problem, there are very good general-purpose solvers. The state of the art in such solvers is an approach known as “branch and bound”. The performance of such solvers depends crucially on four types of in-built heuristics: primal, improvement, branching, and cut-separation or, more generally, bounding heuristics. However, such heuristics have, until recently, not exploited structure in integer linear programs beyond the recognition of certain types of single-row constraints. Many alternative approaches to integer linear programming can be cast in the following, novel framework. “Structure” in any integer linear program is a class of equivalence among triples of algorithms: deriving combinatorial objects from the input, adapting them, and transforming the adapted object to solutions of the original integer linear program. Many such alternative approaches are, however, inherently incompatible with branch and bound solvers. We, hence, define a structure to be “useful”, only when it extracts submatrices, which allow for the implementation of more than one of the four types of heuristics required in the branch and bound approach. Although the extraction of the best possible submatrices is non-trivial, the lack of a considerable submatrix with a given property can often be recognised quickly, and storing useful submatrices in a “pool” makes it possible to use them repeatedly. The goal is to explore whether the state-of-the-art solvers could make use of the structures studied in the academia. Three examples of useful structures in integer linear programs are presented. A particularly widely applicable useful structure relies on the aggregation of variables. Its application can be seen as a decomposition into three stages: Firstly, we partition variables in the original instance into as small number as possible of support sets of constraints forcing convex combinations of binary variables to be less than or equal to one in the original instance, and one-element sets. Secondly, we solve the “aggregated” instance corresponding to the partition of variables. Under certain conditions, we obtain a valid lower bound. Finally, we fix the solution of the aggregated instance in primal and improvement heuristics for the original instance, and use the partition in hyper-plane branching heuristics. Under certain conditions, the primal heuristics are guaranteed to find a feasible solution to the original instance. We also present structures exploiting mutual-exclusion and precedence constraints, prevalent in scheduling and timetabling applications. Mutual exclusion constraints correspond to instances of graph colouring. For numerous extensions of graph colouring, there are natural primal and branching heuristics. We present lower bounding heuristics for extensions of graph colouring, based on augmented Lagrangian methods for novel semidefinite programming relaxations, and reformulations based on a novel transformation of graph colouring to graph multicolouring. Precedence constraints correspond to an instance of precedence-constrained multi-dimensional packing. For such packing problems, we present heuristics based on an adaptive discretisation and strong discretised linear programming relaxations. On in- stances of packing unit-cubes into a box, the reformulation makes it possible to solve instances that are by five orders of magnitude larger than previously. On instances from complex timetabling problems, which combine mutual- exclusion and packing constraints, the combination of heuristics above can often result in the gap between primal and dual bounds being reduced to under five percent, orders of magnitude faster than using state of the art solvers, without any information being used that is outside of the instance.

This thesis investigates the problem of scheduling and routing employees that are required to perform activities at clients’ locations. Clients request the activities to be performed during a time period. Employees are required to have the skills and qualifications necessary to perform their designated activities. The working time of employees must be respected. Activities could require more than one employee. Additionally, an activity might have time-dependent constraints with other activities. Time-dependent activities constraints include: synchronisation, when two activities need to start at the same time; overlap, if at any time two activities are being performed simultaneously; and with a time difference between the start of the two activities. Such time difference can be given as a minimum time difference, maximum time difference, or a combination of both (min-max). The applicability of such workforce scheduling and routing problem (WSRP) is found in many industries e.g. home health care provision, midwives visiting future mothers, technicians performing installations and repairs, estate agents showing residences for sale, security guards patrolling different locations, etc. Such diversity makes the WSRP an important combinatorial optimisation problem to study. Five data sets, obtained from the literature, were normalised and used to investigate the problem. A total of 375 instances were derived from these data sets. Two mathematical models, an integer and a mixed integer, are used. The integer model does not consider the case when the number of employees is not enough to perform all activities. The mixed integer model can leave activities unassigned. A mathematical solver is used to obtain feasible solutions for the instances. The solver provides optimal solutions for small instances, but it cannot provide feasible solutions for medium and large instances. This thesis presents the gradual development of a greedy heuristic that is designed to tackle medium and large instances. Five versions of the greedy heuristic are presented, each of them obtains better results than the previous one. All versions are compared to the results obtained by the mathematical solver when using the mixed integer model. The greedy heuristic exploits domain information to speed the search and discard infeasible solutions. It uses tailored functions to deal with each of the time-dependent activity constraints. These constraints make more difficult the solution process. Further improvements are obtained by using tabu search. It provides moves based on the tailored functions of the greedy heuristic. Overall, the greedy heuristic and the tabu search, maintain feasible solutions at all times. The main contributions of this thesis are: the definition of WSRP; the introduction of 375 instances based on five data sets; the adaptation of two mathematical models; the introduction of a greedy heuristic capable of obtaining better results than the solver; and, the implementation of a tabu search to further improve the results.

This thesis has two independent parts concerned with different aspects of laziness in functional programs. The first part is a theoretical study of productivity for very restricted stream programs. In the second part we define a programming abstraction over a recursive pattern for defining circular traversals modularly. Productivity is in general undecidable. By restricting ourselves to mutually recursive polymorphic stream equations having only three basic operations, namely "head", "tail", and "cons", we aim to prove interesting properties about productivity. Still undecidable for this restricted class of programs, productivity of polymorphic stream functions is equivalent to the totality of their indexing function, which characterise their behaviour in terms of operations on indices. We prove that our equations generate all possible polymorphic stream functions, and therefore their indexing functions are all the computable functions, whose totality problem is indeed undecidable. We then further restrict our language by reducing the numbers of equations and parameters, but despite those constraints the equations retain their expressiveness. In the end we establish that even two non-mutually recursive equations on unary stream functions are undecidable with complexity $Π_2^0$. However, the productivity of a single unary equation is decidable. Circular traversals have been used in the eighties as an optimisation to combine multiple traversals in a single traversal. In particular they provide more opportunities for applying deforestation techniques since it is the case that an intermediate datastructure can only be eliminated if it is consumed only once. Another use of circular programs is in the implementation of attribute grammars in lazy functional languages. There is a systematic transformation to define a circular traversal equivalent to multiple traversals. Programming with this technique is not modular since the individual traversals are merged together. Some tools exist to transform programs automatically and attribute grammars have been suggested as a way to describe the circular traversals modularly. Going to the root of the problem, we identify a recursive pattern that allows us to define circular programs modularly in a functional style. We give two successive implementations, the first one is based on algebras and has limited scope: not all circular traversals can be defined this way. We show that the recursive scheme underlying attribute grammars computation rules is essential to combine circular programs. We implement a generic recursive operation on a novel attribute grammar abstraction, using containers as a parametric generic representation of recursive datatypes. The abstraction makes attribute grammars first-class objects. Such a strongly typed implementation is novel and make it possible to implement a high level embedded language for defining attribute grammars, with many interesting new features promoting modularity.

This project assesses the impact of traditional Bedouin agricultural gardens on biodiversity within the St Katherine Protectorate, South Sinai, Egypt. The Bedouin harvest rainwater from intermittent flash floods, allowing them to cultivate a wide range of trees and crops throughout the year. Rainwater harvesting techniques such as these can improve crop yields and enhance food security in arid regions, but this is one of the first studies to address the impact upon dependent wildlife. The results showed that the irrigated gardens support a more diverse plant community than the surrounding unmanaged habitat, providing an abundance of floral resources which in-turn enhance pollinator abundance and species richness. The inclusion of a diversity of culturally important minority crops had a dramatic effect upon the structure of plant-pollinator visitation networks, with cultivated plants supplementing the resources provided by wild flowers. The presence of simultaneously flowering crops also had a positive effect upon pollination services to the primary crop (almond), by attracting higher densities of wild pollinators into the gardens and facilitating enhanced fruit set. The higher abundance of resources within the gardens also had a positive impact upon birds in the region, with gardens supporting higher densities and species richness than the unmanaged habitat. Gardens were particularly important for migratory species, providing an important stop-over for numerous small passerines. In conclusion this study provides evidence that irrigated agriculture in arid environments has the potential to increase biodiversity above that found in the un-managed environment. The implications on a local scale are that traditional Bedouin practices can have a positive influence on wildlife within the Protectorate, thus initiatives to fund and support gardeners should be encouraged. On a wider scale the results suggest that rainwater harvesting may provide a sustainable mechanism for increasing food security in arid regions, offering a low-cost strategy for increasing agricultural productivity that does not undermine the biodiversity on which it depends.

The branch of algorithms that uses adaptive methods to select or tune heuristics, known as hyper-heuristics, is one that has seen a large amount of interest and development in recent years. With an aim to develop techniques that can deliver results on multiple problem domains and multiple instances, this work is getting ever closer to mirroring the complex situations that arise in the corporate world. However, the capability of a hyper-heuristic is closely tied to the representation of the problem it is trying to solve and the tools that are available to do so. This thesis considers the design of such problem domains for hyper-heuristics. In particular, this work proposes that through the provision of high-quality data and tools to a hyper-heuristic, improved results can be achieved. A definition is given which describes the components of a problem domain for hyper-heuristics. Building on this definition, a domain for the Vehicle Routing Problem with Time Windows is presented. Through this domain, examples are given of how a hyper- heuristic can be provided extra information with which to make intelligent search decisions. One of these pieces of information is a measure of distance between solution which, when used to aid selection of mutation heuristics, is shown to improve results of an Iterative Local Search hyper-heuristic. A further example of the advantages of providing extra information is given in the form of the provision of a set of tools for the Vehicle Routing Problem domain to promote and measure ’fairness’ between routes. By offering these extra features at a domain level, it is shown how a hyper-heuristic can drive toward a fairer solution while maintaining a high level of performance.

Avian tuberculosis remains a significant economic problem for the poultry industry in many countries. An improved understanding of the interaction between host and mycobacteria is important in designing more efficient vaccine strategies. This study investigated the immune responses to M. avium (Ma.) strains isolated from different sources, Ma strains 1-2 isolated from chickens, Ma.3-5 from cattle and Ma.6-8 from humans, using human cells in vitro and avian cells in vitro and in vivo. The responses were characterised by expression levels of pro-inflammatory cytokines tumour necrosis factor alpha (TNF-α), interleukin (IL)-1β, IL-6 and chemokines CXCLi1 (K60) and CXCLi2 (IL-8) and nitric oxide production. A differential immune response was observed between the strains in terms of induction of cytokine and chemokine production in both human THP-1 and avian HD11 cells. With the exception of the avian strains 1 and 2, all strains induced increases in pro-inflammatory cytokines in THP1 cells. Two of the 3 bovine strains also had this effect in HD11 cells but the other strains had little effect. Use of specific inhibitors indicated that in THP-1 cells the extracellular regulating kinase (ERK) and c-Jun N-terminal kinase (JNK) pathways were important in inducing pro-inflammatory cytokines whereas the p38 pathway did not appear to be involved particularly in regulating TNF-α and IL-1β production. The results also indicate an interaction between the mitogen activated protein kinases (MAPK) pathways studied in regulation of cytokine production in HD11 cells. Although layer chickens were resistant to extensive M. avium multiplication in the tissues, significant expression of pro-inflammatory cytokines was observed in the liver of infected birds towards the end of the period of observation of 21 days as granulomata had started to appear, characterised by lymphocyte accumulation. In conclusion, the findings of this study provide further understanding of the host-mycobacteria interaction and that different strains of M. avium might behave differentially regardless of their source of isolation.

This thesis addresses the problem of airline reserve crew scheduling under crew absence and journey time uncertainty. This work is primarily concerned with the allocation of reserve crew to standby duty periods. The times at which reserve crew are on duty, determine which possible crew absence or delay disruptions they can be used to absorb. When scheduling reserve crew, the goal is to minimise the expected levels of delay and cancellation disruptions that occur on the day of operation. This work introduces detailed probabilistic models of the occurrence of crew absence and delay disruptions and how reserve crew are used to absorb such disruptions. Firstly, separate probabilistic models are developed for crew absence and delay disruptions. Then, an integrated probabilistic model of absence and delay disruptions is introduced, which accounts for: delays from all causes; delay propagation; cancellations resulting from excessive delays and crew absence; the use of reserve crew to cover such disruptions given a reserve policy; and the possibility of swap recovery actions as an alternative delay recovery action. The model yields delay and cancellation predictions that match those derived from simulation to a high level of accuracy and does so in a fraction of the time required by simulation. The various probabilistic models are used in various search methodologies to find disruption minimising reserve crew schedules. The results show that high quality reserve crew schedules can be derived using a probabilistic model. A scenario-based mixed integer programming approach to modelling operational uncertainty and reserve crew use is also developed in this thesis and applied to the problem of reserve crew scheduling. A scenario selection heuristic is introduced which improves reserve crew schedule quality using fewer input scenarios. The secondary objective of this thesis is to investigate the effect of the reserve policy used on the day of operation, that is, determining when and which reserve crew should be utilised. The questions of how reserve policies can be improved and how they should be taken into account when scheduling reserve crew are addressed. It was found that the approaches developed for reserve crew scheduling lend themselves well to an online application, that is, using them to evaluate alternative reserve decisions to ensure reserve crew are used as effectively as possible. In general it is shown that `day of operation' disruptions can be significantly reduced through both improved reserve crew schedules and/or reserve policies. This thesis also points the way towards future research based on the proposed approaches.

This thesis develops measures that enable comparisons of subjective information that is represented through fuzzy sets. Many applications rely on information that is subjective and imprecise due to varying contexts and so fuzzy sets were developed as a method of modelling uncertain data. However, making relative comparisons between data-driven fuzzy sets can be challenging. For example, when data sets are ambiguous or contradictory, then the fuzzy set models often become non-normal or non-convex, making them difficult to compare. This thesis presents methods of comparing data that may be represented by such (complex) non-normal or non-convex fuzzy sets. The developed approaches for calculating relative comparisons also enable fusing methods of measuring similarity and distance between fuzzy sets. By using multiple methods, more meaningful comparisons of fuzzy sets are possible. Whereas if only a single type of measure is used, ambiguous results are more likely to occur. This thesis provides a series of advances around the measuring of similarity and distance. Based on them, novel applications are possible, such as personalised and crowd-driven product recommendations. To demonstrate the value of the proposed methods, a recommendation system is developed that enables a person to describe their desired product in relation to one or more other known products. Relative comparisons are then used to find and recommend something that matches a person's subjective preferences. Demonstrations illustrate that the proposed method is useful for comparing complex, non-normal and non-convex fuzzy sets. In addition, the recommendation system is effective at using this approach to find products that match a given query.

Computational argumentation theory deals with the formalisation of argument structure, conflict between arguments and domain-specific constructs, such as proof standards, epistemic probabilities or argument schemes. However, despite these practical components, there is a lack of implementations and implementation methods available for most structured models of argumentation and translations between them. This thesis addresses this problem, by constructing a general framework for relating, implementing and formally verifying argumentation models and translations between them, drawing from dependent type theory and the Curry-Howard correspondence. The framework provides mathematical tools and programming methodologies to implement argumentation models, allowing programmers and argumentation theorists to construct implementations that are closely related to the mathematical definitions. It furthermore provides tools that, without much effort on the programmer's side, can automatically construct counter-examples to desired properties, while finally providing methodologies that can prove formal correctness of the implementation in a theorem prover. The thesis consists of various use cases that demonstrate the general approach of the framework. The Carneades argumentation model, Dung's abstract argumentation frameworks and a translation between them, are implemented in the functional programming language Haskell. Implementations of formal properties of the translation are provided together with a formalisation of AFs in the theorem prover, Agda. The result is a verified pipeline, from the structured model Carneades into existing efficient SAT-based implementations of Dung's AFs. Finally, the ASPIC+ model for argumentation is generalised to incorporate content orderings, weight propagation and argument accrual. The framework is applied to provide a translation from this new model into Dung's AFs, together with a complete implementation.

This thesis investigates the composition of original adaptive musical soundtracks for locative walking activities such as cultural visiting, mobile games and urban, and nature walks; those semi-formal orchestrated walking experiences. This investigation views the ‘soundtrack’ – similarly to those typically found in ‘display’ media experiences such as films and computer games – as an accompaniment rather than the principal feature of the experience. Thus its role is to support and enhance the walking ‘narrative’. In order to best achieve this the soundtrack needs to be heard as congruent and embedded into the activity. This thesis is oriented towards the field of Human Computer Interaction (HCI) and also at composers of such soundtracks; reflecting the thesis’s intention to develop guidelines for locative soundtrack composition that draws upon detailed mappings between musical structure and spatial structure that drives the creation and experience of both. An initial study explored how a group of participants interpreted and responded to different musical features which adapted to their walking routes. This study revealed that participants formed a set of connections between the physical space and the musical structures. These findings were then used to motivate an in-the-field design, composition and deployment of a large-scale adaptive soundtrack for a public cultural visiting experience, which was subsequently experienced by a group of visitors. This study revealed that the soundtrack was considered congruent with the activity and was deeply engaging, quite distinct from a typical visit to this site. These research activities are reflected upon and discussed to distil a framework of guidelines for composing locative soundtracks that is generalizable to other settings and activities.