# Operations Research

Listed on this page are current research projects being offered for the Vacation Scholarship Program.

## Characterisation of phase-type distributions

(posted for 2017/2018 - Also posted under Stochastic Processes)

A random variable that is defined as the absorption time of a finite-state continuous-time Markov chain with a single absorbing state is said to have a phase-type distribution. The representation of a phase-type distribution is the pair (a,T) where a is the initial state probability vector and T is the infinitesimal generator for the n transient states of the Markov chain. The order of the representation is n. If the representation is of minimal order, then n is known as the order of the distribution.

The Laplace-Stieltjes transform of a phase-type distribution is a rational function. If the numerator and denominator polynomials have no factors in common, the degree of the dominator is called the algebraic degree of the phase-type distribution. In general, the algebraic degree of a phase-type distribution is no larger than its order.

There are a number of open problems concerning the connection between the algebraic degree and the order of phase-type distributions. For example, it is well known that there exist phase-type distributions that have small algebraic degree but very large order. The problem is, however, given a phase-type distribution with a certain algebraic degree, how can we determine its order? And if we can determine its order, how can we find a minimal representation for it?

In this project we will investigate some of these open problems. This project is theoretical in nature and fits in with both Operations Research and Stochastic processes. Some familiarity with coding, particularly in Matlab, will come in handy, but is not essential.

Contact: Mark Fackrell fackrell@unimelb.edu.au

## Predicting Behaviour of Patients with Chronic Conditions

(posted for 2017/2018)

People with chronic and complex health needs are often frequent users of hospital services. Health-care professionals have designed and promoted an alternative service model, by providing health consultancy and primary care at home, in order to reduce the number of unplanned hospital admissions. The purpose of this project is to identify patients with a high-risk of hospital readmission, and predict their health status.

A scoring algorithm based on a variety of factors is currently used to identify high-risk patients. However, it is not efficient enough. We plan to use data from the emergency department to determine the behavioural patterns of high-risk patients, and to use the results to provide a more effective prediction algorithm. Machine learning, or more specifically statistical pattern recognition, is the preferred method. This project is suitable for students interested in data analysis, and adapting/developing algorithms. A probability and statistics background, and some experience in coding, preferably in R, are required.

## Improving the Health of Patients with Chronic Conditions using Better Resource Allocation

(posted for 2017/2018)

MonashWatch is an out of the hospital support service for patients with chronic conditions who have had repeated hospitalisations (click here to find out more). Patients recruited to the program are contacted by phone and asked a series of questions in order to determine their health condition, and whether they need to be admitted to hospital or require some other medical intervention. The primary objective here is to maximise the health outcomes for the patients enrolled in the program. Having healthier patients will lead to a reduction in the number of unplanned hospital admissions, which is the secondary objective here.

Operationally, healthcare practitioners involved in MonashWatch need to decide, each day, which patients to contact. There are many factors that determine which patients to ring. These include: the current health condition of the patient, their health history, their time availability, the last time they were contacted, and their previous responses to the program.

We have modelled this problem as a partially observable Markov decision process, or more specifically, as a restless multi-armed bandit processes (see here). Then Whittle indices (see here) are used to determine which patients to ring each day, and in which order.

The goal of this project is to implement the algorithm using simulated data, and compare the outcomes to other existing algorithms. A probability background and experience in coding in C or Matlab are required.

## Predicting Pedestrian Flows in Melbourne

(posted for 2017/2018)

Recently there are increased risks associated with exposure of persons in central city areas due to terrorism. A number of sensors have been installed in Melbourne’s Central Business District (CBD) that measure the number of persons moving at particular sites. This project will involve analysing this data to identify patterns associated with the numbers of persons walking in public areas. Variations relating to location (nearby land use), time of day, day of week, seasonality and special events will be investigated. A model for predicting the number of pedestrians at specific locations in Melbourne will be developed.

Contact: Joyce Zhang Lele.zhang@unimelb.edu.au and Russell Thompson rgthom@unimelb.edu.au

## Perfect codes in Cayley graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

Perfect codes have been important objects of study ever since the dawn of coding theory in the late 1940s, and after more than six decades they still receive much attention today. The aim of this project is to study perfect codes in Cayley graphs, which are generalizations of perfect codes in the classical setting.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Arc-transitive graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

A finite graph is a finite set together with a family of 2-element subsets of the set; each element in the set is called a vertex and each 2-element subset in the family is called an edge. An oriented edge is called an arc. If all vertices have the “same status” in the graph and all arcs have the “same status” as well, then the graph is said to be arc-transitive. Examples of arc-transitive graphs include the 1-skeletons of the five Platonic polyhedral. The study of arc-transitive graphs has long been an important area in algebraic graph theory with strong links to group theory. The goal of this project is to study some families of arc-transitive graphs whose automorphism groups contain a subgroup acting imprimitively on the vertex set.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Cores of graphs

(Also listed in Discrete Mathematics and Algebraic Combinatorics, posted for 2016-2017)

