School of Mathematics and Statistics  Theses
http://hdl.handle.net/11343/295
20200126T08:11:51Z

Stress testing mixed integer programming solvers through new test instance generation methods
http://hdl.handle.net/11343/233868
Stress testing mixed integer programming solvers through new test instance generation methods
Bowly, Simon Andrew
Optimisation algorithms require careful tuning and analysis to perform well in practice. Their performance is strongly affected by algorithm parameter choices, software, and hardware and must be analysed empirically. To conduct such analysis, researchers and developers require highquality libraries of test instances. Improving the diversity of these test sets is essential to driving the development of welltested algorithms.
This thesis is focused on producing synthetic test sets for Mixed Integer Programming (MIP) solvers. Synthetic data should be carefully designed to be unbiased, diverse with respect to measurable features of instances, have tunable properties to replicate realworld problems, and challenge the vast array of algorithms available. This thesis outlines a framework, methods and algorithms developed to ensure these requirements can be met with synthetically generated data for a given problem.
Over many years of development, MIP solvers have become increasingly complex. Their overall performance depends on the interactions of many different components. To cope with this complexity, we propose several extensions over existing approaches to generating optimisation test cases. First, we develop alternative encodings for problem instances which restrict consideration to relevant instances. This approach provides more control over instance features and reduces the computational effort required when we have to resort to searchbased generation approaches. Second, we consider more detailed performance metrics for MIP solvers in order to produce test cases which are not only challenging but from which useful insights can be gained.
This work makes several key contributions:
1. Performance metrics are identified which are relevant to component algorithms in MIP solvers. This helps to define a more comprehensive performance metric space which looks beyond benchmarking statistics such as CPU time required to solve a problem. Using these more detailed performance metrics we aim to produce explainable and insightful predictions of algorithm performance in terms of instance features.
2. A framework is developed for encoding problem instances to support the design of new instance generators. The concepts of completeness and correctness defined in this framework guide the design process and ensure all problem instances of potential interest are captured in the scheme. Instance encodings can be generalised to develop search algorithms in problem space with the same guarantees as the generator.
3. Using this framework new generators are defined for LP and MIP instances which control feasibility and boundedness of the LP relaxation, and integer feasibility of the resulting MIP. Key features of the LP relaxation solution, which are directly controlled by the generator, are shown to affect problem difficulty in our analysis of the results. The encodings used to control these properties are extended into problem space search operators to generate further instances which discriminate between solver configurations.
This work represents the early stages of an iterative methodology required to generate diverse test sets which continue to challenge the state of the art. The framework, algorithms and codes developed in this thesis are intended to support continuing development in this area.
© 2019 Simon Andrew Bowly
20190101T00:00:00Z

Intelligent Management of Elective Surgery Patient Flow
http://hdl.handle.net/11343/230922
Intelligent Management of Elective Surgery Patient Flow
Kumar, Ashwani
Rapidly growing demand and soaring costs for healthcare services in Australia and across the world are jeopardising the sustainability of governmentfunded healthcare systems. We need to be innovative and more efficient in delivering healthcare services in order to keep the system sustainable. In this thesis, we utilise a number of scientific tools to improve the patient flow in a surgical suite of a hospital and subsequently develop a structured approach for intelligent patient flow management. First, we analyse and understand the patient flow process in a surgical suite. Then we obtain data from the partner hospital and extract valuable information from a large database. Next, we use machine learning techniques, such as classification and regression tree analysis, random forest, and knearest neighbour regression, to classify patients into lower variability resource user groups and fit discrete phasetype distributions to the clustered length of stay data.
We use length of stay scenarios sampled from the fitted distributions in our sequential stochastic mixedinteger programming model for tactical master surgery scheduling. Our mixedinteger programming model has the particularity that the scenarios are utilised in a chronologically sequential manner, not in parallel. Moreover, we exploit the randomness in the sample path to reduce the requirement of optimising the process for many scenarios which helps us obtain highquality schedules while keeping the problem algorithmically tractable. Last, we model the patient flow process in a healthcare facility as a stochastic process and develop a model to predict the probability of the healthcare facility exceeding capacity the next day as a function of the number of inpatients and the next day scheduled patients, their resource user groups, and their elapsed length of stay. We evaluate the model's performance using the receiver operating characteristic curve and illustrate the computation of the optimal threshold probability by using costbenefit analysis that helps the hospital management make decisions.
© 2019 Ashwani Kumar
20190101T00:00:00Z

