Enhancing decomposition techniques using large-neighbourhood search to solve large-scale optimisation problems

点击翻译按钮获取中文摘要

Optimisation is a fundamental part of today's society. The planning, management and operation of many services rely on optimisation for efficient and cost effective delivery of services. With an ever growing demand for services, the need for efficient operations is becoming more critical.Transportation is a major beneficiary of research and development of optimisation techniques. The benefits are observed in a reduction of costs through the more efficient running of railways, an increase in the provided services by airlines through better allocation of aircraft and an improvement in the on-time performance of airlines and railway operators through the better integration of crew and aircraft. However, the ability to maintain reduced costs and deliver efficient operations is limited by our capacity to solve optimisation problems of ever growing complexity. Further advances in transportation and other industries will be delivered through the research and development of solution techniques for optimisation problems.The aim of this research is to improve current optimisation techniques to extend the domain of solvable problems beyond current limits. The research will draw upon current research of two closely related fields of mathematical optimisation---mixed integer programming (MIP) and decomposition techniques. The inexact MIP solution approach of large-neighbourhood search is valuable for finding good solutions to optimisation problems. While the exact decomposition technique of Benders' decomposition greatly simplifies problem formulations and provides an effective solution approach. The recent developments in large-neighbourhood search will be employed to significantly enhance the solution algorithm of Benders' decomposition. This project will exploit synergies from the integration these two methods to extend current capabilities for solving large-scale optimisation problems.This project will investigate the enhancement of Benders' decomposition and identify strategies to effectively employ parallel computing infrastructure. The fellowship will achieve the following:1) The production of a software package for applying Benders' decomposition to general large-scale optimisation problems. An enhanced solver will be developed through the integration of Benders' decomposition with large-neighbourhood search. The resulting software will be capable of solving large-scale optimisation problems from industry and academia.2) The development of novel parallelisation schemes for Benders' decomposition using the framework of large-neighbourhood search heuristics. The parallelisation schemes will exploit modern computing architecture to significantly reduce solution run times. Further, the algorithmic development will lay the ground work for future parallel computing research.The developed software will provide tools to apply Benders' decomposition to optimisation problems arising in academia and industry. This will be demonstrated through interdisciplinary collaborative projects in transportation, bioinformatics and climate science. In particular, the recovery of flight schedules after disruption will be investigated, optimisation techniques will be applied to analyse viral sequences and novel algorithms will be employed to identify of strong winds that converge into the jet streams. To facilitate the transfer of knowledge to industry and the wider academic community the available software and solution algorithms will be made freely available for academic use.