A homomorphism from a graph X to a graph Y is a mapping from the vertex set of X to the vertex set of Y that preserves the adjacency relation. Two graphs X, Y are said to be homomorphically equivalent if there is a homomorphism from X to Y and also there is a homomorphism from Y to X. The smallest induced subgraph of X that is homomorphically equivalent to X is called the core of X. This notion plays an important role in understanding structure and colouring of graphs. It is also closely related to several application domains, including synchronization. The purpose of this project is to understand the cores of some families of graphs, especially Cayley graphs of some finite groups.

Contact: Sanming Zhou sanming@unimelb.edu.au

## Enhancing traffic flows at continuous flow intersections

(posted for 2016-2017)

Melbourne is going to have a new type of intersections along one of its busiest corridors (see here). The basic idea behind continuous flow intersections is to move right-turning cars to the other side of the road and so they won’t affect opposing traffic when crossing the intersection. The traffic signal control strategy plays a key role in determining the capacity of the intersection. We shall model vehicular traffic and study cooperative traffic signals in order to improve traffic flows and reduce congestion.

Contact:: Dr. Joyce Zhang lele.zhang@unimelb.edu.au

## Happy blood donor program

(posted for 2016-2017)

Recruiting and retaining blood donors is key challenges for blood agencies. The donor service level depends on appropriate appointment strategies. In this mini-project, we shall study a scheduling problem for the appointment reservation that accounts for both booked donors and walk-in donors. It consists of offline scheduling strategies for preallocating time slots to blood donors and online scheduling algorithms for assigning time slots to donors without reservation. The aim is to improve the experience of donors at blood service centers (e.g. reducing their waiting time) and reduce candidate donor abandonment.

Contact:: Dr. Joyce Zhang lele.zhang@unimelb.edu.au

## β-skeletons in the algorithmic closet: computing Relative Neighbourhood Graphs at the drop of a hat

(posted for 2016-2017, reposted for 2017-2018)

Relative neighbourhood graphs (RNGs) are geometric graphs that capture the essence of “closeness” between points in the plane. Intuitively, these graphs provide a picture of the shape of a set of points, which explains their ubiquitous use in computer graphics and computational geometry. It can be shown that the minimum spanning tree of any set of points in the Euclidean plane is a subgraph of the RNG, which makes this class of graphs of fundamental importance to the field of optimal network design.

The RNG is defined as follows: let A be a set of points in the Euclidean plane. For any pair of points x,y in A, the lens associated with x,y is the intersection of two discs of equal radius |xy| centred at x and y respectively. Edge xy is in the RNG if and only if there are no points of A in the interior of the lens associated with x,y.

In this project we seek to better understand the structure of RNGs and their generalisations, such as β-skeletons. The ultimate aim is to produce lightning-fast algorithms for constructing RNGs. A breakthrough in this area will lead to new algorithms for a multitude of important network-design problems.

Contact: Dr. Charl Ras cjras@unimelb.edu.au

## Survivable spanners: short, simple and sparse

(posted for 2016-2017, reposted for 2017-2018)

Suppose you would like to design a graph so that the distance between any pair of nodes is as short as possible. It is tempting to simply take the complete graph, because then every pair of nodes is separated by just a single edge. As an added bonus, the complete graph has very high connectivity, which means if we remove some of its edges then the remaining graph will still be connected. But here’s the problem: complete graphs actually have too many edges, which makes working with them quite inefficient. Plus, if we are designing a network in the plane then a complete graph just won’t do, because complete graphs cannot be embedded in the plane without crossing some edges!

The above graph is a Delaunay triangulation, which is not a bad candidate.

We therefore present the following challenge: is it possible to design a graph that maintains the desirable properties of complete graphs, yet is also sparse enough to be planar? In this project we will study (and try to improve) a powerful contender: the famous t-spanner graph.

Contact: Dr. Charl Ras cjras@unimelb.edu.au

## Squeezing the life out of wireless sensor networks

(posted for 2014-2015, reposted for 2017-2018)

Wireless sensor networks (WSNs) are an exciting new technology that lies at the intersection of communication networks and smart monitoring. It is easy to imagine the benefits of a system consisting of hundreds or even thousands of sensors distributed over a region or an object and able to measure any of a multitude of aspects of their environment, before passing the information to a central base station for intelligent processing. The applications are countless: early detection of bushfires, smart-home systems, battlefield surveillance, animal population tracking, and environmental pollution monitoring – to name just a few.

Although WSNs are already extensively utilised in the real world, their full potential remains largely untapped. In contrast to other types of communication networks, sensor network technology is fundamentally constrained by existing battery technology and energy conservation protocols. This is because WSNs are required to be autonomous for as long as possible, as they are often deployed in remote, harsh, or even hostile environments.

The topology of a WSN (which is the overall pattern formed by the communication links between pairs of sensors) and the relative locations of sensors within the sensing field, play a large role in the efficiency of the network. This project therefore aims to optimise the topological design and sensor location phase of deploying or repairing (augmenting) a WSN. In working on this project students will employ a variety of fascinating mathematical tools from graph theory and network optimisation.

Contact: Dr. Charl Ras cjras@unimelb.edu.au