This sections shows a number of Research Themes of interested for our group. You can click on the picture or on 'More >>' to get more information about each of these topics.
Machine Learning and Data Mining.
Machine Learning, or how to construct programs that automatically learn from experience is a core component of Artificial Intelligence. Its aim is to identify patterns in data and construct some knowledge (e.g. rules, decision trees, support vectors) that model this data. Some of its applications include medical diagnosis, bioinformatics, stock markets predictions, search engines, recommendation systems, etc. and, in general, any kind of prediction. Data Mining deals with the extraction of knowledge from vasts amounts of data. It contains machine learning as one of its main core components. While machine learning aim is to obtain accurate models, data mining is more focused on knowledge discovery. That is, providing the users with new insight about the data being mined.
As a knowledge based methodology, CBR solves problems by reusing knowledge for solving previous similar problems. The knowledge is modeled and stored as cases in the reasoning system. We investigate CBR techniques to solve complicated scheduling problems including personal scheduling and timetabling problems. Not only solutions themselves are reused, but also are previous heuristics in similar problem solving situations reused for solving different scheduling problems.
Most research about evolutionary algorithms and other randomised search heuristics is of an empirical nature. The theoretical understanding of these methods has been limited. We analyse the runtime (also called optimisation time) of randomised search heuristics mathematically using techniques from probability theory, randomised algorithms, and computational complexity. This type of analysis provides mathematically proven statements about the performance of randomised search heuristics. Such results give valuable insights into how the performance of a given randomised search heuristic depends on its parameter-settings and on the characteristics of the underlying optimisation problem.
Fuzzy systems is an alternative to traditional notions of set membership and logic. Many decision-making and problem-solving tasks are too complex to be understood quantitatively, however, people succeed by using knowledge that is imprecise rather than precise. We use this technology in application areas such as medical optimisation and production scheduling.
Heuristics and Metaheuristics.
Although powerful optimisation techniques and other exact algorithms exist to tackle difficult search and optimisation problems, in some cases such techniques take too long to produce a solution of the required quality within realistic timescales. Hence, heuristic and metaheuristic techniques are powerful and flexible alternatives to tackle these difficult problems. Heuristic and metaheuristic algorithms seek to produce good-quality solutions in reasonable computation times by following a series of pre-defined and often also randomised steps. Heuristics and metaheuristics can be constructive (produce a solution and then stop) or improvement (iteratively improve the current solution and then stop) approaches, but they can also be single-solution or population-based. We investigate and develop a range of heuristic and metaheuristic (H/MH) techniques including their hybridisation with other methods. We develop tailored H/MH algorithms to tackle specific problems. We also develop more generalised H/MH strategies to tackle a broader range of problems. Investigating the functioning and performance of these techniques is also part of our research work.
Multi-objective optimisation is an important area of research that focuses on techniques to tackle problems in which multiple (possibly conflicting) objectives exist. For such problems, the goal is often to obtain a set of solutions representing a compromise between the various objectives. We investigate multi-objective optimisation techniques to solve a range of multi-objective problems. Our aim is to understand the nature of these multi-objective problems in order to tackle them within a multi-objective framework. We also investigate the applicability of multi-objective search and optimisation approaches to a variety of problems, mainly of combinatorial nature. Developing effective and efficient methods for tackling complex multi-objective optimisation problems is also part of our research work, which covers a range of multi-objective techniques including goal programming, evolutionary multi-objective algorithms and multi-objective variants of many other heuristic and metaheuristic algorithms.
Constraint programming originated from constraint solving and logic
programming. Based on the strong constraint propagation and integrated with heuristic search, it has been successfully applied to many highly constrained combinatorial optimisation problems. We investigate advanced constraint programming techniques which are closely integrated with operational research techniques (including column generation) and heuristics for solving highly complex and constrained real world problems
including nurse scheduling problems.
In educational timetabling problems, a set of exams, courses or project presentations, etc. need to be scheduled into limited resources including rooms within a certain number of time periods. A number of constraints of different importance, which are usually different in different institutions also need to be satisfied. In ASAP group, we investigate a wide range of algorithms in meta-heuristics and different techniques concerning multi-objective and constraints handling, etc in educational timetabling problems. One of our research directions is to explore approaches that can operate at a higher level of generality than what the current timetabling system can support.
Personnel scheduling problems are found in a wide variety of environments. Some of the most complex and challenging problems arise in hospitals and healthcare centres, for example nurse and physician rostering. The benefits of automating the rostering process in these situations include reducing the planner's workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce leads to higher productivity, increased quality of patient service and a better level of healthcare. The ASAP group has developed a number of novel and very effective rostering algorithms in real world scenarios. These approaches include tabu search, variable neighbourhood search, memetic algorithms, case-based reasoning, hyperheuristics, hybrid methods and many others. In order to scientifically test and validate these algorithms we have created a suite of highly challenging benchmark data sets from a number of hospitals around the world. These data sets are publicly available athttp://www.cs.nott.ac.uk/~tec/NRP/. This collection is the only source of a wide range of real world nurse rostering benchmark instances and a valuable asset of the personnel scheduling community.
Real world production scheduling problems, which require the efficient allocation of jobs onto machines, are notoriously complex: machines are many and of different characteristics, workers get sick, new jobs arrive to the shop floor, machines break down, etc. Moreover, the case where two or more objective functions have to be optimised simultaneously is often present. Under these circumstances, classical optimisation methods are usually insufficient and, in order to be successful, scheduling systems have to make use of modern artificial intelligence (AI) based techniques. ASAP is a leader in the investigation, design and application of AI techniques, including evolutionary algorithms and hyperheuristics, hybridised with fuzzy systems and multi-objective optimisation approaches, to the scheduling and rescheduling of production shops. Algorithms developed by ASAP have been successfully applied to a wide variety of problems that emerge, among others, from steel production, printed circuit board assembly, cardboard box manufacturing and the printing industry.
Cutting and Packing.
We are conducting research into a variety of stock cutting problems. These include the knapsack problem, regular and irregular 2-dimensional nesting, and other stock cutting variants. We are looking at placement algorithms, case-based reasoning approaches and other current techniques to solve such problems whilst also developing new heuristics and metaheuristics to reduce the size of the search space and produce good solutions. Our research is particularly relevent to the manufacturing industry, so we are closely working with a local company so that our research can be implemented for real world applications.
Recent research on both combinatorial optimisation and financial engineering leads to an increased amount of research in portfolio optimisation based on the modern portfolio theory, i.e the Mean-Variance model. By selecting a subset of investment assets, the objectives of the problem are to maximise the expected return as well as to minimise the risk. We investigate advanced computational methods including matheuristics based on mathematical programming and heuristics to address large scale portfolio optimisation problems with additional constraints to the basic model. In addition, intelligent search algorithms are studied concerning a range of real world trading constraints and multiple objectives.
Multicast routing in wireless telecommunication aims to identify least cost paths in multicast groups satisfying a range of constraints including delay bound. Recent multimedia multicast applications are featured with a range of Quality of Service requirements. These include bandwidth, delay variation as well as link cost and utilisation. The introduction of network coding further extends the complexity of the problem, attracting an increasing research attention in both information theory and operational research. We investigate advanced evolutionary algorithms to address such problems with real world constraints and multiple objectives. Fundamental analysis on the fitness landscape also provide insight on designing effective evolutionary algorithms. Robust techniques are also investigated conncerning dynamic and delay tolerant network routing.
Office Space Allocation.
The office space allocation problem refers to the allocation of entities to the available office space. Entities can be people (e.g. staff, research students, etc.) or 'functions' (e.g. meeting room, utility room, toilet, etc.). The available office space is usually a set of physical rooms within a building. Each entity requires certain office space (i.e. floor area) and each room has certain capacity (i.e. room size). There are additional requirements that limit the way in which the entities can be allocated to the rooms. For example, certain entities must not share a room with another entitiy or certain entities should be allocated to the same or 'nearby' rooms as other entities. The problem is then to assign each entity to a room in such as way that the utilisation of the available office space is maximised while considering the additional requirements. This is very difficult combinatorial optimisation problem given its highly constrained nature (the additional requirements). We have investigated this problem for several years now including the modelling and understanding of the problem as well as the development of mathematical programming, heuristic and metaheuristic techniques to solve it effectively and efficiently.
Transportation Logistics Optimisation.
There is a variety of difficult optimisation problems in transport logistics and we conduct research on the modelling and solving of several of these problems. In particular, we conduct research on problems arising in air transport and also road transport scenarios. For example, our expertise in air transportation problems includes airport operations such as aircraft landing and take-off, baggage handling and stand/gate allocation among others. Our expertise on road transportation problems includes truck loading and routing, warehouse operations, packing of good in HGVs and planning of maintenance operations. Our research at the interface of operations research, computer science and artificial intelligence focuses on the development of effective computational techniques to underpin the implementation of decision support systems to assist in the more efficient execution of these transportation operations. We have a strong record of working with industry in the modelling and solution of real-world complex transportation logistics problems.