Copulabased spatiotemporal modelling for count data
http://hdl.handle.net/11343/230863
Copulabased spatiotemporal modelling for count data
Qiao, Pu Xue
Modelling of spatiotemporal count data has received considerable attention in recent statistical research. However, the presence of massive correlation between locations, time points and variables imposes a great computational challenge. In existing literature, latent models under the Bayesian framework are predominately used. Despite numerous theoretical and practical advantages, likelihood analysis of spatiotemporal modelling on count data is less wide spread, due to the difficulty in identifying the general class of multivariate distributions for discrete responses.
In this thesis, we propose a Gaussian copula regression model (copSTM) for the analysis of multivariate spatiotemporal data on lattice. Temporal effects are modelled through the conditional marginal expectations of the response variables using an observationdriven time series model, while spatial and crossvariable correlations are captured in a block dependence structure, allowing for both positive and negative correlations. The proposed copSTM model is flexible and sufficiently generalizable to many situations. We provide pairwise composite likelihood inference tools. Numerical examples suggest that the proposed composite likelihood estimator produces satisfactory estimation performance.
While variable selection of generalized linear models is a well developed topic, model subsetting in applications of Gaussian copula models remains a relatively open research area. The main reason is the computational burden that is already quite heavy for simply fitting the model. It is therefore not computationally affordable to evaluate many candidate submodels. This makes penalized likelihood approaches extremely inefficient because they need to search through different levels of penalty strength, apart from the fact suggested by our numerical experience that optimization of penalized composite likelihoods with many popular penalty terms (e.g LASSO and SCAD) usually does not converge in copula models. Thus, we propose to use a criterionbased selection approach that borrows strength from the Gibbs sampling technique.The methodology guarantees to converge to the model with the lowest criterion value, yet without searching through all possible models exhaustively.
Finally, we present an R package implementing the estimation and selection of the copSTM model in C++. We show examples comparing our package to many available R packages (on some special cases of the copSTM), confirming the correctness and efficiency of the package functions. The package copSTM provides a competitive toolkit option for the analysis spatiotemporal count data on lattice in terms of both model flexibility and computational efficiency.
© 2019 Pu Xue Qiao
20190101T00:00:00Z

Singular vectors for the WN algebras and the BRST cohomology for relaxed highestweight Lk(sl(2)) modules
http://hdl.handle.net/11343/228926
Singular vectors for the WN algebras and the BRST cohomology for relaxed highestweight Lk(sl(2)) modules
Siu, Steve Wai Chun
This thesis presents the computation of singular vectors of the W_n algebras and the BRST cohomology of modules of the simple vertex operator algebra L_k(sl2) associated to the affine Lie algebra of sl2 in the relaxed category
We will first recall some general theory on vertex operator algebras. We will then introduce the module categories that are relevant for conformal field theory. They are the category O of highestweight modules and the relaxed category which contains O as well as the relaxed highestweight modules with spectral flow and nonsplit extensions. We will then introduce the W_n algebras and the simple vertex operator algebra L_k(sl2). Properties of the Heisenberg algebra, the bosonic and the fermionic ghosts will be discussed as they are required in the free field realisations of W_n and L_k(sl2) as well as the construction of the BRST complex.
We will then compute explicitly the singular vectors of W_n algebras in their Fock representations. In particular, singular vectors can be realised as the image of screening operators of the W_n algebras. One can then realise screening operators in terms of Jack functions when acting on a highestweight state, thereby obtaining explicit formulae of the singular vectors in terms of symmetric functions.
We will then discuss the BRST construction and the BRST cohomology for modules in category O. Lastly we compute the BRST cohomology for L_k(sl2) modules in the relaxed category. In particular, we compute the BRST cohomology for the highestweight modules with positive spectral flow for all degrees and the BRST cohomology for the highestweight modules with negative spectral flow for one degree.
© 2019 Steve Wai Chun Siu
20190101T00:00:00Z