Research project: Discrete Optimisation

Currently Active:: Yes

Our work in discrete optimisation mainly focuses on combinatorial optimisation, especially scheduling in production and transport. For train, vehicle and production scheduling problems, we design models and develop algorithms that are more closely related to industry practice. For example, we have applied our work on air traffic management resulting in scheduling of airport runways to improve throughput while maintaining minimum separation times between aircraft.

Project Overview

Cutting plane generation beyond cut violation

Cutting plane generation is one of the key components of state-of-the-art algorithms for the solution of integer programming problems. This project aims at developing novel cut generation paradigms which go beyond the classic notion of cut violation. At present, we highlight two main research directions. On the one hand, we develop ways to translate the best pivoting rules known for the simplex method into suitably defined (and typically nonlinear) cut generating subproblems and algorithms. On the other hand, we aim at developing techniques based on entirely new concepts, among which those of cut coordination and bound-optimal cut generation. The former is a mathematically well-defined way of cutting planes among which a measure of diversity is maximized. The latter is a paradigm calling for the generation of one or more cuts which, when added to the current relaxation, yield the provably largest bound improvement.

Optimisation in Multi-Hop Wireless Networks

The demand for high-rate wireless services continues to grow, and has done so for decades. Efficiently transmitting data in wireless networks requires joint optimization of routing, scheduling, and power control. We are interested in mathematical algorithms useful for the design and the optimization of multi-hop ad-hoc wireless networks, especially with respect to routing, power control, decomposition approaches, cooperative broadcasts, etc. Most of these algorithms have to work in a distributed fashion in a real-time environment, so their design can be considered as hard. Most of our work is done in conjunction with industrial partners like Alcatel-Lucent, Bell Labs, Qualcomm, and colleagues from the Department of Communications Engineering at the University of Bremen.

Network Optimisation

We are address traffic engineering and network design problems from a discrete optimization perspective, with focus on two topics: network routing with fairness constraints and virtual network embedding. Classical approaches to network routing typically assume that, given a set of connections with an origin and a destination, the network operator can choose how to route them by both choosing the routing paths and the bandwidth allocations. This assumption becomes unrealistic in the Internet, where an automated Traffic Control Protocol (TCP) determines the traffic rate autonomously (solving an implicit optimization problem which maximizes a measure of fairness of the bandwidth allocation) in a way that the network operator cannot affect. In this activity, we cast the network routing problem as a bilevel program with two actors, network operator and TCP, considering different measures of fairness (such as max-min fairness and proportional fairness) and adopting integer programming techniques to solve the problem to global optimality. Network virtualization is one of the key technologies of the future of large scale networking, including the Internet. The idea is to decouple the physical (low level) management aspects of a networking environment from those (of higher level) involving service provisioning.

Skill development in a multi-skilled workforce for maintenance operations

Workforce planning is of strategic importance to most organisations, and particularly challenging when required to plan for various multiple specialised skills of the workforce and when the future demand for each type of task is uncertain. In such environments, the value of dynamic skill development within a workforce cannot be ignored. We are in particular interested in increasing our understanding of how multiple skills and their development should be distributed among a pool of technicians, and how this may depend on the operational environment. We consider novel approaches based on stochastic mixed integer linear programming for determining optimal strategic plans of hiring and skill development of a multi-skilled workforce when there are high levels of uncertainty in the tasks. In particular, we consider the case of complex maintenances line operated by a multi-skilled workforce with these characteristics, and the problem calls for determining effective and efficient strategies for hiring, training, and operational allocation of supervisors and technicians. Skill development can occur through training exercises and through the experience of executing tasks in collaboration with higher skilled technicians.

Related research groups

Operational Research
Computational Optimisation

Share this research project Share this on Facebook Share this on Twitter Share this on Weibo