Now showing 1 - 10 of 22
- PublicationLearning to Sparsify Travelling Salesman Problem InstancesIn order to deal with the high development time of exact and approximation algorithms for NP-hard combinatorial optimisation problems and the high running time of exact solvers, deep learning techniques have been used in recent years as an end-to-end approach to find solutions. However, there are issues of representation, generalisation, complex architectures, interpretability of models for mathematical analysis etc. using deep learning techniques. As a compromise, machine learning can be used to improve the run time performance of exact algorithms in a matheuristics framework. In this paper, we use a pruning heuristic leveraging machine learning as a pre-processing step followed by an exact Integer Programming approach. We apply this approach to sparsify instances of the classical travelling salesman problem. Our approach learns which edges in the underlying graph are unlikely to belong to an optimal solution and removes them, thus sparsifying the graph and significantly reducing the number of decision variables. We use carefully selected features derived from linear programming relaxation, cutting planes exploration, minimum-weight spanning tree heuristics and various other local and statistical analysis of the graph. Our learning approach requires very little training data and is amenable to mathematical analysis. We demonstrate that our approach can reliably prune a large fraction of the variables in TSP instances from TSPLIB/MATILDA (>85%) while preserving most of the optimal tour edges. Our approach can successfully prune problem instances even if they lie outside the training distribution, resulting in small optimality gaps between the pruned and original problems in most cases. Using our learning technique, we discover novel heuristics for sparsifying TSP instances, that may be of independent interest for variants of the vehicle routing problem.
- PublicationIdentifying Patterns of Learner Behaviour: What Business Statistics Students do with Learning ResourcesThe interactions of early stage business students with learning resources over the duration of an introductory statistics module were analysed using latent class analysis. Four distinct behavioural groups were identified. While differing levels of face-to-face attendance and online interaction existed, all four groups failed to engage with online material in a timely manner. The four groups were found to demonstrate significantly different levels of attainment of the module learning outcomes. The patterns of behaviour of the different groups of students give insights as to which analytics education learning resources students use and how their use patterns relate to their level of attainment of the module learning outcomes.
- PublicationHousehold Classification Using Smart Meter DataThis article describes a project conducted in conjunction with the Central Statistics Office of Ireland in response to a planned national rollout of smart electricity metering in Ireland. We investigate how this new data source might be used for the purpose of official statistics production. This study specifically looks at the question of determining household composition from electricity smart meter data using both Neural Networks (a supervised machine learning approach) and Elastic Net Logistic regression. An overview of both classification techniques is given. Results for both approaches are presented with analysis. We find that the smart meter data alone is limited in its capability to distinguish between household categories but that it does provide some useful insights.
Scopus© Citations 43 556
- PublicationSmart Meter Tariff Design to Minimise Wholesale RiskSmart metering in electricity markets offers an opportunity to explore more diversetariff structures. In this article a Genetic Algorithm (GA) is used to design Time ofUse tariffs that minimise the wholesale risk to the supplier in residential markets.Residential demand and the System Marginal Price of Ireland's Single ElectricityMarket are simulated to estimate the wholesale risk associated with each tariff.
374Scopus© Citations 1
- PublicationInteger-Programming Ensemble of Temporal-Relations ClassifiersThe extraction of temporal events from text and the classification of temporal relations among both temporal events and time expressions are major challenges for the interface of data mining and natural language processing. We present an ensemble method, which reconciles the outputs of multiple heterogenous classifiers of temporal expressions. We use integer programming, a constrained optimisation technique, to improve on the best result of any individual classifier by choosing consistent temporal relations from among those recommended by multiple classifiers. Our ensemble method is conceptually simple and empirically powerful. It allows us to encode knowledge about the structure of valid temporal expressions as a set of constraints. It obtains new state-of-the-art results on two recent natural language processing challenges, SemEval-2013 TempEval-3 (Temporal Annotation) and SemEval-2016 Task 12 (Clinical TempEval), with F1 scores of 0.3915 and 0.595 respectively.
Scopus© Citations 1 492
- PublicationProgram Optimisation with Dependency InjectionFor many real-world problems, there exist non-deterministic heuristics which generate valid but possibly sub-optimal solutions. The program optimisation with dependency injection method, introduced here, allows such a heuristic to be placed under evolutionary control, allowing search for the optimum. Essentially, the heuristic is “fooled” into using a genome, supplied by a genetic algorithm, in place of the output of its random number generator. The method is demonstrated with generative heuristics in the domains of 3D design and communications network design. It is also used in novel approaches to genetic programming.
492Scopus© Citations 3
- PublicationA Decomposition Algorithm for the Ring Spur Assignment ProblemThis paper describes the ring spur assignment problem (RSAP), a new problem arising in the design of next generation networks. The RSAP complements the sonet ring assignment problem (SRAP). We describe the RSAP, positioning it in relation to problems previously addressed in the literature. We decompose the problem into two IP problems and describe a branch-and-cut decomposition heuristic algorithm suitable for solving problem instances in a reasonable time. We present promising computational results.
Scopus© Citations 5 471
- PublicationProbability density distributions for household air source heat pump electricity demandThe Irish government is implementing policies to transition Ireland to a low carbon and environmentally sustainable economy by 2050. Ireland has sectoral targets of 600,000 installed heat pumps by 2030, currently roughly 28,000 are installed. Such a high target of heat pumps will not only have a significant effect on electricity demand but also on the management and operation of the grid. In this paper we explore the demand from homes heated by air source heat pumps using an innovative dataset from a field trial in Ireland. To assess the impact of large-scale adoption of heat pumps, this paper estimates the after diversity maximum demand per heat pump heated home. In particular we explore statistical distributions to best model coincident demand, and estimate after diversity maximum demand per home. We use the software package RStudio to model several different distributions. Based on goodness-of-fit statistics and criteria, a Gamma distribution is the best fit. We apply our methodology to data from a similar heat pump trial in the UK to complement our results.
Scopus© Citations 5 180
- PublicationA Branch and Cut Algorithm for the Ring Spur Assignment ProblemThe Ring Spur Assignment Problem (RSAP) arises in the design of Next Generation Telecommunications Networks (NGNs) and has applications in location-allocation problems. The aim is to identify a minimum cost set of interconnected ring spurs. We seek to connect all nodes of the network either on a set of bounded disjoint local rings or by a single spur edge connected to a node on a local ring. Local rings are interconnected by a special ring called the tertiary ring. We show that the problem is NP-Hard and present an Integer Programming formulation with additional valid inequalities. We implement a branch-and-cut algorithm and present our conclusions with computational results.
477Scopus© Citations 9
- PublicationA Genetic Algorithm for a Green Vehicle Routing ProblemWe propose a Genetic Algorithm (GA) to address a Green Vehicle Routing Problem (G-VRP). Unlike classic formulations of the VRP, this study aims to minimise the CO 2 emissions per route. The G-VRP is of interest to policy makers who wish to reduce greenhouse gas emissions. The GA is tested on a suite of benchmark, and real-world instances which include road speed and gradient data. Our solution ap- proach incorporates elements of local and population search heuristics. Solutions are compared with routes currently used by drivers in a courier company. Reductions in emissions are achieved without incurring additional operational costs.